Submission #920665

#TimeUsernameProblemLanguageResultExecution timeMemory
920665OAleksaCouncil (JOI23_council)C++14
6 / 100
242 ms13904 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], 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 (stderr)

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 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...