Zadanie

Nebolo to tak dávno, čo bol náš Emko totálny šialený zabiják. Kežďe bola doba ťažká, jediný zamestnávateľ ochotný zamestnať ho bola Korporátna spoločnosť pseudomafiánov. Tí mali \(n\) nepriateľov, ktorých sa potrebovali zbaviť. Emko ale nebol žiadny lacný chlap, a tak si za odstránenie každého z nepriateľov účtoval nie nutne rôzne sumy.

Spoločnosť má momentálne obmedzené financie, a tak vie zaplatiť odstránenie len niekoľkých nepriateľov. Pre spoločnosť majú nepriatelia iné hodnoty, ako pre Emka, a ešte neživoria, preto nie je najlacnejšie riešenie nutne najlepšie. Potrebovali by teda vedieť \(k\) najmenších účtov, aké vie Emko vystaviť. Potom už ľahko vyberú najlepšiu variantu pre získanie vlády nad svetom.

Keďže ale Emko nepatrí ku najchytrejším a na pohovore mu namerali IQ rovné celých \(26\), je občas ochotný spoločnosti zaplatiť za objednávku. Teda spoločnosť vie dokonca okrem získania vlády občas aj zbohatnúť. Podieľajte sa na tejto akcii a buďte pri koryte aj VY. Pomôžte spoločnosti zistiť \(k\) najmenších účtov, aké nám vie Emko dať.

Úloha

Máte zadaných \(n\) čísiel: ceny, za ktoré je Emko ochotný odstrániť jednotlivých nepriateľov. Zistite hodnoty \(k\) najmenších neprázdnych rôznych účtov, ktoré môže Emko vystaviť. Každý účet je určený zoznamom nepriateľov, ktorých chceme odstrániť, a jeho hodnota je súčet cien týchto nepriateľov. Účty sú rôzne, ak zoznam ľudí na nich nie je identický.

Formát vstupu

Na prvom riadku vstupu sa nachádzajú dve čísla oddelené medzerou, a to \(1 \leq n \leq 200\,000\) a \(1 \leq k \leq \min(2^n - 1, 200\,000)\). Na druhom riadku bude \(n\) medzerou oddelených čísel \(a_i\) (\(|a_i| \leq 10^9\)), a to je cena, za ktorú je Emko ochotný odstrániť \(i\)-teho nepriateľa.

Sú štyri sady vstupov, s takýmito obmedzeniami:

číslo sady \(1\) \(2\) \(3\) \(4\)
\(n \leq\) \(10\) \(100\) \(1\,000\) \(200\,000\)
\(k \leq\) \(1\,023\) \(200\,000\) \(200\,000\) \(200\,000\)

Formát výstupu

Na výstup vypíšte \(k\) riadkov, a to hodnoty \(k\) najmenších možných účtov usporiadaných od najmenšieho. Na každom riadku vypíšte jednu hodnotu.

Príklady

Input:

2 3
-1 1

Output:

-1
0
1

Input:

3 7
-1 0 1

Output:

-1
-1
0
0
0
1
1

Najprv vyriešime ľahšiu úlohu (aj keď ťažko predstaviteľnú) a to takú, že budeme predpokladať, že Emko až taký hlúpy nie je. To znamená, že nie je ochotný zaplatiť za objednávku niektorého z nepriateľov, teda všetky čísla na vstupe budú nezáporné.

Hlavná myšlienka

Keďže chceme vypisovať hodnoty možných účtov od najmenšieho, najrozumnejšie je všetkých kandidátov na najlacnejší účet nahádzať do minimovej haldy a potom odtiaľ vyberať vždy najlacnejší. Kandidátov ale máme všetky podmnožiny, čo je teda až \(2^n\) prvkov v halde. Stačí si však uvedomiť, že kandidátmi na najlacnejší (ešte nevypísaný účet) nie sú od začiatku všetky podmnožiny, ale sa nimi stanú až neskôr.

Kandidáti

Vieme napríklad povedať, že ak \(A\) je podmnožinou \(B\), tak \(A\) vypíšeme určite skôr, lebo \(B\) získame z \(A\) pridaním niekoľko nezáporných prvkov. Takže množina sa stane kandidátom až keď vypíšeme všetky jej podmnožiny, a dovtedy ju do haldy vôbec nemusíme pridávať. Čo teda spôsobí, že v halde sa vyskytne výrazne menej vecí, keďže \(k\) je relatívne malé.

