QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#177534 | #7120. Soccer | triple321# | 14 | 270ms | 35444kb | C++20 | 4.3kb | 2023-09-13 01:50:45 | 2023-09-13 01:50:45 |
Judging History
answer
#include <bits/stdc++.h>
#ifndef CYBER
#include "soccer.h"
#endif
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("Ofast")
using namespace std;
using namespace __gnu_pbds;
#define lg long long
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
lg dx[] = {1, 0, -1, 0};
lg dy[] = {0, 1, 0, -1}, N;
lg valid(lg i, lg j)
{
return i >= 0 && i < N && j >= 0 && j < N;
}
int biggest_stadium(int n, vector<vector<int>> f)
{
N = n;
lg pos = 1, ans = 0, sum = 0;
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
ans += !f[i][j], sum += f[i][j];
vector<int> tree[n];
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
if(f[i][j])
{
tree[i].push_back(j);
}
}
}
for(int i = 0; i < n; i++)
{
lg bef = 0, aft = 0;
for(auto it : tree[i])
{
lg x = it;
while(x >= 0)
{
bef += !f[i][x];
x--;
}
x = it;
while(x < n)
{
aft += !f[i][x];
x++;
}
}
if(bef && aft) pos = 0;
tree[i].clear();
}
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
if(f[i][j])
{
tree[j].push_back(i);
}
}
}
for(int i = 0; i < n; i++)
{
lg bef = 0, aft = 0;
for(auto it : tree[i])
{
lg x = it;
while(x >= 0)
{
bef += !f[x][i];
x--;
}
x = it;
while(x < n)
{
aft += !f[x][i];
x++;
}
}
if(bef && aft) pos = 0;
}
set<lg> se[5];
//down, right, up, left
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
if(f[i][j]) continue;
if(i && j && f[i-1][j] && f[i][j-1])
{
auto it = se[4].lower_bound(i);
if(it != se[4].begin()) pos = 0;
}
if(i+1 < n && j && f[i+1][j] && f[i][j-1])
{
auto it = se[4].upper_bound(i);
if(it != se[4].end()) pos = 0;
}
if(i && f[i-1][j])
{
auto it = se[0].lower_bound(i);
if(it != se[0].begin()) pos = 0;
}
if(i+1 < n && f[i+1][j])
{
auto it = se[2].upper_bound(i);
if(it != se[2].end()) pos = 0;
}
if(j && f[i][j-1])
{
if(se[1].size()) pos = 0;
}
for(int k = 0; k < 4; k++)
{
lg newI = i+dx[k], newJ = j+dy[k];
if(!valid(newI, newJ)) continue;
if(f[newI][newJ])
{
se[k].insert((k%2 ? newI : newJ));
}
}
se[4].insert(i);
}
}
if(!pos) ans = 1;
if(sum == 1 && !pos)
{
int idI = 0, idJ = 0;
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
if(f[i][j])
{
idI = i, idJ = j;
}
}
}
idI++;
idJ++;
// cout << idI << ' ' << idJ << '\n';
// cout << idI*idJ << ' ' << idJ*(n-idI+1) << ' ' << idI*(n-idJ+1) << ' ' << (n-idJ+1)*(n-idI+1) << '\n';
ans = n*n-min({idI*idJ, idJ*(n-idI+1), idI*(n-idJ+1), (n-idJ+1)*(n-idI+1)});
}
else if(n <= 3 && !pos)
{
for(int i = 0; i < (1ll << (n*n)); i++)
{
vector<array<lg, 2>> a;
for(int j = 0; j < n*n; j++)
{
if((1ll << j)&i)
{
a.push_back({j/n, j%n});
}
}
lg o = 1;
for(auto it : a)
{
if(f[it[0]][it[1]]) o = 0;
for(auto it2 : a)
{
if(it[0] == it2[0])
{
for(int j = min(it[1], it2[1]); j <= max(it[1], it2[1]); j++)
{
if(f[it[0]][j]) o = 0;
}
if(o) continue;
}
if(it[1] == it2[1])
{
for(int j = min(it[0], it2[0]); j <= max(it[0], it2[0]); j++)
{
if(f[j][it[1]]) o = 0;
}
if(o) continue;
}
lg d = 1, h = 1;
if(!f[it[0]][it2[1]])
{
for(int i = min(it[1], it2[1]); i <= max(it[1], it2[1]); i++)
{
if(f[it[0]][i]) d = 0;
}
for(int i = min(it[0], it2[0]); i <= max(it[0], it2[0]); i++)
{
if(f[i][it2[1]]) d = 0;
}
if(d) continue;
}
if(!f[it2[0]][it[1]])
{
for(int i = min(it[1], it2[1]); i <= max(it[1], it2[1]); i++)
{
if(f[it2[0]][i]) h = 0;
}
for(int i = min(it[0], it2[0]); i <= max(it[0], it2[0]); i++)
{
if(f[i][it[1]]) h = 0;
}
if(h) continue;
}
o = 0;
break;
}
}
ans = max(ans, (lg)(o*a.size()));
}
}
return ans;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 6
Accepted
Test #1:
score: 6
Accepted
time: 0ms
memory: 3884kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 1 0
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 1
result:
ok ok
Test #2:
score: 6
Accepted
time: 0ms
memory: 3856kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 3 0 0 0 0 1 0 0 0 0
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 5
result:
ok ok
Test #3:
score: 6
Accepted
time: 1ms
memory: 3908kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 100 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 9850
result:
ok ok
Test #4:
score: 6
Accepted
time: 17ms
memory: 5832kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 500 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 236536
result:
ok ok
Test #5:
score: 6
Accepted
time: 270ms
memory: 35444kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 2000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 3786181
result:
ok ok
Test #6:
score: 6
Accepted
time: 0ms
memory: 3904kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 9 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 80
result:
ok ok
Test #7:
score: 6
Accepted
time: 0ms
memory: 3828kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 10 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 99
result:
ok ok
Test #8:
score: 6
Accepted
time: 0ms
memory: 3780kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 3 0 0 0 0 0 0 0 0 1
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 8
result:
ok ok
Test #9:
score: 6
Accepted
time: 0ms
memory: 3904kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 3 0 0 0 0 0 0 1 0 0
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 8
result:
ok ok
Subtask #2:
score: 8
Accepted
Test #10:
score: 8
Accepted
time: 1ms
memory: 4092kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 3 0 0 0 0 1 0 0 1 1
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 5
result:
ok ok
Test #11:
score: 8
Accepted
time: 0ms
memory: 3828kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 3 0 0 0 0 1 1 0 0 1
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 5
result:
ok ok
Test #12:
score: 8
Accepted
time: 1ms
memory: 4116kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 3 0 0 1 0 0 0 1 1 0
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 5
result:
ok ok
Test #13:
score: 8
Accepted
time: 1ms
memory: 4116kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 3 1 0 0 1 0 1 0 0 1
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 4
result:
ok ok
Test #14:
score: 8
Accepted
time: 1ms
memory: 3828kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 3 0 0 1 0 0 0 1 0 0
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 6
result:
ok ok
Test #15:
score: 8
Accepted
time: 0ms
memory: 3816kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 3 0 0 1 0 0 1 0 0 0
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 7
result:
ok ok
Test #16:
score: 8
Accepted
time: 0ms
memory: 4116kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 3 0 0 0 0 0 0 0 0 0
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 9
result:
ok ok
Test #17:
score: 8
Accepted
time: 1ms
memory: 3900kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 3 0 0 0 1 0 0 0 1 0
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 6
result:
ok ok
Test #18:
score: 8
Accepted
time: 0ms
memory: 3824kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 3 0 0 1 1 1 1 0 1 1
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 2
result:
ok ok
Test #19:
score: 8
Accepted
time: 0ms
memory: 3836kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 3 0 0 1 1 0 1 0 1 1
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 3
result:
ok ok
Test #20:
score: 8
Accepted
time: 0ms
memory: 3828kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 3 1 0 1 0 0 0 1 0 0
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 6
result:
ok ok
Subtask #3:
score: 0
Wrong Answer
Dependency #2:
100%
Accepted
Test #21:
score: 5.5
Acceptable Answer
time: 0ms
memory: 4096kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 1
result:
points 0.250 partial
Test #22:
score: 5.5
Acceptable Answer
time: 0ms
memory: 3820kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 1
result:
points 0.250 partial
Test #23:
score: 5.5
Acceptable Answer
time: 0ms
memory: 4116kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 7 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 1 0 0 1 0 0 1 0 1
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 1
result:
points 0.250 partial
Test #24:
score: 5.5
Acceptable Answer
time: 0ms
memory: 3820kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 7 0 0 1 1 0 1 0 1 1 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 1 1 1 0 0 0 1 0 1 0 0 1 0 1 0 0 1 1 0 1 1 0 1 0 1
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 1
result:
points 0.250 partial
Test #25:
score: 5.5
Acceptable Answer
time: 0ms
memory: 3820kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 7 0 0 1 1 0 0 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 0 0 0 0 0 0 1 0 0 1 0 0 1
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 1
result:
points 0.250 partial
Test #26:
score: 0
Wrong Answer
time: 0ms
memory: 3840kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 7 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 0 0 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 1
result:
wrong answer wrong
Subtask #4:
score: 0
Skipped
Dependency #3:
0%
Subtask #5:
score: 0
Skipped
Dependency #4:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
0%