| Fişierul intrare/ieşire: | permutare5.in, permutare5.out | Sursă | ad-hoc |
| Autor | Bogdan Pop | Adăugată de |  descarc •arhive |
| Timp execuţie pe test | 2 sec | Limită de memorie | 512000 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Permutare5
Fie o permutare P de lungime N. Considerăm operaţia de interschimbare de valori aflate pe două poziţii consecutive.
Definim o permutare de lungime N ca fiind un şir care conţine toate numerele de la 0 la N - 1 exact odată. Fie o permutare P = (p0, p1, ..., pi, pi + 1, ..., pN - 1) şi un indice 0 ≤ i < N - 1. În urma interschimbării valorilor aflate pe poziţiile i şi i + 1 din P, permutarea P devine (p0, p1, ..., pi + 1, pi, ..., pN - 1).
Concurentul (adică tu) poate cumpăra astfel de interschimbări. Odată cumpărată, o interschimbare poate fi folosită de oricâte ori. Definim costul lui P ca fiind numărul minim de astfel de interschimbări ce trebuie cumpărate astfel încât permutarea să poată fi sortată folosind doar interschimbările cumpărate, fiecare de oricâte ori.
Comisia (adică noi) schimbă de Q ori permutarea P prin interschimbarea valorilor de pe două poziţii arbitrare, nu neapărat adiacente. Odată făcută o schimbare asupra permutării, ea rămâne valabilă în continuare.
Atât pentru permutarea iniţială, cât şi pentru permutarile obţinute după fiecare dintre schimbările comisiei, se cere costul lui P.
Date de intrare
Fişierul de intrare permutare5.in conţine, pe primul rând, numărul N de elemente a permutării vizate, şi numărul Q de operaţii.
Pe al doilea rând vor apărea cele N elemente a permutării P.
Urmează Q rânduri de forma a b, dintre care fiecare reprezintă o interschimbare a elementelor de pe poziţiile a şi b.
Date de ieşire
Fişierul de ieşire permutare5.out va conţine Q + 1 rândurile, conţinând costul permutării iniţiale, cât şi a tuturor permutărilor obţinute după fiecare dintre schimbările comisiei, în ordine.
Restricţii
- 2 ≤ N ≤ 100.000
- 1 ≤ Q ≤ 200.000
- Pentru 6 puncte, 1 ≤ N ≤ 1.000, 1 ≤ Q ≤ 10
- Pentru 13 puncte, 2 ≤ N ≤ 100.000, 1 ≤ Q ≤ 100
- Pentru 46 puncte, 2 ≤ N ≤ 50.000, 1 ≤ Q ≤ 50.000
- Pentru 22 puncte, 2 ≤ N ≤ 100.000, 1 ≤ Q ≤ 200.000 şi schimbările făcute de comisie interschimbă doar valori de pe poziţii adiacente. Mai exact, y = x + 1 pentru toate schimbarile comisiei.
Exemple
| permutare5.in | permutare5.out |
|---|---|
| 3 4 0 1 2 0 1 0 1 0 2 1 2 | 0 1 0 2 2 |
| 4 6 0 3 2 1 1 2 1 3 0 2 0 1 1 2 0 2 | 2 2 1 3 3 2 3 |
Explicaţie pentru primul exemplu:
În permutarea iniţială, (0, 1, 2), nu este nevoie de nicio interschimbare pentru a sorta permutarea.
În permutarea de după prima schimbare, (1, 0, 2), este nevoie de cumpărarea interschimbarii (0, 1).
Permutarea de după a doua schimbare este indentică cu cea iniţială.
Penultima permutare este (2, 0, 1) şi este nevoie de cumpărarea transpoziţiilor (0, 1) şi (1, 2).
Ultima permutare este (2, 1, 0), iar interschimbarile (0, 1) şi (1, 2) rămân ambele necesare *(chiar dacă sunt folosite de mai multe ori, fiecare este cumpărată doar o dată).
