# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
735797 | 2023-05-04T16:46:32 Z | nguyentunglam | Council (JOI23_council) | C++17 | 2997 ms | 16548 KB |
#include<bits/stdc++.h> #define fi first #define se second #define endl "\n" #define ii pair<int, int> using namespace std; const int N = 3e5 + 10, M = 10, full = 1 << M; bool a[N][21]; int vote[21], ans[N], bit[1 << 20]; int f[1 << M][1 << M], g[1 << M][1 << M]; int n, m; void add(int mask) { int mask1 = (mask >> M); int mask2 = mask ^ (mask1 << M); for(int mask3 = 0; mask3 < full; mask3++) if (f[mask3][mask2]) { g[mask3][mask2] = min(g[mask3][mask2], bit[mask1 & mask3]); if (f[mask3][mask2] > g[mask3][mask2]) swap(f[mask3][mask2], g[mask3][mask2]); } } pair<int, int> get(int mask) { int ret1 = 21, ret2 = 21; int mask3 = mask >> M; int mask4 = mask ^ (mask3 << M); for(int mask2 = 0; mask2 < full; mask2++) if (f[mask3][mask2] != 21) { ret2 = min(ret2, f[mask3][mask2] + bit[mask4 & mask2]); if (ret1 > ret2) swap(ret1, ret2); ret2 = min(ret2, g[mask3][mask2] + bit[mask4 & mask2]); } return make_pair(ret1, ret2); } int main() { #define task "" cin.tie(0) -> sync_with_stdio(0); if (fopen ("task.inp", "r")) { freopen ("task.inp", "r", stdin); freopen ("task.out", "w", stdout); } if (fopen (task".inp", "r")) { freopen (task".inp", "r", stdin); freopen (task".out", "w", stdout); } for(int mask = 0; mask < full; mask++) bit[mask] = __builtin_popcount(mask); cin >> n >> m; for(int i = 1; i <= n; i++) for(int j = 0; j < m; j++) { cin >> a[i][j]; vote[j] += a[i][j]; } for(int mask1 = 0; mask1 < full; mask1++) for(int mask2 = 0; mask2 < full; mask2++) f[mask1][mask2] = g[mask1][mask2] = 21; for(int i = 1; i <= n; i++) { int mask = 0; for(int j = 0; j < m; j++) if (a[i][j]) mask |= (1 << j); add(mask); } for(int i = 1; i <= n; i++) { int mask = 0, tmp = 0, same = 0; for(int j = 0; j < m; j++) { vote[j] -= a[i][j]; if (vote[j] >= n / 2) { if (vote[j] - 1 < n / 2) mask |= (1 << j); tmp++; } vote[j] -= a[i][j]; if (vote[j] >= n / 2) same++; vote[j] += a[i][j] + a[i][j]; } pair<int, int> h = get(mask); if (tmp - h.fi == same) swap(h.fi, h.se); ans[i] = max(ans[i], tmp - h.fi); } for(int i = 1; i <= n; i++) cout << ans[i] << endl; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 8532 KB | Output is correct |
2 | Correct | 5 ms | 8532 KB | Output is correct |
3 | Correct | 5 ms | 8520 KB | Output is correct |
4 | Correct | 4 ms | 8532 KB | Output is correct |
5 | Correct | 6 ms | 8532 KB | Output is correct |
6 | Incorrect | 11 ms | 8532 KB | Output isn't correct |
7 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 8532 KB | Output is correct |
2 | Correct | 5 ms | 8532 KB | Output is correct |
3 | Correct | 5 ms | 8520 KB | Output is correct |
4 | Correct | 4 ms | 8532 KB | Output is correct |
5 | Correct | 6 ms | 8532 KB | Output is correct |
6 | Incorrect | 11 ms | 8532 KB | Output isn't correct |
7 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 8532 KB | Output is correct |
2 | Incorrect | 2997 ms | 16548 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 8532 KB | Output is correct |
2 | Incorrect | 2997 ms | 16548 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 8532 KB | Output is correct |
2 | Incorrect | 2997 ms | 16548 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 8532 KB | Output is correct |
2 | Incorrect | 2997 ms | 16548 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 8532 KB | Output is correct |
2 | Correct | 5 ms | 8532 KB | Output is correct |
3 | Correct | 5 ms | 8520 KB | Output is correct |
4 | Correct | 4 ms | 8532 KB | Output is correct |
5 | Correct | 6 ms | 8532 KB | Output is correct |
6 | Incorrect | 11 ms | 8532 KB | Output isn't correct |
7 | Halted | 0 ms | 0 KB | - |