Zadanie

Na poslednej chate vedúcich Trojstenu vznikol nápad, že by Trojstenáci mohli spolu chodievať do divadla aby si utužili kolektív, získali inšpiráciu na dej sústredenia, naučili sa hereckému majstrovstvu na hranie dejových scénok… Vtedy ti to prišlo ako dobrý nápad, však čo sa môže takým divadlom pokaziť. Veď to si tam proste sadneš, a pozeráš sa. To nemôže byť také zlé… Jedine, ak by bolo. Kvôli tragickým hereckým výkonom si po prvých piatich minútach predstavenia začal ľutovať, že si radšej neostal na intráku robiť domáce úlohy. Po desiatich ti už aj umývať špinavé riady v T2 príde ako dobrý nápad. Po 15tich minútach sa postavíš, aby si odišiel, ale čo sa to deje? Naľavo aj napravo od teba sedia vedúci, a je neslušné ich prekračovať kým sedia. Našťastie, nie si jediný, ktorému to predstavenie príde zlé, a chce odísť… V akom poradí odídu všetci Trojstenáci zo sály?

Úloha

V divadle sedí v jednom rade \(n\) vedúcich. Pre jednoduchosť si ich označme prirodzenými číslami \(1\) až \(n\). Každého z nich po nejakom čase prestane baviť sa pozerať na divadlo, a bude chcieť odísť. Odísť ale môže len vtedy, ak naľavo, alebo napravo od neho nikto nesedí. Viete poradie, v akom sedia vedúci v rade, a viete poradie, v akom ich prestane baviť sa pozerať na divadlo. Vypíšte poradie, v akom odídu zo sály.

Formát vstupu

Na prvom riadku sa nachádza číslo \(n\), (\(1\leq n \leq 100\,000)\): počet vedúcich, ktorí sedia v rade. Na druhom riadku sa nachádza \(n\) medzerou oddelených čísel \(s_i\), ktoré označujú vedúcich v poradí v akom sedia v rade. Prvé a posledné číslo predstavujú vedúcich, ktorí sedia na kraji. Na poslednom riadku dostanete \(n\) medzerou oddelených čísel \(p_i\), ktoré znamenajú poradie, v akom vedúcich prestalo baviť pozerať divadlo.

Formát výstupu

Vypíšte jeden riadok s \(n\) medzerou oddelenými číslami, poradie v akom vedúci odídu zo sály. Za posledným číslom medzeru nevypisujte. Nezabudnite na znak konca riadku.

Príklad

Input:

3
3 1 2
1 3 2

Output:

3 1 2

Najprv prestane divadlo baviť vedúceho \(1\), ktorý ale nemôže odísť. Potom, ako prestane divadlo baviť vedúceho \(3\), ktorý sedí na kraji, už má aj vedúci \(1\) voľnú cestu zo sály, a odíde aj ten. Nakoniec prestane divadlo baviť vedúceho \(2\), ktorý okamžite odíde.

Input:

5
1 2 3 4 5
1 5 2 4 3

Output:

1 5 2 4 3

Pomalá simulácia

Prvá vec, ktorú si môžeme všimnúť je, že človek, ktorý je na kraji môže odísť. Skúsme teda postupne simulovať všetkých ľudí, ktorí budú chcieť odísť z divadla. Pre každého človeka, si pamätáme, že či ešte ostáva alebo chce odísť alebo už odišiel. Vieme to urobiť napríklad pomocou poľa, v ktorom každý index znamená jedného človeka. Ak v poli na danom indexe je \(0\), tak človek ešte nechce odísť, ak je tam \(1\), tak človek chce odísť, ale nemôže, a ak je tam \(2\), tak už odišiel.

Teraz môžeme postupne prejsť ľudí, v poradí v ktorom chcú odísť. Vždy keď niekto chce odísť, prepíšeme mu \(0\) na \(1\), prejdeme všetkých ľudí (celé pole), a skontrolujeme či tento človek môže odísť. Teda či na všetkých menších alebo na všetkých väčších indexoch je \(2\). Ak môže odísť, tak si k nemu poznačíme že odišiel a následne zmeníme všetkých ľudí, ktorí vďaka tomu, že odišiel tento človek, môžu odísť tiež. (Môžete si všimnúť, že keď človek odchádza doľava, uvoľní sa cesta človeku vpravo od neho.)

Avšak, problém tohoto riešenia je, že pre každého človeka v poradí v akom chce odísť musíme prejsť všetkých ostatných ľudí, teda časová zložitosť je \(O(n^2)\).

Lineárne riešenie

Lepšie riešenie je, ak by sme si pamätali, že kde na oboch stranách sedí najkrajnejší človek (ako takú zarážku). Úsek sediacich bude totiž vždy súvislí, keďže zo stredu nemôže odísť nikto. Ďalej si budeme pamätať ku každému človeku, že či už chce odísť alebo nie; podobne ako v pomalom riešení. Keď nejaký človek začne chcieť odísť (slovenčina je krásna ;) ), tak si k nemu poznačíme, že chce odísť a skontrolujeme či sa jedna z týchto “zarážok” vďaka tomu už dá posunúť.

Časová a pamäťová zložitosť

Toto riešenie na prvý pohľad nevyzerá o nič lepšie, ak sa na to nepozrieme takto: Keď je človek na rade, tak si v konštantnom čase poznačíme, že už chce odísť, a následne nejako posunieme zarážku. Obe zarážky dokopy ale určite neposunieme viac ako \(n\)-krát a ľudí je tiež práve \(n\). Naša časová zložitosť je teda \(O(n)\) času poznačiť si všetkých ľudí, a k tomu tiež spolu \(O(n)\) posunutí zarážky. Časová zložitosť je teda \(O(n)\).

Čo sa týka pamäťovej zložitosti, potrebujeme si pamätať len niekoľko polí dĺžky \(n\): poradie v akom sedia ľudia, poradie v akom chcú odísť a to či už chcú odísť alebo nie. Pamäťová zložitosť je teda tiež \(O(n)\).

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ť.