# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1233354 | Ghulam_Junaid | Closing Time (IOI23_closing) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include "soccer.h"
// #include "grader.cpp"
using namespace std;
const int N = 5;
bool in_mask[N][N];
vector<vector<int>> F;
bool safe(int x, int y, int a, int b){
bool good = 1;
if (a == x){
for (int i = min(b, y); i <= max(b, y); i ++)
good &= (F[a][i] == 0 and in_mask[a][i]);
}
else if (b == y){
for (int i = min(a, x); i <= max(a, x); i ++)
good &= (F[i][b] == 0 and in_mask[i][b]);
}
else{
if (x > a){
swap(a, x);
swap(b, y);
}
return (safe(x, y, x, b) and safe(x, b, a, b)) or (safe(x, y, a, y) and safe(a, y, a, b));
}
return good;
}
int biggest_stadium(int n, vector<vector<int>> FF){
F = FF;
int x = -1, y = -1;
for (int i = 0; i < n; i ++)
for (int j = 0; j < n; j ++)
if (F[i][j] == 1)
x = i, y = j;
if (n <= 3){
int ans = 0;
for (int mask = 0; mask < (1 << (n * n)); mask ++){
memset(in_mask, 0, sizeof in_mask);
vector<pair<int, int>> vec;
bool good = 1;
for (int i = 0; i < n * n; i ++)
if ((1 << i) & mask)
vec.push_back({i / n, i % n});
for (auto [x, y] : vec)
in_mask[x][y] = 1;
for (auto [x, y] : vec){
good &= (F[x][y] == 0);
for (auto [a, b] : vec){
good &= safe(x, y, a, b);
}
}
if (good)
ans = max(ans, __builtin_popcount(mask));
}
return ans;
}
if (x == -1) return n * n;
else return n * n - min({(x + 1) * (y + 1), (n - x) * (y + 1), (x + 1) * (n - y), (n - x) * (n - y)});
}