Revizia anterioară Revizia următoare
| 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 sau, 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 că un proces recursiv ce începe dintr-o camera x, o vizitează, iar apoi recursiv se deplaseaza catre 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 celelalt, 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
În 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 ≤ Ai, Bi ≤ N, pentru orice i care respecta 1 ≤ i ≤ N
- Ai ≠ Aj si Bi ≠ Bj, pentru orice i si j care respecta 1 ≤ i < j ≤ N
- Atentie: in ziua i, biroul numarul i este considerat sa fie vizitat o singura data (deci cei doi prieteni se vor vedea in acel birou maxim o singura data).
Subtaskuri
- Subtask Asta ca nu au reusit - 5 puncte: n ≤ 500
- Subtask Nu ca nu au incercat - 6 puncte: n ≤ 2 000
- Subtask Legile lui Kirchhoff - 5 puncte: In fiecare zi, Juju si Netasu viziteaza maxim 100 de birouri
- Subtask Nu-mi pasa-- Si daca se face ora 2 noi tot cautam aia - 21 puncte: In fiecare zi, Juju si Netasu viziteaza toate cele N birouri
- Subtask Chestii random, cum ar fi ca o retea de sortare sorteaza corect orice sir doar daca poate sorta toate sirurile de 0/1-uri - 37 puncte: n ≤ 100 000
- Subtask ...Sa dormi nestiind daca te vei trezi cu un cutit in spate ( ◜‿◝ ) - 36 puncte: Fără restricţii suplimentare
Exemplu
| permdist.in | permdist.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
