splatoon

Time limit: 0.7s Memory limit: 128MB Input: Output:

Se consideră un tablou bidimensional format din NN linii și NN coloane, care conține celule libere codificate cu valoarea 00 și celule blocate, codificate cu valoarea 11. MM jucători sunt poziționați în celule diferite ale matricei. Un jucător poate fi poziționat într-o celulă liberă sau într-o celulă blocată. Începând cu momentul t0=0t_0 = 0, la fiecare moment întreg de timp tt, fiecare jucător colorează celulele libere aflate la distanța tt de poziția în care se află.

Definim distanța dintre două celule (i1,j1)(i_1, j_1) și (i2,j2)(i_2, j_2) ca fiind egală cu max(i1i2,j1j2)max(|i_1 - i_2|, |j_1 - j_2|), unde i1i_1 și i2i_2 corespund indicilor liniilor pe care se află cele două celule, iar j1j_1 și j2j_2 corespund coloanelor.

Cerința

Scrieți un program care citește un număr natural NN, valorile matricei și pozițiile inițiale ale jucătorilor și afișează la ieșire răspunsul la QQ întrebări de forma: “Care este primul moment de timp după care avem cel puțin PP celule colorate în matrice?”. În cazul în care pentru o întrebare nu se vor putea colora PP celule libere (după oricât de mult timp), se va afișa ca răspuns pentru acea întrebare valoarea 1-1.

Date de intrare

Prima linie conține numărul NN, iar fiecare din următoarele NN linii, câte NN numere separate prin câte un spațiu, corespunzând tipului celulelor de pe linia corespunzătoare din matrice.

Linia N+2N + 2 conține numărul de jucători MM, iar fiecare din următoarele MM linii câte două numere naturale, separate prin spațiu, reprezentând numărul liniei, respectiv, numărul coloanei în care se află fiecare din cei MM jucători.

Linia M+N+3M + N + 3 conține numărul natural QQ, reprezentând numărul de întrebări, iar ultima linie conține QQ numere naturale separate prin câte un spațiu, reprezentând valorile lui PP, pentru fiecare dintre cele QQ interogări.

Întrucât volumul datelor de intrare este foarte mare, vă recomandăm, în cazul în care folosiți pentru citire biblioteca iostream din standardul C++, să adăaugați la începutul funcției main următoarele instrucțiuni:

std::ios_base::sync_with_stdio(false);
std::cin.tie(0);

Date de ieșire

Ieșirea constă într-o singură linie, care va conține QQ numere, separate prin câte un spațiu, corespunzătoare răspunsurilor la întrebările date, în ordinea în care au fost citite.

Restricții și precizări

  • 3N15003 \leq N \leq 1500
  • 1M,QN21 \leq M, Q \leq N^2
  • 1P1091 \leq P \leq 10^9
  • Liniile și coloanele sunt indexate începând cu 11.
# Punctaj Restricții
1 12 1N201 \leq N \leq 20
2 33 1M101 \leq M \leq 10
3 21 3N6003 \leq N \leq 600
4 34 Nu există restricții suplimentare

Exemplu

stdin

8
0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 1 0 0 1 0 0 0
0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 1
2
3 3
6 6
3
35 16 1000

stdout

2 1 -1

Explicație

După momentul de timp t=0t = 0, se va colora doar celula (3,3)(3, 3). (Total: 11)

După momentul de timp t=1t = 1, se vor mai colora în plus celulele (2,2)(2, 2), (2,3)(2, 3), (2,4)(2, 4), (3,2)(3, 2), (3,4)(3, 4), (4,2)(4, 2), (4,3)(4, 3), (4,4)(4, 4), (5,6)(5, 6), (5,7)(5, 7), (6,5)(6, 5), (6,7)(6, 7), (7,5)(7, 5), (7,6)(7, 6), (7,7)(7, 7). (Total: 1616)

După momentul de timp t=2t = 2, vom avea în total colorate 4040 de celule.

Pentru prima interogare, primul moment de timp după care avem cel puțin 3535 de celule colorate este 22.

Analog, pentru a doua interogare, răspunsul este 11.

Nu se vor putea colora niciodată 10001000 de celule, răspunsul fiind 1-1.

Log in or sign up to be able to send submissions!