Fişierul intrare/ieşire:	turneu2.in, turneu2.out	Sursă	Lot Seniori Campulung 2018, baraj 3
Autor		Adăugată de	Tamio Vesa Nakajima •tamionv
Timp execuţie pe test	0.5 sec	Limită de memorie	32000 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Turneu2

Se consideră un număr întreg pozitiv K şi N = 2^K. La un turneu participă N concurenţi numerotaţi de la 0 la N-1. Pentru fiecare concurent i este cunoscută puterea acestuia p[i]. Puterile sunt numere întregi pozitive distincte şi strict mai mici decât N. Cu alte cuvinte şirul p[] este o permutare a numerelor întregi de la 0 la N-1. Un meci între doi concurenţi este câştigat de jucătorul care are putere mai mare.
În primul tur al turneului se desfăşoară meciuri după cum urmează: primul meci este între concurenţii 0 şi 1, al doilea meci între concurenţii 2 şi 3 , ş.a.m.d , al m-lea meci este între concurenţii 2m-2 şi 2m-1. Ultimul meci din primul tur va fi între jucătorii N-2 şi N-1.
Începând cu al doilea tur meciurile se vor desfăşura astfel: primul meci va fi între câştigătorii din primele două meciuri din turul anterior, al doilea meci între câştigătorii următoarelor două meciuri, ş.a.m.d. astfel că ultimul meci va fi între câştigătorii ultimelor două meciuri din turul anterior. Turneul va continua până va fi desemnat câştigătorul turneului.
Să ne imaginăm următorul scenariu: sunteţi concurentul cu puterea x şi aţi vrea să câştigaţi cât mai multe meciuri în turneu. Pentru a atinge acest scop aveţi dreptul să faceţi un număr de cel mult y intershimbări între participanţii la turneu. La o interschimbare poziţiile celor doi jucători în tabloul iniţial al meciurilor din primul tur se schimbă între ele. După efectuarea a cel mult y interschimbări turneul începe şi se supune regulilor descrise mai sus, dar datorită modificărilor este posibil ca la unele dintre meciuri câştigătorii să fie diferiţi.

Date de intrare

În primul rând al fişierului de intrare turneu2.in va apărea N.
Pe al doilea rând al fişierului de intrare vor apărea valorile şirului p.
Pe al treilea rând al fişierului de intrare va apărea Q, numărul de scenarii ce vor apărea in fişier.
În următoarele Q rânduri ale fişierului de intrare va apărea o pereche de numere p q, dintre care fiecare reprezintă câte un scenariu de test. Dacă v este răspunsul pentru scenariul precedent (sau 0 dacă este vorba de primul scenariu), atunci în acest scenariu de test x = p xor v şi y = q xor v.

Date de ieşire

Fişierul de ieşire turneu2.out va conţine răspunsurile pentru cele Q scenarii, în ordinea în care sunt date, câte unul pe un rând.

Restricţii si precizări

• ATENŢIE! Un jucător poate fi schimbat cu oricare alt jucător – inclusiv jucătorul cu puterea x.
• 2 ≤ K ≤ 20
• 0 ≤ x, y ≤ N-1
• Q ≤ 500 000
• Pentru 15 puncte K ≤ 10, Q ≤ 1000
• Pentru alte 20 de puncte K ≤ 17, valorile x ale interogărilor sunt date în ordine crescătoare
• Pentru alte 10 puncte K = 18
• Pentru alte 10 puncte K = 19
• Pentru restul de 45 de puncte K = 20
• Atenţie la limita de memorie!

Exemplu

Explicaţie

În primul exemplu, valorile pe care le ia (x, y) în diferetele scenarii sunt (1, 0), (0, 2), (3, 1), (2, 2).
În cel de-al doilea exemplu, valorile pe care le ia (x, y) în diferetele scenarii sunt (3, 1), (3, 0), (1, 5), (4, 7), (7, 7)

Cum se trimit solutii?