Fișierul intrare/ieșire	rotatesearch.in, rotatesearch.out	Sursă
Autor	autor necunoscut	Adăugată de	Teodor Plop • teodor94
Timp de execuție pe test	0.05 sec	Limită de memorie	2048 KB
Scorul tău	N/A	Dificultate	N/A

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Rotate Search (clasa a 10-a)

Atenție! Se pot obține 100 puncte sortând vectorul V. Fiți mai inventivi de atât și rezolvați altfel problema!

Se dă un vector V cu N elemente numere naturale distincte. Vectorul a fost inițial sortat crescător, iar mai apoi este posibil ca Bixi să îl fi rotit cu un anumit pivot K, vectorul dat arătând astfel:

• V(K), V(K + 1), ..., V(N – 1), V(0), V(1), ..., V(K – 1)

Să se răspundă la Q întrebări de tipul:

• Se găsește valoarea lui E în vectorul V?

Date de intrare

Fișierul de intrare rotatesearch.in conține pe prima linie valoarea lui N. Pe cea de-a doua linie, se găsesc N numere naturale reprezentând elementele vectorului V. Pe cea de-a treia linie se află valoarea lui Q, urmată de Q linii, fiecare linie conținând o valoare E care trebuie căutată în vector.

Date de ieșire

În fișierul de ieșire rotatesearch.out se găsesc Q linii, în fiecare linie i găsindu-se răspunsul la întrebarea i:

• În cazul în care valoarea se găsește în vector, se va afișa 1
• Altfel, se va afișa 0

Restricții

• 1 ≤ N ≤ 50.000
• 1 ≤ V[i] < 2³², 0 ≤ i < N
• 1 ≤ Q ≤ 10.000
• 1 ≤ E < 2³²

Exemplu