Problem 1932: turneu

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 $2 \cdot m-2$ şi $2 \cdot m-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.

Cerință

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.

În această problemă va trebui să implementaţi două funcţii.

void init (int N, int *p)

Această funcţie va fi apelată de graderul comisiei o singură dată. Acest apel va trimite prin intermediul parametrului $N$ valoarea cu semnificaţia din enunţ iar prin intermediul parametrului $p$ adresa de început a unui vector de numere întregi conţinând puterile celor $N$ concurenţi.

int query (int x, int y)

Această funcţie va fi apelată de mai multe ori în graderul comisiei după unicul apel al funcţiei init. Funcţia va trebui să rezolve un scenariu de tipul celui descris mai sus. Prin intermediul parametrului $x$ funcţia primeşte puterea unui concurent şi prin intermediul parametrului $y$ un număr maxim de interschimbări permise şi trebuie să returneze numărul maxim de meciuri pe care l-ar putea câştiga jucătorul cu puterea $x$ dacă face într-un mod convenabil cel mult $y$ interschimbări în tabloul iniţial.

ATENŢIE: Un jucător poate fi schimbat cu oricare alt jucător – inclusiv jucătorul cu puterea $x$ .

Restricții și precizări

$2 \leq K \leq 20$
$0 \leq x, y \leq N-1$ pentru fiecare apel al funcţiei query
funcţia query va fi apelată de graderul comisiei de cel mult $5\times 10^5$ ori.
Pentru $15$ puncte $K \leq 10$ , numărul apelurilor a functiei query $\leq 1 \ 000$
Pentru alte $20$ de puncte $K \leq 17$ , valorile $x$ ale query-urilor 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$
Pointerul primit în funcția init poate fi folosit în orice fel (inclusiv modificată memoria)

Exemplu

Actiune grader

init( 4,{3,2,0,1}) 
query (1,0)
query (0,2)
query (3,1)
query (2,2)

Efect

Explicatie

La turneu participă $4$ jucători: Jucătorul $0$ are putere $3$ , Jucătorul $1$ are putere $2$ , Jucătorul $2$ are putere $0$ , Jucătorul $3$ are putere $1$ .

Pentru primul query, nu este permisă nicio interschimbare. În primul tur jucătorul cu puterea $1$ câştigă meciul împotriva jucătorului cu puterea $0$ . În al doilea tur jucătorul cu puterea $1$ pierde în faţa jucătorului cu puterea $3$ .

Pentru cel de-al doilea query, sunt permise $2$ interschimbări. Indiferent de numărul de interschimbări efectuate jucătorul cu puterea $0$ va pierde din primul tur deoarece are cea mai mică putere din tot turneul.

Pentru cel de-al treilea query, o singură interschimbare este permisă. Indiferent de numărul de interschimbări jucătorul cu puterea $3$ va câştiga orice meci deoarece are cea mai mare putere. Astfel după ce câştigă primul meci cu unul dintre adversari, va câştiga meciul cu câştigătorul meciului dintre ceilalţi doi devenind astfel şi câştigătorul turneului.

Exemplul 2