#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
#define f first
#define s second
bool CheckIfStadium(int N, vector<vector<int>> F)
{
pii minRow, maxRow;
bool possible = true;
int state = 0;
int fullCount = 0;
vector<pii> rows;
pii prev;
for (int i = 0; i < N; i++)
{
int start = N;
int end = 0;
int openCount = 0;
for (int j = 0; j < N; j++)
{
if (F[i][j] == 0)
{
fullCount++;
if (openCount == 0)
{
openCount++;
}
else if (openCount == 2)
{
openCount++;
break;
}
start = min(start, j);
end = max(end, j);
}
else
{
if (openCount == 1)
{
openCount++;
}
}
}
// cout << "i = " << i << ", {" << start << ", " << end << "}, cnt = " << openCount << '\n';
if (openCount >= 3)
{
possible = false;
}
for (pii p : rows)
{
if (!((start <= p.f && end >= p.s) || (start >= p.f && end <= p.s)))
{
possible = false;
break;
}
}
if (!possible)
break;
rows.push_back({start, end});
if (i == 0)
{
minRow = {start, end};
maxRow = {start, end};
prev = {start, end};
continue;
}
// cout << "min: {" << minRow.f << ", " << minRow.s << "}, max: {" << maxRow.f << ", " << maxRow.s << "}\n";
if (state == 0 && start <= maxRow.f && end >= maxRow.s)
{
maxRow = {start, end};
prev = {start, end};
continue;
}
else if (start >= prev.f && end <= prev.s && ((start >= minRow.f && end <= minRow.s) || (start <= minRow.f && end >= minRow.s)))
{
state = 1;
minRow = {max(minRow.f, start), min(minRow.s, end)};
prev = {start, end};
continue;
}
possible = false;
break;
}
return possible;
}
int biggest_stadium(int N, vector<vector<int>> F)
{
bool isStadium = CheckIfStadium(N, F);
int treeCount = 0;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
treeCount += F[i][j];
}
}
if (isStadium)
{
return isStadium;
}
else
{
if (treeCount == 1)
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
if (!F[i][j])
continue;
int ans = N * N;
ans -= min(i + 1, N - i) * min(j + i, N - j);
return ans;
}
}
}
return 0;
}
}
int biggest_stadium2(int N, vector<vector<int>> F)
{
vector<vector<int>> prefixLine(N), prefixCol(N);
for (int i = 0; i < N; i++)
{
prefixLine[i] = vector<int>(N, 0);
prefixLine[i][0] = F[i][0];
for (int j = 1; j < N; j++)
{
prefixLine[i][j] = prefixLine[i][j - 1] + F[i][j];
}
}
for (int i = 0; i < N; i++)
{
prefixCol[i] = vector<int>(N, 0);
prefixCol[i][0] = F[0][i];
for (int j = 1; j < N; j++)
{
prefixCol[i][j] = prefixCol[i][j - 1] + F[j][i];
}
}
set<pii> freeCells;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
if (F[i][j] == 0)
{
freeCells.insert({i, j});
}
}
}
bool possible = true;
for (pii p1 : freeCells)
{
for (pii p2 : freeCells)
{
if (p1 == p2)
continue;
if (p1.f == p2.f)
{
int sum = prefixLine[p1.f][max(p1.s, p2.s)];
if (min(p1.s, p2.s) > 0)
{
sum -= prefixLine[p1.f][min(p1.s, p2.s) - 1];
}
if (sum != 0)
{
// cout << "{" << p1.f << ", " << p1.s << "} - {" << p2.f << ", " << p2.s << "}\n";
possible = false;
break;
}
}
else if (p1.s == p2.s)
{
int sum = prefixCol[p1.s][max(p1.f, p2.f)];
if (min(p1.f, p2.f) > 0)
{
sum -= prefixCol[p1.s][min(p1.f, p2.f) - 1];
}
if (sum != 0)
{
// cout << "{" << p1.f << ", " << p1.s << "} - {" << p2.f << ", " << p2.s << "}\n";
possible = false;
break;
}
}
else
{
// cout << "check {" << p1.f << ", " << p1.s << "} - {" << p2.f << ", " << p2.s << "}\n";
int sum1 = prefixLine[p1.f][max(p1.s, p2.s)] + prefixCol[p2.s][max(p1.f, p2.f)];
int sum2 = prefixLine[p2.f][max(p1.s, p2.s)] + prefixCol[p1.s][max(p1.f, p2.f)];
if (min(p1.s, p2.s) > 0)
{
sum1 -= prefixLine[p1.f][min(p1.s, p2.s) - 1];
sum2 -= prefixLine[p2.f][min(p1.s, p2.s) - 1];
}
if (min(p1.f, p2.f) > 0)
{
sum1 -= prefixCol[p2.s][min(p1.f, p2.f) - 1];
sum2 -= prefixCol[p1.s][min(p1.f, p2.f) - 1];
}
// cout << "sums: " << sum1 << " " << sum2 << '\n';
// cout << "s1: " << prefixLine[p1.f][max(p1.s, p2.s)] - prefixLine[p1.f][min(p1.s, p2.s)] << '\n';
if (sum1 != 0 && sum2 != 0)
{
// cout << "{" << p1.f << ", " << p1.s << "} - {" << p2.f << ", " << p2.s << "}\n";
possible = false;
break;
}
}
}
if (!possible)
break;
}
if (possible)
{
return freeCells.size();
}
else
{
return 0;
}
}
// int main()
// {
// int count = 0;
// for (int num = 0; num < (1 << 25); num++)
// {
// if (num % 100 == 0)
// {
// cout << "----" << num << '\n';
// }
// vector<vector<int>> vec(5);
// bitset<25> bSet(num);
// for (int i = 0; i < 5; i++)
// {
// vec[i] = vector<int>(5);
// for (int j = 0; j < 5; j++)
// {
// vec[i][j] = bSet[5 * i + j];
// }
// }
// int res = biggest_stadium(5, vec);
// int res2 = biggest_stadium2(5, vec);
// if (res != res2)
// {
// cout << "\nfound: " << count << '\n';
// count++;
// for (int i = 0; i < 5; i++)
// {
// for (int j = 0; j < 5; j++)
// {
// cout << vec[i][j];
// }
// cout << '\n';
// }
// cout << "different: " << res << " " << res2 << '\n';
// return 0;
// }
// }
// }
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
0 ms |
344 KB |
partial |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
wrong |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
wrong |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
0 ms |
344 KB |
partial |
| 2 |
Incorrect |
0 ms |
348 KB |
wrong |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
0 ms |
344 KB |
partial |
| 2 |
Incorrect |
0 ms |
348 KB |
wrong |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
0 ms |
344 KB |
partial |
| 2 |
Incorrect |
0 ms |
348 KB |
wrong |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
0 ms |
344 KB |
partial |
| 2 |
Incorrect |
0 ms |
348 KB |
wrong |
| 3 |
Halted |
0 ms |
0 KB |
- |
