Fişierul intrare/ieşire:	permdist.in, permdist.out	Sursă	Junior Challenge 2023
Autor	Voicu Mihai Valeriu	Adăugată de	Voicu Mihai Valeriu •cadmium_
Timp execuţie pe test	1 sec	Limită de memorie	524288 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Permdist

Juju e o ţestoasă veselă de când lucrează la Centrul de Organizare a Misiunilor Externe. Cea mai veselă parte din ziua lui este când se întâlneşte cu patronul său, Netaşu. Aceştia au efectiv aceeaşi slujba, anume a supravegherii celorlaltor angajaţi.

Centrul poate fi descris prin N birouri diferite, fiecare având câte o misiune diferită. Un sistem de supraveghere peste aceste birouri poate fi descris ca o permutare de N numere, T. Definim o supraveghere ca un proces recursiv ce începe dintr-o cameră x, o vizitează, iar apoi recursiv se deplasează către camera T[x] (luându-i o secundă), până când se ajunge într-o camera care a fost vizitată deja. Când asta se întâmplă, supravegherea se opreşte.

Cei doi angajaţi şi-au dezvoltat fiecare câte un sistem diferit de supraveghere, anume pentru Juju acesta este A, iar pentru Netaşu acesta este B. Contractul lor este pe N zile, în a i-a din această ei vor fi nevoiţi să înceapă o supraveghere din biroul i. Cum ei sunt foarte fericiţi să se întâlnească unul pe celălalt, aceştia vor să ştie de câte ori vor fi în a i-a zi în acelaşi birou în acelaşi timp.

Date de intrare

Fişierul de intrare permdist.în va conţine pe prima linie N, numărul de birouri. Pe al doilea rând se vor afla N numere ce compun permutarea A. Pe al doilea rând se vor afla N numere ce compun permutarea B. 

Date de ieşire

Fişierul de ieşire permdist.out va conţine N numere, al i-lea fiind de câte ori se vor vedea cei doi prieteni în ziua i.

Restricţii

• 1 ≤ N ≤ 1 000 000
• 1 ≤ A_i, B_i ≤ N, pentru orice i care respectă 1 ≤ i ≤ N
• A_i ≠ A_j şi B_i ≠ B_j, pentru orice i şi j care respectă 1 ≤ i < j ≤ N
• Atenţie: în ziua i, biroul numărul i este considerat să fie vizitat o singură dată (deci cei doi prieteni se vor vedea în acel birou maxim o singură dată).
• În lumea celor doi prieteni, zilele au un număr suficient de mare de secunde.

Subtaskuri

• Subtask Asta că nu au reuşit - 4 puncte (testele 1-4): n ≤ 500
• Subtask Nu că nu au încercat - 6 puncte (testele 5-7): n ≤ 2 000
• Subtask Le ştie aşa cu numele că n-a prea înotat - 10 puncte (testele 8-10): n ≤ 100 000. În plus, în fiecare zi, Juju şi Netaşu vizitează maximum 100 de birouri
• Subtask Nu-mi pasă-- Si daca se face ora 2 noi tot căutăm aia - 16 puncte (testele 11-13): n ≤ 100 000. În plus, în fiecare zi, Juju şi Netaşu vizitează toate cele N birouri
• Subtask Dormi neştiind dacă te vei trezi cu un cuţit în spate ( ◜‿◝ ) - 37 puncte (testele 14-19): n ≤ 100 000
• Subtask Chestii random, cum ar fi că o reţea de sortare sortează corect orice şir doar dacă poate sorta toate sirurile de 0/1-uri - 27 puncte (testele 20-30): Fără restricţii suplimentare

Exemplu

Explicaţie

În ziua 1:

• Juju vizitează pe rând: 1 3 2 5
• Netaşu vizitează pe rând: 1 5 2 3

Ei se văd unul pe celălalt în prima şi a treia secundă.

Cum se trimit solutii?