# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
736074 | 2023-05-05T07:53:02 Z | nguyentunglam | Council (JOI23_council) | C++17 | 339 ms | 29260 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 = 1e5 + 10, M = 20; bool a[N][M]; int f[2][1 << M], g[N], bit[1 << M], vote[M]; pair<int, int> dp[2][1 << M]; void add(int mask, int idx) { if (idx == -1) return; f[1][mask] = f[0][mask]; f[0][mask] = idx; } void up(int mask, pair<int, int> tmp) { if (tmp.se == dp[1][mask].se || tmp.se == dp[0][mask].se) return; dp[1][mask] = max(dp[1][mask], tmp); if (dp[0][mask] < dp[1][mask]) swap(dp[0][mask], dp[1][mask]); } 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); } int n, m; cin >> n >> m; for(int i = 0; i < (1 << m); i++) { bit[i] = __builtin_popcount(i); f[0][i] = f[1][i] = -1; } 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 j = 0; j < m; j++) if (!a[i][j]) g[i] |= (1 << j); add(g[i], i); } for(int i = 0; i < m; i++) for(int mask = (1 << m) - 1; mask >= 0; mask--) { if (!(mask >> i & 1)) { add(mask, f[0][mask | (1 << i)]); add(mask, f[1][mask | (1 << i)]); } } for(int i = 0; i < m; i++) for(int mask = 0; mask < (1 << m); mask++) { if (f[0][mask] != -1) up(mask, make_pair(bit[mask], f[0][mask])); if (f[1][mask] != -1) up(mask, make_pair(bit[mask], f[1][mask])); if (mask >> i & 1) { up(mask, dp[0][mask ^ (1 << i)]); up(mask, dp[1][mask ^ (1 << i)]); } } for(int i = 1; i <= n; i++) { int mask = 0, ans = 0; for(int j = 0; j < m; j++) { vote[j] -= a[i][j]; if (vote[j] == n / 2) mask |= (1 << j); if (vote[j] > n / 2) ans++; vote[j] += a[i][j]; } if (dp[0][mask].se == i) cout << ans + dp[1][mask].fi; else cout << ans + dp[0][mask].fi; cout << endl; } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
2 | Correct | 1 ms | 468 KB | Output is correct |
3 | Correct | 0 ms | 340 KB | Output is correct |
4 | Correct | 0 ms | 340 KB | Output is correct |
5 | Correct | 196 ms | 29056 KB | Output is correct |
6 | Correct | 112 ms | 29004 KB | Output is correct |
7 | Correct | 129 ms | 28956 KB | Output is correct |
8 | Correct | 148 ms | 29156 KB | Output is correct |
9 | Correct | 265 ms | 29028 KB | Output is correct |
10 | Correct | 130 ms | 29032 KB | Output is correct |
11 | Correct | 154 ms | 29044 KB | Output is correct |
12 | Correct | 263 ms | 29004 KB | Output is correct |
13 | Correct | 0 ms | 340 KB | Output is correct |
14 | Correct | 0 ms | 336 KB | Output is correct |
15 | Correct | 0 ms | 340 KB | Output is correct |
16 | Correct | 0 ms | 340 KB | Output is correct |
17 | Correct | 0 ms | 340 KB | Output is correct |
18 | Correct | 0 ms | 340 KB | Output is correct |
19 | Correct | 0 ms | 340 KB | Output is correct |
20 | Correct | 1 ms | 332 KB | Output is correct |
21 | Correct | 0 ms | 340 KB | Output is correct |
22 | Correct | 0 ms | 340 KB | Output is correct |
23 | Correct | 0 ms | 340 KB | Output is correct |
24 | Correct | 0 ms | 340 KB | Output is correct |
25 | Correct | 0 ms | 340 KB | Output is correct |
26 | Correct | 0 ms | 340 KB | Output is correct |
27 | Correct | 0 ms | 340 KB | Output is correct |
28 | Correct | 1 ms | 340 KB | Output is correct |
29 | Correct | 1 ms | 340 KB | Output is correct |
30 | Correct | 1 ms | 340 KB | Output is correct |
31 | Correct | 1 ms | 412 KB | Output is correct |
32 | Correct | 0 ms | 340 KB | Output is correct |
33 | Correct | 1 ms | 340 KB | Output is correct |
34 | Correct | 0 ms | 340 KB | Output is correct |
35 | Correct | 0 ms | 340 KB | Output is correct |
36 | Correct | 1 ms | 340 KB | Output is correct |
37 | Correct | 1 ms | 324 KB | Output is correct |
38 | Correct | 1 ms | 340 KB | Output is correct |
39 | Correct | 1 ms | 340 KB | Output is correct |
40 | Correct | 1 ms | 340 KB | Output is correct |
41 | Correct | 3 ms | 724 KB | Output is correct |
42 | Correct | 2 ms | 724 KB | Output is correct |
43 | Correct | 3 ms | 724 KB | Output is correct |
44 | Correct | 2 ms | 724 KB | Output is correct |
45 | Correct | 3 ms | 724 KB | Output is correct |
46 | Correct | 23 ms | 3916 KB | Output is correct |
47 | Correct | 17 ms | 3924 KB | Output is correct |
48 | Correct | 19 ms | 3968 KB | Output is correct |
49 | Correct | 15 ms | 3876 KB | Output is correct |
50 | Correct | 19 ms | 3964 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
2 | Correct | 1 ms | 468 KB | Output is correct |
3 | Correct | 0 ms | 340 KB | Output is correct |
4 | Correct | 0 ms | 340 KB | Output is correct |
5 | Correct | 196 ms | 29056 KB | Output is correct |
6 | Correct | 112 ms | 29004 KB | Output is correct |
7 | Correct | 129 ms | 28956 KB | Output is correct |
8 | Correct | 148 ms | 29156 KB | Output is correct |
9 | Correct | 265 ms | 29028 KB | Output is correct |
10 | Correct | 130 ms | 29032 KB | Output is correct |
11 | Correct | 154 ms | 29044 KB | Output is correct |
12 | Correct | 263 ms | 29004 KB | Output is correct |
13 | Correct | 0 ms | 340 KB | Output is correct |
14 | Correct | 0 ms | 336 KB | Output is correct |
15 | Correct | 0 ms | 340 KB | Output is correct |
16 | Correct | 0 ms | 340 KB | Output is correct |
17 | Correct | 0 ms | 340 KB | Output is correct |
18 | Correct | 0 ms | 340 KB | Output is correct |
19 | Correct | 0 ms | 340 KB | Output is correct |
20 | Correct | 1 ms | 332 KB | Output is correct |
21 | Correct | 0 ms | 340 KB | Output is correct |
22 | Correct | 0 ms | 340 KB | Output is correct |
23 | Correct | 0 ms | 340 KB | Output is correct |
24 | Correct | 0 ms | 340 KB | Output is correct |
25 | Correct | 0 ms | 340 KB | Output is correct |
26 | Correct | 0 ms | 340 KB | Output is correct |
27 | Correct | 0 ms | 340 KB | Output is correct |
28 | Correct | 1 ms | 340 KB | Output is correct |
29 | Correct | 1 ms | 340 KB | Output is correct |
30 | Correct | 1 ms | 340 KB | Output is correct |
31 | Correct | 1 ms | 412 KB | Output is correct |
32 | Correct | 0 ms | 340 KB | Output is correct |
33 | Correct | 1 ms | 340 KB | Output is correct |
34 | Correct | 0 ms | 340 KB | Output is correct |
35 | Correct | 0 ms | 340 KB | Output is correct |
36 | Correct | 1 ms | 340 KB | Output is correct |
37 | Correct | 1 ms | 324 KB | Output is correct |
38 | Correct | 1 ms | 340 KB | Output is correct |
39 | Correct | 1 ms | 340 KB | Output is correct |
40 | Correct | 1 ms | 340 KB | Output is correct |
41 | Correct | 3 ms | 724 KB | Output is correct |
42 | Correct | 2 ms | 724 KB | Output is correct |
43 | Correct | 3 ms | 724 KB | Output is correct |
44 | Correct | 2 ms | 724 KB | Output is correct |
45 | Correct | 3 ms | 724 KB | Output is correct |
46 | Correct | 23 ms | 3916 KB | Output is correct |
47 | Correct | 17 ms | 3924 KB | Output is correct |
48 | Correct | 19 ms | 3968 KB | Output is correct |
49 | Correct | 15 ms | 3876 KB | Output is correct |
50 | Correct | 19 ms | 3964 KB | Output is correct |
51 | Correct | 117 ms | 29044 KB | Output is correct |
52 | Correct | 270 ms | 29132 KB | Output is correct |
53 | Correct | 309 ms | 29244 KB | Output is correct |
54 | Correct | 339 ms | 29260 KB | Output is correct |
55 | Correct | 1 ms | 340 KB | Output is correct |
56 | Correct | 48 ms | 4052 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 340 KB | Output is correct |
2 | Runtime error | 17 ms | 4428 KB | Execution killed with signal 11 |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 340 KB | Output is correct |
2 | Runtime error | 17 ms | 4428 KB | Execution killed with signal 11 |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 340 KB | Output is correct |
2 | Runtime error | 17 ms | 4428 KB | Execution killed with signal 11 |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 340 KB | Output is correct |
2 | Runtime error | 17 ms | 4428 KB | Execution killed with signal 11 |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
2 | Correct | 1 ms | 468 KB | Output is correct |
3 | Correct | 0 ms | 340 KB | Output is correct |
4 | Correct | 0 ms | 340 KB | Output is correct |
5 | Correct | 196 ms | 29056 KB | Output is correct |
6 | Correct | 112 ms | 29004 KB | Output is correct |
7 | Correct | 129 ms | 28956 KB | Output is correct |
8 | Correct | 148 ms | 29156 KB | Output is correct |
9 | Correct | 265 ms | 29028 KB | Output is correct |
10 | Correct | 130 ms | 29032 KB | Output is correct |
11 | Correct | 154 ms | 29044 KB | Output is correct |
12 | Correct | 263 ms | 29004 KB | Output is correct |
13 | Correct | 0 ms | 340 KB | Output is correct |
14 | Correct | 0 ms | 336 KB | Output is correct |
15 | Correct | 0 ms | 340 KB | Output is correct |
16 | Correct | 0 ms | 340 KB | Output is correct |
17 | Correct | 0 ms | 340 KB | Output is correct |
18 | Correct | 0 ms | 340 KB | Output is correct |
19 | Correct | 0 ms | 340 KB | Output is correct |
20 | Correct | 1 ms | 332 KB | Output is correct |
21 | Correct | 0 ms | 340 KB | Output is correct |
22 | Correct | 0 ms | 340 KB | Output is correct |
23 | Correct | 0 ms | 340 KB | Output is correct |
24 | Correct | 0 ms | 340 KB | Output is correct |
25 | Correct | 0 ms | 340 KB | Output is correct |
26 | Correct | 0 ms | 340 KB | Output is correct |
27 | Correct | 0 ms | 340 KB | Output is correct |
28 | Correct | 1 ms | 340 KB | Output is correct |
29 | Correct | 1 ms | 340 KB | Output is correct |
30 | Correct | 1 ms | 340 KB | Output is correct |
31 | Correct | 1 ms | 412 KB | Output is correct |
32 | Correct | 0 ms | 340 KB | Output is correct |
33 | Correct | 1 ms | 340 KB | Output is correct |
34 | Correct | 0 ms | 340 KB | Output is correct |
35 | Correct | 0 ms | 340 KB | Output is correct |
36 | Correct | 1 ms | 340 KB | Output is correct |
37 | Correct | 1 ms | 324 KB | Output is correct |
38 | Correct | 1 ms | 340 KB | Output is correct |
39 | Correct | 1 ms | 340 KB | Output is correct |
40 | Correct | 1 ms | 340 KB | Output is correct |
41 | Correct | 3 ms | 724 KB | Output is correct |
42 | Correct | 2 ms | 724 KB | Output is correct |
43 | Correct | 3 ms | 724 KB | Output is correct |
44 | Correct | 2 ms | 724 KB | Output is correct |
45 | Correct | 3 ms | 724 KB | Output is correct |
46 | Correct | 23 ms | 3916 KB | Output is correct |
47 | Correct | 17 ms | 3924 KB | Output is correct |
48 | Correct | 19 ms | 3968 KB | Output is correct |
49 | Correct | 15 ms | 3876 KB | Output is correct |
50 | Correct | 19 ms | 3964 KB | Output is correct |
51 | Correct | 117 ms | 29044 KB | Output is correct |
52 | Correct | 270 ms | 29132 KB | Output is correct |
53 | Correct | 309 ms | 29244 KB | Output is correct |
54 | Correct | 339 ms | 29260 KB | Output is correct |
55 | Correct | 1 ms | 340 KB | Output is correct |
56 | Correct | 48 ms | 4052 KB | Output is correct |
57 | Correct | 0 ms | 340 KB | Output is correct |
58 | Runtime error | 17 ms | 4428 KB | Execution killed with signal 11 |
59 | Halted | 0 ms | 0 KB | - |