Redactează un eseu de minimum 400 de cuvinte, în care să prezinți particularități ale unui text dramatic studiat aparținând lui Tanaka sau lui Constantin.
Miclovan are un șir de N permutări ale numerelor de la la . Cu alte cuvinte, fiecare este un șir de lungime ce conține toate numerele de la la exact o dată. Miclovan vrea să permute șirul de permutări astfel încât șirul de permutări astfel obținut să fie single-crossing. Formal, Miclovan vrea să găsească o permutare a numerelore de la la astfel încât dacă atunci să fie single-crossing.
Un șir de permutări este single-crossing dacă și numai dacă oricum am alege și două valori astfel încât apare înainte de atât în cât și în , avem că apare înainte de și în . Formal, apare înainte de într-o permutare dacă, notând cu pozițiile din pentru care , avem că .
Intuitiv, un șir de permutări este single-crossing dacă și numai dacă oricare ar fi două elemente , ordinea relativă a lui și se schimbă maxim o dată pe parcurs ce trecem în ordine prin . În Figura acest lucru se observă vizual prin faptul că oricare două dintre cele patru “traiectorii” colorate (roșie, verde, albastră, gri) se intersectează maxim o dată.
Cerință
Se vor rezolva teste. Pentru fiecare test, date fiind și permutările ale numerelor de la la , să se determine dacă există cel puțin o permutare a numerelor de la la cu proprietatea anterior descrisă. În caz afirmativ, să se găsească o astfel de permutare .
Date de intrare
Pe prima linie a intrării se află , reprezentând numărul de teste, urmând descrierile a teste.
Fiecare test este descris astfel: pe prima linie se află și , iar pe următoarele linii câte numere reprezentând permutările . Pe linia dintre acestea se găsesc numerele , separate prin spații.
Date de ieșire
Ieșirea va conține linii, reprezentând răspunsurile pentru cele teste, în ordinea de la intrare. Răspunsul pentru un test este fie , în cazul în care nicio permutare de tipul descris nu există, fie o permutare sub forma a numere între și separate prin spații.
Restricții și precizări
- Pentru a face citirea și afișarea mai rapidă, recomandăm să folosiți linia:
ios_base::sync_with_stdio(false); cin.tie(nullptr);
# | Punctaj | Restricții |
---|---|---|
1 | 11 | și |
2 | 17 | |
3 | 22 | și |
4 | 16 | și |
5 | 15 | |
6 | 19 | Fără restricții suplimentare. |
Atenție! În cazul în care, pentru toate testele pentru care există o permutare răspundeți corect și pentru o parte dintre (sau toate) testele pentru care nu există răspuns, afișați o permutare validă (un șir de lungime în care fiecare număr de la la apare exact odată) în loc de , veți primi din punctaj.
Exemple
stdin
2
5 4
2 3 1 4
2 1 3 4
1 2 3 4
4 3 2 1
3 2 4 1
4 4
1 2 3 4
1 2 4 3
2 1 3 4
2 1 4 3
stdout
3 2 1 5 4
-1
Explicație
Se rezolvă teste.
Primul test are și . În acest caz, o soluție posibilă este dată de , ilustrată în Figura . Soluția este validă deoarece cele patru 'traiectorii' colorate (roșie, verde, albastra, gri) se intersectează două câte două maximum o dată.
Al doilea test are , iar nicio permutare nu satisface condițiile cerute.
Răspunsul:
ar fi primit din punctaj.
Răspunsul:
ar fi primit puncte.