Fişierul intrare/ieşire:	ghemotoace.in, ghemotoace.out	Sursă	InfoPro, Etapa 3, Grupa B
Autor	Alexandru Petrescu	Adăugată de	Mihai-Cristian Popescu •mihai50000
Timp execuţie pe test	0.115 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Ghemotoace

Alex a cumpărat pentru pisica sa n ghemotoace de culori diferite. În fiecare zi i din următoarele t, pisica va alege q_i perechi de ghemotoace adiacente cu care să se joace şi va interschimba poziţiile gheotoacelor din fiecare pereche. Alex ştie culorile ghemotoacelor care au fost interschimbate, dar nu şi ordinea în care s-au realizat interschimbările. Astfel el vă cere să găsiţi ordinea în care se află ghemotoacele în fiecare zi.

Culorile sunt codificate prin numere naturale de la 1 la n. Iniţial, ghemotoacele sunt sortate crescător după acest indice al culorii.

Răspunsul pentru fiecare zi va fi dat sub forma unui cod reţinut într-o variabilă de tip unsigned long long şi obţinut din următoarea formulă: , unde v[i] înseamnă culoarea ghemotocului de pe poziţia i.

Date de intrare

Fişierul de intrare ghemotoace.in conţine pe prima linie numerele n şi t. Pe următoarele linii se află descrierea fiecărui test astfel: pe următoarea linie se găseşte q_i urmat de q_i linii care conţin câte două numere ce descriu culorile ghemotoacelor care sunt interschimbate.

Date de ieşire

În fişierul de ieşire ghemotoace.out se vor afla t numere, câte unul pe fiecare linie. Pe linia i se va găsi răspunsul pentru ziua i.

Notă

Între ataşamente, puteţi găsi fişierul manager.cpp pe care îl puteţi descărca. E recomandat, atât pentru a scrie o sursa eficientă şi elegantă, cât şi pentru a simula experienţa problemei din timpul concursului, să completaţi această sursă cu implementarea funcţiilor init() si makeSwaps().

Restricţii

• Orice pereche (neordonată) de culori apare cel mult o singură dată în cadrul unei zile. Pentru orice pereche (a, b) se garantează că a != b, iar ordinea în care sunt date culorile în pereche este aleatorie.
• Punctarea se va face separat, testele fiind independente unul de altul. Punctajele pe subtaskuri diferă de cele din concurs.
• Primul test ( nrTestCase = 1 ) are proprietatea ca perechile sunt date în ordinea în care s-au efectuat interschimbările
• Următoarele 2 teste respectă următoarele restricţii: 1 ≤ n ≤ 20.000 şi t = 1
• Următoarele 3 teste respectă următoarele restricţii: 1 ≤ n, t, q_i ≤ 50
• Următoarele 4 teste respectă următoarele restricţii: 1 ≤ n, t ≤ 20.000
• pentru toate testele

Exemplu

Explicaţie

N = 4
nrTestCase = 2
t = 2

Pentru prima zi:

[1, 2, 3, 4] -> [2, 1, 3, 4] -> [2, 3, 1, 4]

Observaţi că secvenţa [1, 2, 3, 4] -> [3, 1, 2, 4] -> [3, 2, 1, 4] este greşită deoarece elementele 1 şi 3 nu sunt adiacente când sunt interschimbate.

25948 = 23³ * 3 + 23² * 3 + 23¹ * 1 + 23⁰ * 4

Pentru a doua zi:

[2, 3, 1, 4] -> [2, 3, 4, 1] -> [2, 4, 3, 1] -> [4, 2, 3, 1] -> [4, 3, 2, 1]

50302 = 23³ * 4 + 23² * 3 + 23¹ * 2 + 23⁰ * 1

Cum se trimit solutii?