# PBinfo #3681 – splatoon – Rezolvare C++ Sursa: Codul lui Andrei Limbaj: C++ Autor rezolvare: Darius ## Enunț Se consideră un tablou bidimensional format din N linii și N coloane, care conține celule libere codificate cu valoarea 0 și celule blocate, codificate cu valoarea 1. M 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 = 0, la fiecare moment întreg de timp t, fiecare jucător colorează celulele libere aflate la distanța t de poziția în care se află. Definim distanța dintre două celule (i1, j1) și (i2, j2) ca fiind egală cu max(|i1 - i2|, |j1 - j2|), unde i1 și i2 corespund indicilor liniilor pe care se află cele două celule, iar j1 și j2 corespund coloanelor. Cerința Scrieți un program care citește un număr natural N, valorile matricei și pozițiile inițiale ale jucătorilor și afișează la ieșire răspunsul la Q întrebări de forma: “Care este primul moment de timp după care avem cel puțin P celule colorate în matrice?”. În cazul în care pentru o întrebare nu se vor putea colora P celule libere (după oricât de mult timp), se va afișa ca răspuns pentru acea întrebare valoarea -1. Date de intrare Prima linie conține numărul N, iar fiecare din următoarele N linii, câte N numere separate prin câte un spațiu, corespunzând tipului celulelor de pe linia corespunzătoare din matrice. Linia N + 2 conține numărul de jucători M, iar fiecare din următoarele M 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 M jucători. Linia M + N + 3 conține numărul natural Q, reprezentând numărul de întrebări, iar ultima linie conține Q numere naturale separate prin câte un spațiu, reprezentând valorile lui P, pentru fiecare dintre cele Q 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 Q 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 3 ≤ N ≤ 1500 \( 1 ≤ M, Q ≤ {N}^{2} \) \( 1 ≤ P ≤ {10}^{9} \) liniile și coloanele sunt indexate începând cu 1. Subtask 1(12 puncte) 3 ≤ N ≤ 20 Subtask 2(33 de puncte) 1 ≤ M ≤ 10 Subtask 3(21 de puncte) 3 ≤ N ≤ 600 Subtask 4(34 de puncte) fără restricții suplimentare. Exemplu: Intrare 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 Ieșire 2 1 -1 Explicație După momentul de timp t = 0, se va colora doar celula (3, 3). (Total: 1) După momentul de timp t = 1, se vor mai colora în plus celulele (2, 2), (2, 3), (2, 4), (3, 2), (3, 4), (4, 2), (4, 3), (4, 4), (5, 6), (5, 7), (6, 5), (6, 7), (7, 5), (7, 6), (7, 7). (Total: 16) După momentul de timp t = 2, vom avea în total colorate 40 de celule. Pentru prima interogare, primul moment de timp după care avem cel puțin 35 de celule colorate este 2. Analog, pentru a doua interogare, răspunsul este 1. Nu se vor putea colora niciodată 1000 de celule, răspunsul fiind -1. ## Cod sursă C++ ```cpp /* * Splatoon - O(N^2*logN) * Bogdan Iordache */ #include using namespace std; const int kMaxN = 1505; int N, M; bool blocked[kMaxN][kMaxN]; int player_mat[kMaxN][kMaxN]; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> N; for (int i = 1; i <= N; ++i) for (int j = 1; j <= N; ++j) cin >> blocked[i][j]; cin >> M; for (int i = 1; i <= M; ++i) { int x, y; cin >> x >> y; player_mat[x][y] = 1; } // Determinam pentru fiecare celula libera care este timpul minim dupa care // va fi colorata. Cautam binar acest timp si verificam, folosind sume // partiale, daca exista vreun jucator in patratul centrat in celula // curenta, corespunzator timpului fixat. for (int i = 1; i <= N; ++i) for (int j = 1; j <= N; ++j) player_mat[i][j] += player_mat[i - 1][j] + player_mat[i][j - 1] - player_mat[i - 1][j - 1]; vector times; times.reserve(N * N); for (int i = 1; i <= N; ++i) { for (int j = 1; j <= N; ++j) { if (blocked[i][j]) continue; int lo = 0, hi = N; while (lo <= hi) { int mid = (lo + hi) / 2; int up = max(1, i - mid), down = min(N, i + mid); int left = max(1, j - mid), right = min(N, j + mid); int check = player_mat[down][right] - player_mat[up - 1][right] - player_mat[down][left - 1] + player_mat[up - 1][left - 1]; // daca avem macar un jucator in acest patrat if (check > 0) hi = mid - 1; else lo = mid + 1; } times.push_back(lo); } } sort(times.begin(), times.end()); times.push_back(-1); int Q; cin >> Q; for (int i = 1; i <= Q; ++i) { int p; cin >> p; cout << times[min(p - 1, int(times.size()) - 1)] << " \n"[i == Q]; } return 0; } ``` ## Resurse - [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/3681) - [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/3681/cod.cpp) - [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-3681/main.cpp) - [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)