| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 920666 |
2024-02-02T21:37:12 Z |
OAleksa |
Council (JOI23_council) |
C++14 |
|
263 ms |
43864 KB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define f first
#define s second
const int N = 3e5 + 69;
const int M = 21;
int a[N], cnt[M], n, m;
int t[M], k, gas, pr, suf, bt, b, ans, c, s, x;
vector<int> g[1030];
pair<pair<int, int>, pair<int, int>> bst[1030][1030];
int kurac[1030][1030];
signed main() {
int tt = 1;
//cin >> tt;
while (tt--) {
cin >> n >> m;
for (int i = 1;i <= n;i++) {
for (int j = 0;j < m;j++) {
scanf("%d", &x);
if (x > 0) {
a[i] |= (1 << j);
cnt[j]++;
}
}
pr = (a[i] & ((1 << (m - k)) - 1));
suf = (a[i] >> (m - k));
//g[pr].push_back(suf);
}
int k = (m + 1) / 2;
for (int i = 0;i < (1 << k);i++) {
for (int j = 0;j < (1 << (m - k));j++) {
kurac[i][j] = __builtin_popcount(i & j);
bst[i][j] = {{(1 << m) - 1, m + 1}, {(1 << m) - 1, m + 1}};
}
}
for (int j = 1;j <= n;j++) {
pr = (a[j] & ((1 << (m - k)) - 1));
gas = (a[j] >> (m - k));
for (int i = 0;i < (1 << k);i++) {
bt = kurac[gas][i];
if (bt < bst[pr][i].f.s) {
bst[pr][i].s = bst[pr][i].f;
bst[pr][i].f = {a[j], bt};
}
else if (bt < bst[pr][i].s.s)
bst[pr][i].s = {a[j], bt};
}
}
//sufix duzine k, prefix duzine m - k
for (int i = 1;i <= n;i++) {
b = ans = c = 0;
for (int j = 0;j < m;j++) {
gas = cnt[j] - ((a[i] & (1 << j)) > 0);
if (gas == (n >> 1)) {
b |= (1 << j);
c++;
}
else if (gas > (n >> 1))
ans++;
}
suf = (b >> (m - k)), s = c;
pr = (b & ((1 << (m - k)) - 1));
for (int j = 0;j < (1 << (m - k));j++) {
if (a[i] != bst[j][suf].f.f)
s = min(s, bst[j][suf].f.s + kurac[pr][j]);
else
s = min(s, bst[j][suf].s.s + kurac[pr][j]);
}
ans += c - s;
printf("%d\n", ans);
}
}
return 0;
}
Compilation message
council.cpp: In function 'int main()':
council.cpp:20:14: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
20 | scanf("%d", &x);
| ~^ ~~
| | |
| | long long int*
| int*
| %lld
council.cpp:71:14: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
71 | printf("%d\n", ans);
| ~^ ~~~
| | |
| int long long int
| %lld
council.cpp:20:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
20 | scanf("%d", &x);
| ~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 2 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 3 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 5 |
Correct |
8 ms |
43864 KB |
Output is correct |
| 6 |
Correct |
9 ms |
43612 KB |
Output is correct |
| 7 |
Correct |
8 ms |
43612 KB |
Output is correct |
| 8 |
Correct |
8 ms |
43612 KB |
Output is correct |
| 9 |
Correct |
9 ms |
43612 KB |
Output is correct |
| 10 |
Correct |
7 ms |
43612 KB |
Output is correct |
| 11 |
Correct |
8 ms |
43612 KB |
Output is correct |
| 12 |
Correct |
11 ms |
43612 KB |
Output is correct |
| 13 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 14 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 15 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 16 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 17 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 18 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 19 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 20 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 21 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 22 |
Correct |
2 ms |
8536 KB |
Output is correct |
| 23 |
Incorrect |
1 ms |
6492 KB |
Output isn't correct |
| 24 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 2 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 3 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 5 |
Correct |
8 ms |
43864 KB |
Output is correct |
| 6 |
Correct |
9 ms |
43612 KB |
Output is correct |
| 7 |
Correct |
8 ms |
43612 KB |
Output is correct |
| 8 |
Correct |
8 ms |
43612 KB |
Output is correct |
| 9 |
Correct |
9 ms |
43612 KB |
Output is correct |
| 10 |
Correct |
7 ms |
43612 KB |
Output is correct |
| 11 |
Correct |
8 ms |
43612 KB |
Output is correct |
| 12 |
Correct |
11 ms |
43612 KB |
Output is correct |
| 13 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 14 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 15 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 16 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 17 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 18 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 19 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 20 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 21 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 22 |
Correct |
2 ms |
8536 KB |
Output is correct |
| 23 |
Incorrect |
1 ms |
6492 KB |
Output isn't correct |
| 24 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
64 ms |
5712 KB |
Output is correct |
| 3 |
Correct |
68 ms |
4944 KB |
Output is correct |
| 4 |
Correct |
52 ms |
5712 KB |
Output is correct |
| 5 |
Correct |
69 ms |
5672 KB |
Output is correct |
| 6 |
Correct |
53 ms |
5556 KB |
Output is correct |
| 7 |
Correct |
71 ms |
5556 KB |
Output is correct |
| 8 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 9 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 10 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 11 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 12 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 13 |
Correct |
1 ms |
4492 KB |
Output is correct |
| 14 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 15 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 16 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 17 |
Correct |
1 ms |
4444 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
64 ms |
5712 KB |
Output is correct |
| 3 |
Correct |
68 ms |
4944 KB |
Output is correct |
| 4 |
Correct |
52 ms |
5712 KB |
Output is correct |
| 5 |
Correct |
69 ms |
5672 KB |
Output is correct |
| 6 |
Correct |
53 ms |
5556 KB |
Output is correct |
| 7 |
Correct |
71 ms |
5556 KB |
Output is correct |
| 8 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 9 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 10 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 11 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 12 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 13 |
Correct |
1 ms |
4492 KB |
Output is correct |
| 14 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 15 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 16 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 17 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 18 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 19 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 20 |
Correct |
263 ms |
9888 KB |
Output is correct |
| 21 |
Incorrect |
263 ms |
9812 KB |
Output isn't correct |
| 22 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
64 ms |
5712 KB |
Output is correct |
| 3 |
Correct |
68 ms |
4944 KB |
Output is correct |
| 4 |
Correct |
52 ms |
5712 KB |
Output is correct |
| 5 |
Correct |
69 ms |
5672 KB |
Output is correct |
| 6 |
Correct |
53 ms |
5556 KB |
Output is correct |
| 7 |
Correct |
71 ms |
5556 KB |
Output is correct |
| 8 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 9 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 10 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 11 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 12 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 13 |
Correct |
1 ms |
4492 KB |
Output is correct |
| 14 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 15 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 16 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 17 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 18 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 19 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 20 |
Correct |
263 ms |
9888 KB |
Output is correct |
| 21 |
Incorrect |
263 ms |
9812 KB |
Output isn't correct |
| 22 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
64 ms |
5712 KB |
Output is correct |
| 3 |
Correct |
68 ms |
4944 KB |
Output is correct |
| 4 |
Correct |
52 ms |
5712 KB |
Output is correct |
| 5 |
Correct |
69 ms |
5672 KB |
Output is correct |
| 6 |
Correct |
53 ms |
5556 KB |
Output is correct |
| 7 |
Correct |
71 ms |
5556 KB |
Output is correct |
| 8 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 9 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 10 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 11 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 12 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 13 |
Correct |
1 ms |
4492 KB |
Output is correct |
| 14 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 15 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 16 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 17 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 18 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 19 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 20 |
Correct |
263 ms |
9888 KB |
Output is correct |
| 21 |
Incorrect |
263 ms |
9812 KB |
Output isn't correct |
| 22 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 2 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 3 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 5 |
Correct |
8 ms |
43864 KB |
Output is correct |
| 6 |
Correct |
9 ms |
43612 KB |
Output is correct |
| 7 |
Correct |
8 ms |
43612 KB |
Output is correct |
| 8 |
Correct |
8 ms |
43612 KB |
Output is correct |
| 9 |
Correct |
9 ms |
43612 KB |
Output is correct |
| 10 |
Correct |
7 ms |
43612 KB |
Output is correct |
| 11 |
Correct |
8 ms |
43612 KB |
Output is correct |
| 12 |
Correct |
11 ms |
43612 KB |
Output is correct |
| 13 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 14 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 15 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 16 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 17 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 18 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 19 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 20 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 21 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 22 |
Correct |
2 ms |
8536 KB |
Output is correct |
| 23 |
Incorrect |
1 ms |
6492 KB |
Output isn't correct |
| 24 |
Halted |
0 ms |
0 KB |
- |
