matrice

Se consideră o matrice $A$ cu $N$ linii şi $N$ coloane cu elemente distincte din mulţimea $\{0, 1 , \dots, N^2-1 \}$. Liniile şi respectiv coloanele sunt numerotate de la $0$ la $N-1$.

Vom nota cu $colmax(i)$ coloana pe care se află elementul maxim pe linia $i$ a matricei. Spunem că matricea $A$ este monotonă dacă pentru orice $i_1<i_2$, $colmax(i_1) \leq colmax(i_2)$.

Fie $L= \{ L_1, L_2, \dots, L_k \}$ o submulţime de linii ale matricei, iar $C= \{ C_1, C_2, \dots, C_p \}$ o submulţime de coloane. O submatrice a matricei $A$ este formată din elementele $A_{i, j}$, unde $i \in L$, iar $j \in C$.

Spunem că matricea $A$ este total monotonă dacă orice submatrice a ei este monotonă.
De exemplu, matricea din figura $1$ este total monotonă, valorile maxime de pe fiecare linie fiind îngroşate. Matricea din figura $2$ nu este total monotonă (am haşurat elementele unei submatrice care nu e monotonă).

Cerinţă

Se consideră o matrice total monotonă cu $N$ linii şi $N$ coloane care conţine valori distincte din mulţimea $\{0, 1 , \dots, N^2-1 \}$. Se cere să se determine pentru fiecare linie a matricei coloana pe care se află elementul maxim.

Interacţiune

Programul vostru nu va citi şi nu va scrie nimic. În schimb, va implementa funcția

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

ce primește ca parametru numǎrul natural $N$, reprezentând dimensiunea matricei, și care returnează un vector (indexat de la $0$) ce va conține, în ordine, coloanele pe care se află valorile maxime de pe liniile $0, 1, \dots, N-1$.

În interioriul funcției solve, puteți apela funcția

int query(int lin, int col);

ce va returna valoarea care se află în matrice pe linia $lin$ şi coloana $col$.

Restricții și precizări

• $1 \leq N \leq 100$;
• Dacă programul vostru va efectua cel mult $6 \cdot N$ interogări va primi punctajul maxim pe testul respectiv.
• Dacă programul vostru va efectua mai mult de $6 \cdot N$ interogări, dar nu mai mult de $10 \cdot N$ interogări, atunci veţi primi $50\%$ din punctajul testului respectiv
• Dacă programul vostru ajunge la rezultatul corect, dar foloseşte mai mult de $10 \cdot N$ interogări, atunci veţi primi $20\%$ din punctajul testului respectiv.
• Dacă programul vostru nu ajunge la răspunsul corect sau nu interacţionează corespunzător cu programul comisiei veţi primi $0$ puncte pe testul respectiv.
• Trebuie să includeți fișierul matrix.h.

Exemplu de interacţiune

Se apelează solve(2).
În solve se apelează query(0, 0), care returnează $3$.
În solve se apelează query(1, 1), care returnează $2$.
Funcția solve returnează $\{0, 1\}$.