#include "bits/stdc++.h"
using namespace std;
struct Point {
int x, y;
Point(int x, int y): x(x), y(y) {}
};
bool operator<(const Point &a, const Point &b) {
return a.x < b.x || (a.x == b.x && a.y < b.y);
}
int biggest_stadium(int N, vector<vector<int>> F) {
int num_trees = 0;
for (auto i: F) for (int j: i) num_trees += j;
if (num_trees == 0) {
return N*N;
}
if (num_trees == 1) {
int x, y;
for (int i = 0; i < N; i++) for (int j = 0; j < N; j++)
if (F[i][j] == 1) {
x = i, y = j;
break;
}
return N*N - min(x + 1, N - x) * min(y + 1, N - y);
}
for (int i = 0; i < N; i++) {
F[i].insert(F[i].begin(), 1);
F[i].push_back(1);
}
F.insert(F.begin(), vector<int>(N + 2, 1));
F.push_back(vector<int>(N + 2, 1));
N += 2;
if (N <= 10) {
vector<vector<set<Point>>> quads[4];
for (auto &q: quads) q.resize(N, vector<set<Point>>(N, set<Point>()));
// index, dx, dy, starting x, starting y, x increment, y increment
int m = N - 1;
int quad_dirs[4][7] = {
{0, -1, -1, 0, 0, 1, 1},
{1, -1, 1, 0, m, 1, -1},
{2, 1, 1, m, m, -1, -1},
{3, 1, -1, m, 0, -1, 1}
};
for (auto [idx, dx, dy, sx, sy, ix, iy]: quad_dirs) {
for (int i = sx; i < N && i >= 0; i += ix) for (int j = sy; j < N && j >= 0; j += iy) {
if (F[i][j] == 1) continue;
int a[2] = {i + dx, j};
int b[2] = {i, j + dy};
if (F[a[0]][a[1]] == 0)
for (auto p: quads[idx][a[0]][a[1]]) if (p.y == j) quads[idx][i][j].insert(p);
if (F[b[0]][b[1]] == 0)
for (auto p: quads[idx][b[0]][b[1]]) if (p.x == i) quads[idx][i][j].insert(p);
quads[idx][i][j].insert(Point(i, j));
}
}
vector<vector<set<Point>>> lines = vector<vector<set<Point>>>(N, vector<set<Point>>(N, set<Point>()));
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
for (int k = 0; k < 4; k++)
for (auto p: quads[k][i][j]) lines[i][j].insert(p);
for (auto [idx, dx, dy, sx, sy, ix, iy]: quad_dirs) {
for (int i = sx; i < N && i >= 0; i += ix) for (int j = sy; j < N && j >= 0; j += iy) {
if (F[i][j] == 1) continue;
int a[2] = {i + dx, j};
int b[2] = {i, j + dy};
if (F[a[0]][a[1]] == 1 || F[b[0]][b[1]] == 1) continue;
set<Point> temp;
set_intersection(quads[idx][a[0]][a[1]].begin(), quads[idx][a[0]][a[1]].end(),
quads[idx][b[0]][b[1]].begin(), quads[idx][b[0]][b[1]].end(),
inserter(temp, temp.begin()));
for (auto p: temp) quads[idx][i][j].insert(p);
}
}
int max_area = 0;
for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) {
if (F[i][j] == 1) continue;
auto union_size = [&](set<Point> &a, set<Point> &b, set<Point> &c) {
set<Point> t;
for (auto p: a) t.insert(p);
for (auto p: b) t.insert(p);
for (auto p: c) t.insert(p);
return t.size();
};
auto print_union = [&](set<Point> &a, set<Point> &b, set<Point> &c) {
set<Point> t;
for (auto p: a) t.insert(p);
for (auto p: b) t.insert(p);
for (auto p: c) t.insert(p);
for (int x = 0; x < N; x++) {
for (int y = 0; y < N; y++) {
if (x == i && y == j) cerr << "X ";
else cerr << (t.count(Point(x, y)) ? 'x' : (F[x][y] ? '_': ' ')) << " ";
}
cerr << endl;
}
cerr << endl;
};
for (int k = 0; k < 4; k++) {
int area = union_size(quads[k][i][j], quads[(k + 1) % 4][i][j], lines[i][j]);
if (area >= max_area) {
max_area = area;
// print_union(quads[k][i][j], quads[(k + 1) % 4][i][j], lines[i][j]);
}
}
}
return max_area;
}
// for (auto row: F) {
// bool beg = false, end = false;
// for (int i: row) {
// if (i == 0 && !beg) beg = true;
// if (i == 1 && beg) end = true;
// if (i == 0 && end) return 0;
// }
// }
bool beg, end;
for (int i = 0; i < N; i++) {
beg = false, end = false;
for (int j = 0; j < N; j++) {
if (F[j][i] == 0 && !beg) beg = true;
if (F[j][i] == 1 && beg) end = true;
if (F[j][i] == 0 && end) return 0;
}
beg = false, end = false;
for (int j = 0; j < N; j++) {
if (F[i][j] == 0 && !beg) beg = true;
if (F[i][j] == 1 && beg) end = true;
if (F[i][j] == 0 && end) return 0;
}
}
auto valid = [&](int n) {
return n >= 0 && n < N;
};
int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
vector<vector<bool>> seen(N, vector<bool>(N, false));
queue<tuple<int, int, bool>> q;
bool f1 = false, f0 = false;
for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) {
if (!f1 && F[i][j] == 1)
q.push({i, j, 1}), f1 = 1, seen[i][j] = true;
if (!f0 && F[i][j] == 0)
q.push({i, j, 0}), f0 = 1, seen[i][j] = true;
}
while (!q.empty()) {
auto [x, y, t] = q.front();
q.pop();
for (auto [dx, dy]: dirs) {
int nx = x + dx, ny = y + dy;
if (valid(nx) && valid(ny) && !seen[nx][ny] && F[nx][ny] == t) {
q.push({nx, ny, t});
seen[nx][ny] = true;
}
}
}
for (int i = 0; i < N; i++) for (int j = 0; j < N; j++)
if (!seen[i][j]) return 0; // islands!!!
// most extreme zeros
// Point minx = {N, N}, maxx = {0, 0}, miny = {N, N}, maxy = {0, 0};
// for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) {
// if (F[i][j] == 0) {
// if (i < minx.x) minx = {i, j};
// if (i > maxx.x) maxx = {i, j};
// if (j < miny.y) miny = {i, j};
// if (j > maxy.y) maxy = {i, j};
// }
// }
// Point points[4] = {minx, maxx, miny, maxy};
vector<Point> points;
for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) {
if (F[i][j] == 0) {
int corners[4][2][2] = {
{{ 1, 0}, {0, 1}},
{{ 1, 0}, {0, -1}},
{{-1, 0}, {0, 1}},
{{-1, 0}, {0, -1}}
};
for (auto [a, b]: corners) {
int ax = i + a[0], ay = j + a[1];
int bx = i + b[0], by = j + b[1];
if (F[ax][ay] + F[bx][by] == 2) {
points.push_back(Point(i, j));
break;
}
}
}
}
for (int i = 0; i < points.size(); i++) for (int j = i + 1; j < points.size(); j++) {
if (F[points[i].x][points[j].y] + F[points[j].x][points[i].y] == 2) {
return 0; // 3 or more kicks
}
}
int zeros = 0;
for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) {
if (F[i][j] == 0) zeros++;
}
return zeros;
}
