Security

Cerință

Există $N$ obiecte numerotate $0, 1, \ldots, N - 1$ și $M$ porți de securitate numerotate $0, 1, \ldots, M - 1$. Fiecare poartă de securitate $i$ are asociată o submulțime secretă de obiecte $A[i]$.

$\\[0.25cm]$

Poți trimite un pachet $P$ format dintr-o submulțime nevidă a celor $N$ obiecte. Pachetul trece prin porțile de securitate în ordine crescătoare. Poarta de securitate $i$ confiscă pachetul dacă $|A[i] \cap P|$ este impar. Pachetul este oprit la prima poartă, care îl confiscă. După trimiterea pachetului sunteți anunțați despre indexul porții de securitate care l-a oprit.

$\\[0.25cm]$

Se garantează că fiecare pachet nevid este confiscat de una din porțile de securitate.

$\\[0.25cm]$

O poartă de securitate este numită $\bold{utilă}$ dacă există un pachet pentru care această poartă este prima care îl confiscă. Se poate demonstra că există exact $N$ useful security gates. Fie indicii acestora, în ordine crescătoare:

Misiunea ta este să trimiți pachetele astfel încât pentru orice $0 \leq i < N$, poarta de securitate $c[i]$ confiscă exact $N - i$ dintre pachetele trimise.

$\\[0.25cm]$

Poți alege fiecare pachet pe baza răspunsurilor obținute pentru pachetele trimise anterior.

Interacțiune

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

void solve(int N, int M)

• $N$: numărul de obiecte.
• $M$: numărul de porți de securitate.
• Această funcție este apelată exact o singură dată pentru fiecare testcase.

Funcția solve() poate apela următoarea funcție:

int send_package(std::vector<int> P)

• $P$ trebuie să conțină indicii unei submulțimi nevid de obiecte.
• Procedura returnează indicele primei porți de securitate care confiscă $P$.
• Fiecare obiect poate apărea cel mult o singură dată în $P$.

Modelul graderului $\bold{este \ neadaptiv}$. Aceasta înseamnă că mulțimile $A[0], A[1], \ldots, A[M - 1]$ sunt fixate înainte de apelul solve.

Exemplu

Presupunem că $N = 3$ și $M = 4$, iar submulțimile secrete sunt:

• $A[0] = \{0, 1\}$
• $A[1] = \{0, 1\}$
• $A[2] = \{1, 2\}$
• $A[3] = \{2\}$

În acest caz, porțile de securitate utile sunt $0, 2,$ și $3$. Poarta 1 nu este utilă, deoarece orice pachet, pe care îl poate confisca aceasta, a fost deja confiscat de poarta $0$.

$\\[0.25cm]$

O posiblă secvență de apeluri pentru send_package este:

De exemplu, pachetul $\{0, 1, 2\}$ trece prin porțile $0, 1,$ și $2,$ deoarece intersecția lui cu fiecare dintre submulțimile lor are o dimensiune pară. El este mai apoi confcat de poarta $3$.

$\\[0.25cm]$

În final, poarta $0$ a confiscat $3$ pachete, poarta $2$ a confiscat $2$ pachete, și poarta $3$ a confiscat $1$ package. pachet. Prin urmare, obiectivul a fost atins.

$\\[0.25cm]$

$\bold{Notă:}$ Submulțimile secrete sunt prezentate doar pentru ilustrarea exempului. Ele nu sunt transmise către programul tău.

Restricții și precizări

• $1 \leq N \leq 300$
• $N \leq M \leq 2000$
• Fiecare pachet nevid este confiscat de o careva poartă de securitate.
• sunt exact $N$ porți de securitate utile.

Testare locală

Grader-ul local citește inputul în următorul format:

• linia 1: $N \ M$
• linia 2 + $i$ ($0 \leq i < M$): $K \ A[i][0] \ A[i][1] \ \ldots \ A[i][K - 1]$

Aici, $K$ este numărul de obiecte în mulțimea $A[i]$.

$\\[0.25cm]$

Grader-ul local apelează solve(N, M) și simulează funcția send_package.

$\\[0.25cm]$

După ce solve se termină, grader-ul local printează unul dintre următoarele mesaje:

• Correct dacă toate porțile utile au fost găsite și fiecare poartă utilă $c[i]$ a confiscat exact $N - i$ pachete.
• You did not find all useful gates dacă mai puțin de $N$ porți au confiscat cel puțin un pachet.
• Wrong dacă toate porțile utile au fost găsite, dar numărul necesar de pachete nu a fost confiscat de fiecare dintre ele.
• Invalid package if send_package este apelat cu un pachet nevalid. În acest caz, graderul local se închide imediat.