Problem 269: Islands

Istvan a mers in excursie în insula Modnarcaskurr, și a început să se uite la dansul floriilor. Dansul floriilor funcționează în felul următor. Sunt N dansatoare (numerotate de la 0 la N − 1) și N flori. La început, dansatoarea numărul i ia floarea cu numărul p[i], unde p este o permutare (această permutare este un secret al culturii insulei). Apoi, dansatoarele se grupează în k grupe, $A_1, ..., A_k$ . Fiecare dintre cele N dansatoare se încadrează în exact o grupă. În timpul dansului, dansatoarele din cadrul unei grupe se amestecă, iar la fel și grupele între ele, dar NU se pot modifica grupele. După dans, dansatoarele din fiecare grupă își aruncă florile în aer, și putem să vedem cum sunt grupate florile: în grupele $B_1, ..., B_k$ , unde oricare $B_i$ reprezintă florile asociate unei grupe de dansatoare (nu neapărat grupa $A_i$ ).

Istvan se duce apoi la oracolul insulei, care îl lasă să pună mai multe întrebări de forma $A_1, ..., A_k$ , unde răspunsul la o interogare este $B_1, ..., B_k$ . Oracolul îl întreabă acum: “Poți afla permutarea p?”.

Formal, există o permutare ascunsă p a numerelor de la 0 la N − 1, și se pot face interogări de forma $A_1, ..., A_k$ , unde $A_1, ..., A_k$ este o partiție a lui {0, ..., N − 1}. Răspunsul la o interogare este o partiție $B_1, ..., B_k$ a lui {0, . . . , N − 1}, unde pentru fiecare $A_i$ există exact un $B_j$ astfel încât $k ∈ A_i$ dacă și numai dacă $p[k] ∈ B_j$ . Se cere să se afle p.

Protocol de interacțiune

Concurentul trebuie să implementeze o funcție:

std::vector<int> solve (int N);

Parametrul N reprezintă lungimea permutării. Funcția va întoarce un vector de lungime N, reprezentând permutarea găsită de concurent. Concurentul trebuie să nu implementeze funcția main. Funcția va fi apelată doar o singură dată la o rulare.

Concurentul poate apela următoarea funcție pentru o interogare:

std::vector<std::vector<int>> ask (const std::vector<std::vector<int>> &partition);

Parametrul partition reprezintă partiția pentru care este dată interogarea (A de mai sus din enunț).
Fiecare vector din acest vector de vectori reprezintă una dintre mulțimile ce alcătuiesc partitția. Evident, atât ordinea elementelor din vectorul de vectori partition cât și ordinea vectorilor ce îl alcătuiesc sunt irelevante (căci reprezintă mulțimi). Răspunsul este partiția B descrisă în enunț, reprezentată ca un vector de vectori, la fel ca A.

Restricții și precizări

3 ≤ N ≤ 10 000
Q reprezintă numărul maxim de interogări pentru a obține scor maxim pe test.
optimal reprezintă numărul minim de interogări pentru a afla permutarea ascunsă.
Scorul pe un subtask este scorul minim obținut pe un test din subtask.
maxC reprezintă cardinalul maxim al oricărei partiții astfel încât să se obțină scor nenul pe test.
Concurentul are dreptul la maxim 20 000 de interogări pentru un test.
Trebuie să includeți islands.h

Subtask 1 (11 puncte)

N = 15
Q = 15
maxC = N

Subtask 2 (15 puncte)

N = 4997
Q = optimal + 15
maxC = N

Subtask 3 (15 puncte)

N = 5000
Q = optimal + 15
maxC = N

Subtask 4 (17 puncte)

N = 5010
Q = optimal + 5
maxC = N

Subtask 5 (16 puncte)

$3 ≤ N ≤ 10^4$
Q = optimal
maxC = N

Subtask 6 (9 puncte)

N = 8778
Q = optimal
maxC = 500

Subtask 7 (8 puncte)

N = 9889
Q = optimal
maxC = 500

Subtask 8 (9 puncte)

$3 ≤ N ≤ 10^4$
Q = optimal
maxC = 500

Punctare

Scorul este calculat în următorul fel, depinzând de numărul de interogrări ale concurentului (contestantQ) și cardinalul maxim al unei partiții (contestantC):

$score = \left\{ \begin{array}{ll} 0.6^{max(contestantQ−Q,0)} \cdot maxScore & \text{dacă contestantC ≤ maxC} \\ 0 & \text{altfel} \end{array} \right.$

Exemplu

Comisia
p = (0, 2, 1)
se apelează solve(3)

Concurent
ask({{0, 1, 2}}) = {{0, 1, 2}}
ask({{0}, {1, 2}}) = {{0}, {1, 2}}
ask({{1}, {0, 2}}) = {{2}, {0, 1}}
ask({{2}, {0, 1}}) = {{1}, {0, 2}}
ask({{0}, {1}, {2}}) = {{0}, {1}, {2}}
solve returnează (0, 2, 1).

Explicație

Observați că pentru ask({{0, 1, 2}}) orice permutare este un răspuns valid. De asemenea, pentru ask({{1}, {0, 2}}), oricare răspuns dintre {{2}, {0, 1}}, {{2}, {1, 0}}, {{1, 0}, {2}}, {{0, 1}, {2}} este corect.

Islands