| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 769605 | 2023-06-29T20:38:46 Z | MilosMilutinovic | Council (JOI23_council) | C++14 | 1224 ms | 98888 KB |
#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 10;
const int M = 22;
int n, m, a[N][M], b[N][M], v[N], cnt[M], bst[1 << M], ans[N];
void dfs(int i, int x) {
for (int j = 1; j <= m; j++) {
int ni = (i ^ (1 << j));
if (__builtin_popcount(bst[ni] & ni) > __builtin_popcount(x & ni)) {
bst[ni] = x;
dfs(ni, x);
}
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
scanf("%d", &a[i][j]);
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cnt[j] += a[i][j];
}
}
int full_mask = 0;
for (int j = 1; j <= m; j++) {
full_mask += (1 << j);
}
for (int iter = 1; iter <= 2; iter++) {
for (int i = 1; i <= n; i++) {
v[i] = 0;
for (int j = 1; j <= m; j++) {
if (a[i][j] == 1) {
v[i] += (1 << j);
}
}
}
for (int i = 0; i < (1 << M); i++) {
bst[i] = i;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cnt[j] -= a[i][j];
}
int msk = 0, good = 0;
for (int j = 1; j <= m; j++) {
if (cnt[j] == (n / 2)) {
msk ^= (1 << j);
}
if (cnt[j] >= (n / 2)) {
good += 1;
}
}
ans[iter == 1 ? i : n - i + 1] = max(ans[iter == 1 ? i : n - i + 1], good - __builtin_popcount(bst[msk] & msk));
for (int j = 1; j <= m; j++) {
cnt[j] += a[i][j];
}
dfs(full_mask ^ v[i], v[i]);
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
b[n - i + 1][j] = a[i][j];
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
a[i][j] = b[i][j];
}
}
}
for (int i = 1; i <= n; i++) {
printf("%d\n", ans[i]);
}
return 0;
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 9 ms | 16724 KB | Output is correct |
| 2 | Correct | 11 ms | 16980 KB | Output is correct |
| 3 | Correct | 9 ms | 16724 KB | Output is correct |
| 4 | Correct | 9 ms | 16724 KB | Output is correct |
| 5 | Correct | 500 ms | 98696 KB | Output is correct |
| 6 | Correct | 10 ms | 16724 KB | Output is correct |
| 7 | Correct | 706 ms | 98888 KB | Output is correct |
| 8 | Correct | 954 ms | 98164 KB | Output is correct |
| 9 | Correct | 1162 ms | 98792 KB | Output is correct |
| 10 | Correct | 599 ms | 98760 KB | Output is correct |
| 11 | Correct | 772 ms | 98728 KB | Output is correct |
| 12 | Correct | 1224 ms | 98764 KB | Output is correct |
| 13 | Incorrect | 9 ms | 16724 KB | Output isn't correct |
| 14 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 9 ms | 16724 KB | Output is correct |
| 2 | Correct | 11 ms | 16980 KB | Output is correct |
| 3 | Correct | 9 ms | 16724 KB | Output is correct |
| 4 | Correct | 9 ms | 16724 KB | Output is correct |
| 5 | Correct | 500 ms | 98696 KB | Output is correct |
| 6 | Correct | 10 ms | 16724 KB | Output is correct |
| 7 | Correct | 706 ms | 98888 KB | Output is correct |
| 8 | Correct | 954 ms | 98164 KB | Output is correct |
| 9 | Correct | 1162 ms | 98792 KB | Output is correct |
| 10 | Correct | 599 ms | 98760 KB | Output is correct |
| 11 | Correct | 772 ms | 98728 KB | Output is correct |
| 12 | Correct | 1224 ms | 98764 KB | Output is correct |
| 13 | Incorrect | 9 ms | 16724 KB | Output isn't correct |
| 14 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 9 ms | 16744 KB | Output is correct |
| 2 | Correct | 110 ms | 71196 KB | Output is correct |
| 3 | Correct | 107 ms | 71240 KB | Output is correct |
| 4 | Correct | 90 ms | 71300 KB | Output is correct |
| 5 | Correct | 114 ms | 71284 KB | Output is correct |
| 6 | Incorrect | 93 ms | 71252 KB | Output isn't correct |
| 7 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 9 ms | 16744 KB | Output is correct |
| 2 | Correct | 110 ms | 71196 KB | Output is correct |
| 3 | Correct | 107 ms | 71240 KB | Output is correct |
| 4 | Correct | 90 ms | 71300 KB | Output is correct |
| 5 | Correct | 114 ms | 71284 KB | Output is correct |
| 6 | Incorrect | 93 ms | 71252 KB | Output isn't correct |
| 7 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 9 ms | 16744 KB | Output is correct |
| 2 | Correct | 110 ms | 71196 KB | Output is correct |
| 3 | Correct | 107 ms | 71240 KB | Output is correct |
| 4 | Correct | 90 ms | 71300 KB | Output is correct |
| 5 | Correct | 114 ms | 71284 KB | Output is correct |
| 6 | Incorrect | 93 ms | 71252 KB | Output isn't correct |
| 7 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 9 ms | 16744 KB | Output is correct |
| 2 | Correct | 110 ms | 71196 KB | Output is correct |
| 3 | Correct | 107 ms | 71240 KB | Output is correct |
| 4 | Correct | 90 ms | 71300 KB | Output is correct |
| 5 | Correct | 114 ms | 71284 KB | Output is correct |
| 6 | Incorrect | 93 ms | 71252 KB | Output isn't correct |
| 7 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 9 ms | 16724 KB | Output is correct |
| 2 | Correct | 11 ms | 16980 KB | Output is correct |
| 3 | Correct | 9 ms | 16724 KB | Output is correct |
| 4 | Correct | 9 ms | 16724 KB | Output is correct |
| 5 | Correct | 500 ms | 98696 KB | Output is correct |
| 6 | Correct | 10 ms | 16724 KB | Output is correct |
| 7 | Correct | 706 ms | 98888 KB | Output is correct |
| 8 | Correct | 954 ms | 98164 KB | Output is correct |
| 9 | Correct | 1162 ms | 98792 KB | Output is correct |
| 10 | Correct | 599 ms | 98760 KB | Output is correct |
| 11 | Correct | 772 ms | 98728 KB | Output is correct |
| 12 | Correct | 1224 ms | 98764 KB | Output is correct |
| 13 | Incorrect | 9 ms | 16724 KB | Output isn't correct |
| 14 | Halted | 0 ms | 0 KB | - |