/* Ignut
started: 13.08.2024
now: 13.08.2024
████████████████████████████████████████████████████████████████████
████████████████████████████████ ████████████████████████████████
██████████████████████████████ ██████████████████████████████
██████ ██████████████████ ██████████████████ ██████
██████ ██████████████ ██████████████ ██████
██████ ██ ████████████ ████████████ ██ ██████
██████ ████ ██████████ ██████████ ████ ██████
██████ ████ ██████████ ██████████ ████ ██████
██████ ████ ██████████ ██████████ ██████ ██████
██████ ██████ ██████████ ██████████ ██████ ██████
██████ ██████ ████████ ████████ ██████ ██████
██████ ██████ ██████ ██████ ██████ ██████
██████ ████ ████ ████ ████ ██████
██████ ██████████ ████ ██████████ ██████
██████ ██ ██████ ████████ ██████ ██ ██████
██████ ██████ ████████ ██████ ██████
██████ ██ ██ ██████
██████████████████████ ████ ████ ██████████████████████
████████████████████████ ██ ██ ████████████████████████
██████████████████████████ ██████████████████████████
██████████████████████████████ ██████████████████████████████
████████████████████████████████████████████████████████████████████
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 2222;
int n;
vector<vector<int>> f;
bool used[MAXN][MAXN];
vector<pair<int, int>> delta = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
bool Good(int i, int j) {
return i >= 0 && j >= 0 && i < n && j < n && f[i][j] == 0 && !used[i][j];
}
int cnt = 0;
void dfs(int i, int j) {
cnt ++;
used[i][j] = true;
for (auto [di, dj] : delta) {
int ci = i + di, cj = j + dj;
if (Good(ci, cj)) {
dfs(ci, cj);
}
}
}
int Check() {
for (int i = 0; i < n; i ++)
for (int j = 0; j < n; j ++)
used[i][j] = false;
int prev_l = -1, prev_r = -1;
bool have_sm = false;
for (int i = 0; i < n; i ++) {
int first = -1, last = -1, cnt = 0;
for (int j = 0; j < n; j ++) {
if (f[i][j] == 1) continue;
if (first == -1) first = j;
last = j;
cnt ++;
}
if (cnt > 0 && cnt != last - first + 1) return 1;
if (prev_l == -1) {
prev_l = first;
prev_r = last;
continue;
}
if (cnt == 0) continue;
bool sm = false;
if (first > prev_l || last < prev_r) sm = true;
bool bg = false;
if (first < prev_l || last > prev_r) bg = true;
if (sm && bg) return 1;
if (bg && have_sm) return 1;
if (sm) have_sm = true;
prev_l = first;
prev_r = last;
}
prev_l = -1, prev_r = -1;
have_sm = false;
for (int j = 0; j < n; j ++) {
int first = -1, last = -1, cnt = 0;
for (int i = 0; i < n; i ++) {
if (f[i][j] == 1) continue;
if (first == -1) first = i;
last = i;
cnt ++;
}
if (cnt > 0 && cnt != last - first + 1) return 1;
if (prev_l == -1) {
prev_l = first;
prev_r = last;
continue;
}
if (cnt == 0) continue;
bool sm = false;
if (first > prev_l || last < prev_r) sm = true;
bool bg = false;
if (first < prev_l || last > prev_r) bg = true;
if (sm && bg) return 1;
if (bg && have_sm) return 1;
if (sm) have_sm = true;
prev_l = first;
prev_r = last;
}
for (int i = 0; i < n; i ++) {
for (int j = 0; j < n; j ++) {
if (f[i][j] == 1) continue;
int up = 0;
for (int ii = i; ii >= 0; ii --) {
if (f[ii][j] == 1) break;
up ++;
}
int left = 0;
for (int jj = j; jj >= 0; jj --) {
if (f[i][jj] == 1) break;
left ++;
}
if (Good(i - up, j - left)) return 1;
int right = 0;
for (int jj = j; jj < n; jj ++) {
if (f[i][jj] == 1) break;
right ++;
}
if (Good(i - up, j + right)) return 1;
}
}
int i0, j0;
for (int i = 0; i < n; i ++)
for (int j = 0; j < n; j ++)
if (f[i][j] == 0)
i0 = i, j0 = j;
cnt = 0;
dfs(i0, j0);
int sum = n * n;
for (int i = 0; i < n; i ++)
for (int j = 0; j < n; j ++)
sum -= f[i][j];
if (cnt != sum) return 1;
return sum;
}
int biggest_stadium(int N, vector<vector<int>> F) {
int cntT = 0;
for (int i = 0; i < N; i ++)
for (int j = 0; j < N; j ++)
cntT += F[i][j];
if (cntT <= 1) {
for (int i = 0; i < N; i ++) {
for (int j = 0; j < N; j ++) {
if (F[i][j] == 0) continue;
int mn = N * N;
mn = min(mn, (i + 1) * (j + 1));
mn = min(mn, (N - i) * (N - j));
mn = min(mn, (N - i) * (j + 1));
mn = min(mn, (i + 1) * (N - j));
return N * N - mn;
}
}
return N * N;
}
if (N > 3) return Check();
n = N;
f = F;
int res = 1;
for (int mask = 0; mask < 1 << (N * N); mask ++) {
for (int i = 0; i < N; i ++) {
for (int j = 0; j < N; j ++) {
f[i][j] = F[i][j];
f[i][j] |= (mask & 1);
mask >>= 1;
}
}
}
return res;
}
Compilation message
soccer.cpp: In function 'int Check()':
soccer.cpp:155:8: warning: 'j0' may be used uninitialized in this function [-Wmaybe-uninitialized]
155 | dfs(i0, j0);
| ~~~^~~~~~~~
soccer.cpp:155:8: warning: 'i0' may be used uninitialized in this function [-Wmaybe-uninitialized]
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
ok |
| 2 |
Correct |
0 ms |
348 KB |
ok |
| 3 |
Correct |
0 ms |
348 KB |
ok |
| 4 |
Correct |
0 ms |
348 KB |
ok |
| 5 |
Correct |
0 ms |
348 KB |
ok |
| 6 |
Correct |
0 ms |
348 KB |
ok |
| 7 |
Correct |
1 ms |
348 KB |
ok |
| 8 |
Correct |
12 ms |
2200 KB |
ok |
| 9 |
Correct |
226 ms |
31792 KB |
ok |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
ok |
| 2 |
Correct |
0 ms |
348 KB |
ok |
| 3 |
Execution timed out |
4534 ms |
344 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
