Submission #921569

#TimeUsernameProblemLanguageResultExecution timeMemory
921569vjudge1Council (JOI23_council)C++17
100 / 100
914 ms57696 KiB
// I stand with PALESTINE //#pragma GCC optimize("Ofast,O3") //#pragma GCC target("avx,avx2") #include "bits/stdc++.h" using namespace std; using ll = long long; int btc(int a) { return __builtin_popcount(a); } void solve() { int n, m; cin >> n >> m; vector a(n, vector(m, 0)); vector<pair<int, int>> cnt(1 << m, make_pair(n, n)); vector<int> bta(n + 1), have(m); auto upd = [&](int bt, int i) -> void { if (btc(bta[cnt[bt].first] & bt) < btc(bta[i] & bt)) cnt[bt] = make_pair(i, cnt[bt].first); else if (cnt[bt].first != i and btc(bta[cnt[bt].second] & bt) < btc(bta[i] & bt)) cnt[bt].second = i; }; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> a[i][j]; if (!a[i][j]) bta[i] |= 1 << j; have[j] += a[i][j]; } upd(bta[i], i); } for (int bt = (1 << m) - 1; bt >= 0; bt--) { for (int j = 0; j < m; j++) { if (bt & (1 << j)) continue; upd(bt, cnt[bt | (1 << j)].first); upd(bt, cnt[bt | (1 << j)].second); } } for (int bt = 0; bt < (1 << m); bt++) { for (int j = 0; j < m; j++) { if (bt & (1 << j)) continue; upd(bt | (1 << j), cnt[bt].first); upd(bt | (1 << j), cnt[bt].second); } } for (int i = 0; i < n; i++) { int ans = 0, bt = 0; for (int j = 0; j < m; j++) { have[j] -= a[i][j]; if (have[j] != n / 2) ans += have[j] > n / 2; else bt |= 1 << j; have[j] += a[i][j]; } // int mx = 0; // for (int j = 0; j < n; j++) { // if (i == j) continue; // mx = max(mx, __builtin_popcount(bta[j] & bt)); // } // ans += mx; // cout << ans << ' ' << bta[i] << ' ' << bt << ' ' << cnt[bt].first << ' ' << cnt[bt].second << endl; // cout << ans << ' ' << bta[i] << ' ' << __builtin_popcount(bta[i]) << endl; if (i == cnt[bt].first) ans += btc(bta[cnt[bt].second] & bt); else ans += btc( bta[cnt[bt].first] & bt); cout << ans << '\n'; } } int main() { cin.tie(0)->sync_with_stdio(false); #ifdef sunnatov freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif int q = 1; // cin >> q; while (q--) { solve(); cout << '\n'; } }
#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...