Fişierul intrare/ieşire:randomizare.in, randomizare.outSursăLot Alba Iulia 2010, Baraj 3
AutorAndrei Grigorean, Andrei Paul Puni, Cosmin GheorgheAdăugată demathboyDragos-Alin Rotaru mathboy
Timp execuţie pe test0.5 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/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.inrandomizare.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

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content