Submission #919971

#TimeUsernameProblemLanguageResultExecution timeMemory
919971OAleksaCouncil (JOI23_council)C++14
78 / 100
4027 ms36392 KiB
#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]; pair<pair<int, int>, pair<int, int>> bst[1030][1030]; signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int tt = 1; //cin >> tt; while (tt--) { cin >> n >> m; for (int i = 1;i <= n;i++) { for (int j = 0;j < m;j++) { int x; cin >> x; if (x > 0) { a[i] += (1 << j); cnt[j]++; } } } int k = (m + 1) / 2; for (int i = 0;i < (1 << (m - k));i++) { for (int j = 0;j < (1 << k);j++) bst[i][j] = {{(1 << m) - 1, m + 1}, {(1 << m) - 1, m + 1}}; } for (int i = 0;i < (1 << k);i++) { for (int j = 1;j <= n;j++) { int x = (i << (m - k)); int pr = (a[j] & ((1 << (m - k)) - 1)); int k = __builtin_popcount(a[j] & x); if (k <= bst[pr][i].f.s) { bst[pr][i].s = bst[pr][i].f; bst[pr][i].f = {a[j], k}; } else if (k <= bst[pr][i].s.s) bst[pr][i].s = {a[j], k}; } } //sufix duzine k, prefix duzine m - k for (int i = 1;i <= n;i++) { int b = 0, ans = 0, c = 0; for (int j = 0;j < m;j++) { t[j] = cnt[j]; if (a[i] & (1 << j)) t[j]--; if (t[j] == n / 2) b += (1 << j), c++; else if (t[j] > n / 2) ans++; } int suf = (b >> (m - k)), s = c; for (int j = 0;j < (1 << (m - k));j++) { int g = __builtin_popcount(b & j); if (a[i] != bst[j][suf].f.f) s = min(s, bst[j][suf].f.s + g); else s = min(s, bst[j][suf].s.s + g); } ans += c - s; cout << ans << '\n'; } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...