QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #154837 | #7120. Soccer | arbuzick | 6 | 169ms | 50564kb | C++20 | 2.6kb | 2023-09-01 00:52:16 | 2024-04-28 06:37:12 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
int biggest_stadium(int n, vector<vector<int>> f) {
vector<vector<int>> pr_sum(n + 1, vector<int>(n + 1));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
f[i][j] ^= 1;
pr_sum[i + 1][j + 1] = pr_sum[i + 1][j] + pr_sum[i][j + 1] - pr_sum[i][j] + f[i][j];
}
}
if (pr_sum[n][n] == n * n - 1) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (!f[i][j]) {
return n * n - min(i + 1, n - i) * min(j + 1, n - j);
}
}
}
}
vector<vector<int>> ll(n, vector<int>(n, -1)), rr(n, vector<int>(n, n)), dd(n, vector<int>(n, n));
for (int i = n - 1; i >= 0; --i) {
for (int j = 0; j < n; ++j) {
if (!f[i][j]) {
ll[i][j] = j;
dd[i][j] = i;
} else {
if (j > 0) {
ll[i][j] = ll[i][j - 1];
}
if (i + 1 < n) {
dd[i][j] = dd[i + 1][j];
}
}
}
for (int j = n - 1; j >= 0; --j) {
if (!f[i][j]) {
rr[i][j] = j;
} else if (j + 1 < n) {
rr[i][j] = rr[i][j + 1];
}
}
}
bool check = true;
auto get = [&](int i1, int j1, int i2, int j2) {
return pr_sum[i2][j2] - pr_sum[i1][j2] - pr_sum[i2][j1] + pr_sum[i1][j1];
};
for (int i1 = 0; i1 < n; ++i1) {
for (int j1 = 0; j1 < n; ++j1) {
for (int i2 = 0; i2 < n; ++i2) {
for (int j2 = 0; j2 < n; ++j2) {
if (!f[i1][j1] || !f[i2][j2]) {
continue;
}
}
}
}
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (!f[i][j]) {
continue;
}
int l = ll[i][j], r = rr[i][j], d = dd[i][j];
if (get(i, 0, i + 1, l + 1) || get(d, j, n, j + 1) || get(i, r, i + 1, n)) {
check = false;
}
if (l > -1 && d < n) {
if (get(d + 1, 0, n, l)) {
check = false;
}
}
if (r < n && d < n) {
if (get(d + 1, r + 1, n, n)) {
check = false;
}
}
}
}
if (check) {
return pr_sum[n][n];
} else {
return pr_sum[n][n] - 1;
}
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 6
Accepted
Test #1:
score: 6
Accepted
time: 1ms
memory: 3876kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 1 0
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 1
result:
ok ok
Test #2:
score: 6
Accepted
time: 0ms
memory: 4128kb
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: 3980kb
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: 12ms
memory: 6044kb
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: 169ms
memory: 50564kb
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: 1ms
memory: 3816kb
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: 4100kb
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: 3796kb
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: 3836kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 3 0 0 0 0 0 0 1 0 0
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 8
result:
ok ok
Subtask #2:
score: 0
Wrong Answer
Test #10:
score: 8
Accepted
time: 0ms
memory: 4096kb
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: 3804kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 3 0 0 0 0 1 1 0 0 1
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 5
result:
ok ok
Test #12:
score: 0
Wrong Answer
time: 0ms
memory: 3792kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 3 0 0 1 0 0 0 1 1 0
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 6
result:
wrong answer wrong
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
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:
0%