autocar

Cerință

Această problemă este interactivă!
Gigel vine, impreună cu prietenii săi, la Euro cu autocarul. Odată ce organizatorii au aflat acest lucru, ei au început să se pregătească pentru a-i primi. Ei dețin o parcare în care locurile sunt așezate în linie. Parcarea are lungimea $N$ și este reprezentată printr-un șir binar $p$ de lungime $N$, unde $p_i$ este $0$ dacă al $i$-lea loc este liber și $1$ dacă este ocupat. Această parcare este făcută pentru mașini, nu pentru autocare, dar organizatorii fac un compromis în cazul lui Gigel, lăsându-l să își parcheze autocarul "pe invers"(vezi desen), pe locuri libere. Totuși, ei îi spun lui Gigel că NU are voie să își parcheze autocarul de lungime $K$ pe o secvență maximală de locuri libere cu lungimea mai mare decât $\text{4K}$.
Deoarece organizatorii nu știu lungimea autocarului lui Gigel, ei vor să îi scrie pe o foaie un șir cât mai scurt de numere naturale mai mici sau egale cu $1000$.
O secvență maximală de locuri libere este o secvență de locuri libere care are în stânga și în dreapta ei locuri ocupate sau capetele parcării.

Protocol de interacțiune

Concurentul trebuie să implementeze funcțiile:

vector<int> init(int N, vector<bool> p);
pair<int,int> solve(int N, int K, vector<int> v);

Funcția init va primi $N$ și șirul $p$, indexat de la 0, reprezentând parcarea, și va returna șirul $v$, cel pe care îl vor scrie organizatorii pe foaie. Funcția init va fi apelată o singură dată pentru fiecare test.
Funcția solve va primi $N$, $K$ și șirul $v$ scris pe foaie de organizatori și va returna capetele secvenței libere maximală unde va fi parcat autocarul lui Gigel (spre exemplu, dacă locurile 3, 4, 5, 6, 7 sunt libere și autocarul are lungimea 2, va returna {3,7}). Se garantează că există tot timpul un loc unde Gigel își poate parca autocarul. Funcția solve va fi apelată de mai multe ori pentru fiecare test, însă configurația parcării va fi cea inițială.

Concurentul NU va avea în program funcția main!
Concurentul NU va avea in program variabile globale!

Restricții și precizări

• $1 \leq K \leq N \leq 1 \ 000$

Punctaj

• Dacă pentru un test, la o apelare a funcției solve, răspunsul returnat este greșit, soluția va lua 0 puncte pe acel test.
• Fie $L$ lungimea șirului scris de către organizatori pe foaie. Fie $R = min(1,20/L)$.
• Punctajul obținut pe un test de $T$ puncte va fi $T \cdot R^2$.