#include <bits/stdc++.h>
using namespace std;
struct Pos {
int x, y;
Pos(int x, int y) : x(x), y(y) {}
};
bool FIELD[2001][2001] = {0};
// bool empty(int a, int b, int x, int y) {
// assert(a == x || b == y); // only 1d queries
// if (a == x)
// for (int i = min(b, y); i <= max(b, y); i++)
// if (FIELD[a][i]) return false;
// if (b == y)
// for (int i = min(a, x); i <= max(a, x); i++)
// if (FIELD[i][b]) return false;
// return true;
// }
set<int> USED;
map<int, set<int>> G;
vector<int> NODES;
int biggest_stadium(int N, vector<vector<int>> F) {
vector<Pos> trees;
for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) {
if (F[i][j] == 1) trees.push_back({i, j});
FIELD[i][j] = F[i][j];
}
for (auto tree : trees) {
cerr << tree.x << " " << tree.y << endl;
}
if (trees.size() == 0) return N * N;
if (trees.size() == 1) {
int x = trees[0].x, y = trees[0].y;
int n = N - 1;
int a = (abs(x - 0) + 1) * (abs(y - 0) + 1);
int b = (abs(x - 0) + 1) * (abs(y - n) + 1);
int c = (abs(x - n) + 1) * (abs(y - 0) + 1);
int d = (abs(x - n) + 1) * (abs(y - n) + 1);
return N * N - min({a, b, c, d});
}
const int MAXN = 500;
set<set<pair<int, int>>> cover;
for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) {
if (FIELD[i][j] == 1) continue;
const int DIRS[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
// x, y and direction and the kick
// 0 = first kick, 1 = second kick
queue<tuple<int, int, int, bool>> q;
bool used[MAXN][MAXN][4][2] = {0};
bool visited[MAXN][MAXN] = {0};
set<pair<int, int>> vis;
visited[i][j] = true;
vis.insert({i, j});
for (int d = 0; d < 4; d++) {
used[i][j][d][0] = true;
q.push({i, j, d, 0});
}
while (!q.empty()) {
auto [x, y, d, k] = q.front(); q.pop();
x += DIRS[d][0];
y += DIRS[d][1];
if (x < 0 || x >= N || y < 0 || y >= N) continue;
if (FIELD[x][y]) continue;
if (used[x][y][d][k]) continue;
visited[x][y] = true;
vis.insert({x, y});
used[x][y][d][k] = true;
q.push({x, y, d, k});
if (k == true) continue;
for (int d = 0; d < 4; d++) {
used[x][y][d][1] = true;
q.push({x, y, d, 1});
}
}
for (auto [x, y] : vis) {
int a = i * N + j;
int b = x * N + y;
G[a].insert(b);
G[b].insert(a);
NODES.push_back(a);
NODES.push_back(b);
}
cover.insert(vis);
cerr << "\ncoverage from " << i << " " << j << endl;
for (int a = 0; a < N; a++) {
for (int b = 0; b < N; b++) {
if (a == i && b == j) cerr << "@";
else if (FIELD[a][b]) cerr << "#";
else if (visited[a][b]) cerr << "+";
else cerr << " ";
cerr << " ";
}
cerr << '\n';
}
}
vector<set<int>> max_comps;
deque<set<int>> comps;
set<set<int>> done;
for (int node: NODES) comps.push_back({node});
for (int node: NODES) done.insert({node});
while (!comps.empty()) {
set<int> comp = comps.front(); comps.pop_front();
bool changed = false;
for (int node: NODES) {
if (comp.count(node)) continue;
set<int> children = G[node];
// check if comp is a subset of children
bool is_subset = true;
for (int c : comp) {
if (!children.count(c)) {
is_subset = false;
break;
}
}
if (is_subset) {
changed = true;
set<int> new_comp = comp;
new_comp.insert(node);
if (!done.count(new_comp)) {
done.insert(new_comp);
comps.push_back(new_comp);
}
}
}
if (!changed) {
max_comps.push_back(comp);
}
}
for (auto comp: max_comps) {
cout << endl;
cout << "Component of size " << comp.size() << endl;
for (int a = 0; a < N; a++) {
for (int b = 0; b < N; b++) {
if (FIELD[a][b]) cerr << "#";
else if (comp.count(a * N + b)) cerr << "+";
else cerr << " ";
cerr << " ";
}
cerr << '\n';
}
}
int max_size = 0;
for (auto comp: max_comps)
max_size = max(max_size, (int)comp.size());
return max_size;
// for (int a = 0; a < N; a++) for (int b = 0; b < N; b++) {
// for (int x = 0; x < N; x++) for (int y = 0; y < N; y++) {
// // going throgh (a, y)
// if (a == x && b == y) continue;
// if (FIELD[a][b] || FIELD[x][y]) continue;
// if ((empty(a, b, a, y) && empty(x, y, a, y))
// || empty(a, b, x, b) && empty(x, y, x, b)) {
// continue;
// } else {return 0;}
// }
// }
// return N * N - trees.size();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4533 ms |
16832 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2648 KB |
ok |
| 2 |
Correct |
2 ms |
2652 KB |
ok |
| 3 |
Correct |
1 ms |
2652 KB |
ok |
| 4 |
Correct |
1 ms |
2652 KB |
ok |
| 5 |
Correct |
1 ms |
2396 KB |
ok |
| 6 |
Correct |
1 ms |
2488 KB |
ok |
| 7 |
Correct |
2 ms |
2804 KB |
ok |
| 8 |
Correct |
14 ms |
5976 KB |
ok |
| 9 |
Correct |
204 ms |
45836 KB |
ok |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2648 KB |
ok |
| 2 |
Correct |
2 ms |
2652 KB |
ok |
| 3 |
Incorrect |
3 ms |
2652 KB |
Possible tampering with the output |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4533 ms |
16832 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4533 ms |
16832 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4533 ms |
16832 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4533 ms |
16832 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
