Koniec kola: 4. marec 2024 23:59
10 dní
Počet bodov:
Program:  100b

Táto úloha je programátorská. Ako svoje riešenie odovzdaj program vo svojom obľúbenom jazyku a automaticky sa dozvieš koľko si dostal/a bodov. Ak si takýto typ úloh ešte nikdy neriešil/a skús sa pozrieť ako by mal vyzerať ideálny program. Ak zaťiaľ programovať nevieš, ale chcel/a by si vedieť možeš skúsiť náš python tutoriál.

Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Kubovi na [email protected]

Jedného krásneho dňa sa Kodik vybral na tajomnú cestu Čínou. Cestoval už dlho a ďaleko, mal so sebou aj nejaké to jedlo, však poriadna panda musí pravidelne papkať. Cesta je však dlhšia ako očakával a už mu nezostáva veľa jedla. Našťastie je neďaleko bambusového hája, kde sa môže napapať. Tá horšia vec je, že odtiaľ musí pokračovať ďalej a nevie, či nájde po ceste ešte nejaké jedlo. Preto sa rozhodol, že si z bambusového hája vezme čo najviac bambusu. Nemá však veľké rozpätie rúk a preto by si chcel z kusok bambusu urobiť jednu, čo najvyššiu vežu. To ale nebude až tak jednoduché, keďže každý kus bambusu má iný tvar a teda aj inú nosnosť. Viete mu s tvorením takejto veže pomôcť?

Úloha

Máme \(n\) kusov bambusu. Každý kus má výšku \(1m\) a silu \(a_i\). Každý kus bambusu vie uniesť \(a_i\) metrov bambusu nad sebou. Ak by mal nad sebou viac ako \(a_i\) metrov bambusu, zlomil by sa. Kodik chce z týchto kusov bambusu vytvoriť čo najvyššiu vežu tak, že ich bude skladať na seba. Zároveň chceme, aby sa žiaden kus bambusu nezlomil.
Akú najvyššiu vežu vieme z týchto kusov bambusu postaviť?

Formát vstupu

Na prvom riadku je celé číslo \(n\) (\(1 \leq n \leq 750000\)) udávajúce počet kusov bambusu.
Na ďalšom riadku sa nachádza \(n\) celých čísel \(a_i\) (\(0 \leq a_i \leq 10^{8}\)), z ktorých \(i\)-te číslo udáva silu \(i\)-teho kusu bambusu.

Formát výstupu

Na prvý riadok výstupu vypíšte jedno celé číslo - najvyššiu vežu, ktorú vieme z týchto kusov bambusu postaviť.
Na nasledujúcom riadku vypíšte rad čísel \(i_1, i_2, \dots, i_k\) oddelených medzerami, označujúce indexy kusov bambusu (z pôvodného poradia), ktoré sú súčasťou najvyššej veže od spodu po vrch.

Ak je riešení viacero, vypíšte ľubovoľné z nich.

Hodnotenie a obmedzenia

Existujú 4 sady vstupov, za každú z nich môžete získať 25 bodov. Platia v nich nasledovné obmedzenia:

Sada 1. 2. 3. 4.
\(1 \leq n \leq\) \(100\) \(15000\) \(200000\) \(300000\)
\(0 \leq a_i \leq\) \(100\) \(10000\) \(10^7\) \(10^8\)

Príklady

Input:

5
3 2 0 2 3

Output:

4
0 4 1 3

Ďalšie správne riešenie by mohlo byť napríklad 4 0 1 3.

Input:

3
1 2 0

Output:

3
1 0 2

Iné riešenie neexistuje.

Odovzdávanie

Na odovzdávanie sa musíš prihlásiť

Otázky a diskusia

Po skončení kola budete mať príležitosť na diskutovanie o riešeniach v diskusii pod vzorovým riešením.