Submission #1211085

#TimeUsernameProblemLanguageResultExecution timeMemory
1211085dima2101Council (JOI23_council)C++20
100 / 100
731 ms38964 KiB
#include <bits/stdc++.h> #define int long long struct Node { int first_max; int ind1; int second_max; int ind2; Node() { first_max = 0; ind1 = -1; second_max = 0; ind2 = -1; } }; Node relax(Node now, std::pair<int, int> be) { if (now.ind1 == -1 && be.second != now.ind1) { now.first_max = be.first; now.ind1 = be.second; } else if (now.first_max < be.first) { if (be.second != now.ind1) { now.second_max = now.first_max; now.ind2 = now.ind1; } now.first_max = be.first; now.ind1 = be.second; } else if (now.ind2 == -1 && be.second != now.ind1) { now.second_max = be.first; now.ind2 = be.second; } else if (now.second_max < be.first && be.second != now.ind1) { now.second_max = be.first; now.ind2 = be.second; } return now; } signed main() { std::ios::sync_with_stdio(false); std::cin.tie(0); int n, m; std::cin >> n >> m; std::vector<int> all(n); std::vector<Node> dp((1 << m)); for (int i = 0; i < n; i++) { int now = 0; for (int j = 0; j < m; j++) { int help; std::cin >> help; if (help == 1) { now |= (1 << j); } } all[i] = now; dp[now] = relax(dp[now], std::make_pair(m - __builtin_popcount(now), i)); } for (int i = 0; i < (1 << m); i++) { for (int j = 0; j < m; j++) { if (!((i >> j) & 1)) { int help = i; help |= (1 << j); Node need = dp[i]; need.first_max--; need.second_max--; dp[help] = relax(dp[help], std::make_pair(need.first_max, need.ind1)); dp[help] = relax(dp[help], std::make_pair(need.second_max, need.ind2)); } } } for (int i = (1 << m) - 1; i >= 0; i--) { for (int j = 0; j < m; j++) { if ((i >> j) & 1) { int help = i; help ^= (1 << j); dp[help] = relax(dp[help], std::make_pair(dp[i].first_max, dp[i].ind1)); dp[help] = relax(dp[help], std::make_pair(dp[i].second_max, dp[i].ind2)); } } } std::vector<int> type(m); for (int i = 0; i < m; i++) { int cnt = 0; for (int j = 0; j < n; j++) { if ((all[j] >> i) & 1) { cnt++; } else { cnt--; } } if (cnt < -1) { type[i] = -2; } else if (cnt == -1) { type[i] = -1; } else if (cnt == 0) { type[i] = -1; } else if (cnt == 1 || cnt == 2) { type[i] = 0; } else { type[i] = 1; } // std::cout << i << ' ' << type[i] << std::endl; } std::vector<int> ans(n); for (int i = 0; i < n; i++) { int ind = (1 << m) - 1; int cnt = 0; for (int j = 0; j < m; j++) { if (type[j] == 1) { cnt++; continue; } if ((all[i] >> j) & 1) { if (type[j] == 0) { ind ^= (1 << j); } } else { if (type[j] == 0) { cnt++; } if (type[j] == -1) { ind ^= (1 << j); } } } // for (int j = 0; j < m; j++) // { // if ((ind >> j) & 1) // { // std::cout << "0"; // } // else // { // std::cout << "1"; // } // } // std::cout << std::endl; // std::cout << ind << ' ' << cnt << ' ' << dp[ind].first_max << std::endl; if (dp[ind].ind1 == i) { ans[i] = cnt + dp[ind].second_max; } else { ans[i] = cnt + dp[ind].first_max; } } for (int i = 0; i < n; i++) { std::cout << ans[i] << std::endl; } 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...