Underrated

Cerință

La concursul Stelele Informaticii există $N$ participanți, numerotați $0, 1, \ldots, N - 1$.

$\\[0.25cm]$

După concurs, participanții sunt clasați conform unei permutări secrete $P$ a numerelor $0, 1, \ldots, N - 1$, unde $P[i]$ reprezintă poziția participantului $i$ în clasamentul secret. Poziția $0$ corespunde primului loc. Álec Sdima cunoaște clasamentul secret, dar tu nu îl cunoști.

$\\[0.25cm]$

Poți propune un clasament $Q$, care trebuie să fie o permutare a numerelor $0, 1, \ldots, N - 1$, unde $Q[i]$ reprezintă poziția pe care o atribui participantului $i$. Se numește underrating-ul participantului $i$, în clasamentul propus, valoarea $Q[i] - P[i]$.

$\\[0.25cm]$

După ce vede clasamentul propus de tine, Álec îți comunică valoarea maximă a underrating-ului tuturor participanților, definită astfel:

Trebuie să determini clasamentul secret $P$ folosind cât mai puține propuneri.

Interacțiune

Programul nu va citi date de la intrare și nu va afișa nimic. Concurentul trebuie să implementeze funcția:

std::vector<int> find_ranking(int N)

• $N$: numărul de participanți.
• Funcția trebuie să returneze clasamentul secret $P$.
• Funcția este apelată o singură dată pentru fiecare test case.
• Funcția find_ranking() poate apela următoarea funcție:

int ask(std::vector<int> Q)

• $Q$ trebuie să fie o permutare a numerelor $0, 1, \ldots, N - 1$.
• $Q[i]$ reprezintă poziția atribuită participantului $i$.
• Funcția returnează valoarea:

• Această funcție poate fi apelată de cel mult $20,000$ de ori în fiecare test case.

Comportamentul grader-ului este $\bold{adaptiv}$. Aceasta înseamnă că grader-ul nu folosește o permutare fixă $P$. În schimb, valorile returnate de funcția ask depind de apelurile anterioare ale acesteia.

$\\[0.25cm]$

Se garantează că grader-ul răspunde astfel încât, după fiecare apel, să existe cel puțin o permutare $P$ compatibilă cu toate răspunsurile oferite până în acel moment.

Restricții

• $1 \leq N \leq 1000$
• $P$ este o permutare a numerelor $0, 1, \ldots, N - 1$.

Precizări

• Dacă, în oricare dintre test case-uri, funcția ask este apelată cu un argument care nu respectă regulile precizate mai sus sau permutarea returnată de find_ranking este incorectă, punctajul obținut pentru acel test case va fi $0$.
• Fie $Q$ numărul maxim de apeluri ale funcției ask efectuate într-un test case. Definim, de asemenea, valoarea $X$ astfel:

Punctajul se calculează după cum urmează:

În particular, pentru a obține 100 de puncte, soluția ta trebuie să efectueze cel mult $1 \ 997$ de apeluri ale funcției ask în fiecare test case. Punctajul fiecărui subtask este rotunjit la două zecimale.

Exemplu

Să presupunem că $N = 4$, iar clasamentul secret este $P = [2, 0, 3, 1]$. Aceasta înseamnă că participantul $1$ ocupă primul loc, participantul $3$ ocupă locul al doilea, participantul $0$ ocupă locul al treilea, iar participantul $2$ ocupă locul al patrulea.

$\\[0.25cm]$

Să considerăm următorul apel:

ask({0, 1, 2, 3})

Pentru acest clasament, valorile $Q[i] - P[i]$ sunt $[-2, 1, -1, 2]$. Prin urmare, valoarea maximă a underrating-ului este $2$, iar funcția returnează $2$.

$\\[0.25cm]$

Să considerăm acum următorul apel:

ask({3, 0, 2, 1})

Valorile $Q[i] - P[i]$ sunt $[1, 0, -1, 0]$. Prin urmare, funcția returnează $1$.

$\\[0.25cm]$

În cele din urmă, dacă clasamentul propus coincide cu cel secret,

ask({2, 0, 3, 1})

toate valorile $Q[i] - P[i]$ sunt $0$, astfel că funcția returnează $0$.

Sample grader

Sample grader-ul este $\bold{neadaptiv}$. Clasamentul secret $P$ este fixat înainte de apelarea funcției find_ranking.

$\\[0.25cm]$

Sample grader-ul citește datele de intrare în următorul format:

Linia 1: $N$

$\\[0.25cm]$

Linia 2: $P[0] \ P[1] \ \ldots \ P[N - 1]$

$\\[0.25cm]$

Pentru fiecare apel al funcției ask(Q), sample grader-ul returnează valoarea:

Sample grader-ul afișează datele de ieșire în următorul format:

• Linia 1: $C$
• Linia 2: $R[0] \ R[1] \ \ldots \ R[N - 1]$

Aici $C$ reprezintă numărul de apeluri ale funcției ask, iar $R$ este permutarea returnată de find_ranking.