| Fişierul intrare/ieşire: | curatenie.in, curatenie.out | Sursă | FMI No Stress 3 |
| Autor | Dragos Oprica | Adăugată de |  Dragos Oprica •DraStiK |
| Timp execuţie pe test | 0.375 sec | Limită de memorie | 36864 kbytes |
| Scorul tău | N/A | Dificultate |   1/5 |
Vezi solutiile trimise | Statistici
Curatenie
Vampirii din Twilight nu s-au mulţumit cu numărul imens de fani foarte înfocaţi. Asa ca au atacat membrii organizatori ai Balulului Bobocilor al Facultăţii de Matematică şi Informatică din Universitatea din Bucureşti. Transformarea a început cu un singur individ. Apoi acesta a transformat la rândul sau cel mult doi indivizi, deoarece fiecare vampir are doua transformări la dispoziţie, şi tot asa mai departe fiecare individ a transformat indivizi, pana când toţi membrii Asociaţiei Studenţilor la Matematica şi Informatica au devenit vampiri. Astfel, ii putem aşeza ca într-un arbore binar, unde rădăcina este primul individ transformat, fii unui nod sunt exact membrii pe care acesta ia transformat. Problema lor, a vampirilor, este ca au făcut mizerie prin aceste transformări. Şi trebuie sa facă curăţenie. Tot ce ştiu ei e ca au doua tipuri de-a face curăţenie, şi anume:
1) dacă este rândul lui X sa facă curăţenie, acesta îl pune pe primul transformat sa facă curăţenie, dacă exista, apoi face el curat, iar apoi îl va pune pe cel de-al doilea, dacă exista.
2) dacă este rândul lui X sa facă curăţenie, va face el curat, după care acesta îl pune pe primul transformat, dacă exista, sa facă curăţenie, iar apoi îl va pune pe cel de-al doilea, dacă exista.
Date cele doua ordini de a face curăţenie, voi trebuie sa aflaţi cine pe cine a transformat.
Date de intrare
Fişierul de intrare curatenie.in conţine pe prima linie N, numărul de membrii transformaţi, iar pe următoarele doua linii cele doua ordini: pe linia a doua se va afla cea de tipul 1, iar pe linia a treia se va afla cea de tipul 2.
Date de ieşire
În fişierul de ieşire curatenie.out se afla N linii, unde linia i conţine 2 numere, reprezentând cei doi indivizi transformaţi de membrul i. Daca unul din ei nu exista, se va afişa 0 pentru respectivul.
Restricţii şi precizari
- 1 ≤ N ≤ 500.000
- Numerele din fisierul de intrare sunt intre 1 si N.
- Atenţie la faptul ca un individ poate alege sa nu transforme pe nimeni, sau sa îşi folosească doar prima sau doar a doua transformare, contând ordinea.
Exemplu
| curatenie.in | curatenie.out |
|---|---|
| 4 1 4 2 3 3 1 2 4 | 0 2 4 0 1 0 0 0 |
| 7 4 2 5 1 3 7 6 1 2 4 5 3 6 7 | 2 3 4 5 0 6 0 0 0 0 7 0 0 0 |
