| Fişierul intrare/ieşire: | randomizare.in, randomizare.out | Sursă | Lot Alba Iulia 2010, Baraj 3 |
| Autor | Andrei Grigorean, Andrei Paul Puni, Cosmin Gheorghe | Adăugată de |  Dragos-Alin Rotaru •mathboy |
| Timp execuţie pe test | 0.25 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Randomizare
Qwerty se joacă foarte mult cu numere aleatoare. Recent şi-a combinat pasiunea pentru numere aleatoare cu pasiunea pentru permutări. Qwerty are un şir de numere distincte V şi o permutare P. El a început să aplice permutarea asupra şirului. Ar vrea să aplice permutarea de un număr infinit de ori asupra şirului, dar din cauză că lumea se va sfârşi în anul 2012 s-a gândit să-ţi ceară ajutorul ca să îşi satisfacă curiozitatea bolnavă.
Cerinţă
Qwerty te roagă să îi spui care este cel mai mic şir din punct de vedere lexicografic pe care îl poate obţine aplicând permutarea P asupra şirului V de un număr oarecare de ori şi în schimb îţi oferă 100 de puncte şi o şansă în plus pentru IOI.
Date de intrare
Fişierul de intrare randomizare.in conţine pe prima linie numărul natural N reprezentând lungimea permutării P şi a şirului V, pe a doua linie se vor afla N numere naturale distincte reprezentând elementele şirului V, iar pe a treia linie se vor afla N numere naturale distincte cuprinse între 1 şi N reprezentând elementele permutării P.
Date de ieşire
În fişierul de ieşire randomizare.out se vor afişa N numere naturale distincte reprezentând cel mai mic şir din punct de vedere lexicografic ce poate fi obţinut.
Restricţii
- 1 ≤ N ≤ 200 000
- Elementele şirului V pot fi memorate în variabile de tip intreg, pe 32 de biţi cu semn.
Exemplu
| randomizare.in | randomizare.out |
|---|---|
| 10 18 5 67 25 4 68 34 65 74 82 4 3 8 7 1 5 2 10 6 9 | 4 34 5 18 68 74 25 67 82 65 |
Explicaţie
Şirurile pe care le poate obţine Qwerty sunt:
1. 18 5 67 25 4 68 34 65 74 82
2. 25 67 65 34 18 4 5 82 68 74
3. 34 65 82 5 25 18 67 74 4 68
4. 5 82 74 67 34 25 65 68 18 4
5. 67 74 68 65 5 34 82 4 25 18
6. 65 68 4 82 67 5 74 18 34 25
7. 82 4 18 74 65 67 68 25 5 34
8. 74 18 25 68 82 65 4 34 67 5
9. 68 25 34 4 74 82 18 5 65 67
10. 4 34 5 18 68 74 25 67 82 65