Vyššie uvedená úvaha sa ale dá potiahnuť ešte ďalej. Vieme si vybudovať graf závislostí, kde vrcholy sú možné účty a orientovaná hrana z \(A\) do \(B\) bude znamenať, že \(B\) pridáme do haldy (stane sa kandidátom) keď vypíšeme \(A\).

Od takéhoto grafu budeme požadovať viacero vecí. Za prvé si musíme byť istý, že \(A\) je lacnejší ako \(B\), teda že sa od nás nečakalo, že vypíšeme \(B\) a \(B\) sme ešte nemali ani v halde. A zároveň nechceme ten istý účet pridávať do haldy viackrát, teda do jedného vrchola môže smerovať najviac jedna hrana. Nakoniec musí byť každý vrchol dosiahnuteľný z vrcholu reprezentujúceho najlacnejší účet.

Rozmyslite si, prečo sú horeuvedené tri podmienky nutné a zároveň postačujúce na to, aby náš algoritmus (\(k\)-krát vyber najlacnejšieho kandidáta z haldy a pridaj do nej nových kandidátov) fungoval správne.

Ako rozumne zvoliť graf?

Ak máme vrchol reprezentujúci podmnožinu \(\lbrace a_1, a_2, ..., a_n \rbrace\), tak budú z neho viesť hrany do vrcholov reprezentujúcich množiny \(\lbrace a_1, a_2, ..., a_n, b \rbrace\) a \(\lbrace a_1, a_2, ..., a_{n-1}, b \rbrace\), kde \(b\) označuje najmenšie číslo väčšie ako \(a_n\).

Zjavne platí, že do každého vrchola vedie len jedna hrana. A tiež hrany vedú smerom od lacnejších účtov ku drahším, keďže prvý typ hrany vedie ku nadmnožine a pri druhom type vymeníme \(a_n\) za \(b\), čo je aspoň tak veľké číslo. A nakoniec, na príklade ilustrujeme, akým spôsobom vieme dosiahnuť každý vrchol (a všeobecný prípad nechávame na rozmyslenie): ak sú všetky čísla \(1, 2, 3, 4, 5, 6, 7, 8\), tak napríklad vrchol \(\lbrace 1, 3, 4, 7\rbrace\) dosiahneme takto:

\[ \lbrace 1 \rbrace \rightarrow \lbrace 1, 2 \rbrace \rightarrow \lbrace 1, 3 \rbrace \rightarrow \lbrace 1, 3, 4 \rbrace \rightarrow \lbrace 1, 3, 4, 5 \rbrace \rightarrow \lbrace 1, 3, 4, 6 \rbrace \rightarrow \lbrace 1, 3, 4, 7 \rbrace \]

Riešenie našej podúlohy

To čo teraz vieme spraviť je, že na začiatku pridáme do haldy najlacnejší prvok, a následne \(k\)-krát vyberieme z haldy najlacnejší prvok, vypíšeme ho, a pridáme \(2\) nasledujúcich kandidátov do haldy. Na to aby sme o kažom vrchole vedeli povedať, kam smerujú jeho hrany a vedeli vypísať jeho hodnotu, nám stačí si pamätať súčet jeho členov a najväčší prvok.

Riešenie ak je Emko hlúpy

Toto vieme upraviť na úlohu, ktorú sme už vyriešili. Stačí ak spustíme náš algoritmus na absolútnych hodnotách a odpočítali vždy súčet záporných čísel na vstupe. Prečo to funguje? Totiž ak sa rozhodneme neakú podmnožinu vypísať, tak vlastne sa rozhodneme vypísať túto podmnožinu s tým, že tam pridáme všetky záporné čísla okrem tých ktoré sme už vybrali (v absolútnej hodnote) a teda sa nám akoby vynulujú.

Prvýkrát, keď by sme mali vypísať nulový účet, ho na výstup nedáme (lebo neprázdny účet nás nezaujíma).

Čo sa týka časovej zložitosti, tak potrebujeme načítať vstup a v \(k\)-kolách vždy jeden prvok odstrániť a dva pridať do haldy, teda \(O(n + k \log k)\).

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.