Submission #1014188

#TimeUsernameProblemLanguageResultExecution timeMemory
1014188PacybwoahCouncil (JOI23_council)C++17
100 / 100
1085 ms47112 KiB
#include<iostream> #include<vector> #include<cassert> #include<utility> using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; vector<int> vec(n), cnt(1 << m), popcnt(1 << m); vector<int> res(m); vector<pair<int, int>> dp(1 << m, make_pair(-1, -1)); for(int i = 0; i < n; i++){ int tmp; for(int j = 0; j < m; j++){ cin >> tmp; vec[i] += (tmp << j); res[j] += tmp; } cnt[vec[i]]++; if(dp[((1 << m) - 1) ^ vec[i]].first != -1) dp[((1 << m) - 1) ^ vec[i]].second = i; else dp[((1 << m) - 1) ^ vec[i]].first = i; } for(int i = 0; i < m; i++){ for(int j = 0; j < (1 << m); j++){ if((1 << i) & j){ popcnt[j]++; if(dp[j ^ (1 << i)].first == -1){ dp[j ^ (1 << i)].first = dp[j].first; dp[j ^ (1 << i)].second = dp[j].second; } else if(dp[j ^ (1 << i)].second == -1){ if(dp[j ^ (1 << i)].first != dp[j].first) dp[j ^ (1 << i)].second = dp[j].first; else dp[j ^ (1 << i)].second = dp[j].second; } } } } vector<pair<pair<int, int>, pair<int, int>> > dp2(1 << m, make_pair(make_pair(0, 0), make_pair(0, 0))); for(int i = 0; i < (1 << m); i++){ if(dp[i].first != -1){ dp2[i].first.first = popcnt[i]; dp2[i].first.second = dp[i].first + 1; } if(dp[i].second != -1){ dp2[i].second.first = popcnt[i]; dp2[i].second.second = dp[i].second + 1; } } auto pull = [&](pair<pair<int, int>, pair<int, int>> &a, pair<pair<int, int>, pair<int, int>> &b){ vector<int> poss, pos; if(b.first.second != a.first.second && b.first.second != a.second.second) poss.push_back(b.first.second), pos.push_back(b.first.first); if(b.second.second != a.first.second && b.second.second != a.second.second) poss.push_back(b.second.second), pos.push_back(b.second.first); while((int)poss.size() < 2) poss.push_back(0), pos.push_back(0); if(pos[0] >= a.first.first){ if(pos[1] >= a.first.first) a.second = make_pair(pos[1], poss[1]); else a.second = a.first; a.first = make_pair(pos[0], poss[0]); } else{ if(pos[0] > a.second.first) a.second = make_pair(pos[0], poss[0]); } }; for(int i = 0; i < m; i++){ for(int j = 0; j < (1 << m); j++){ if((1 << i) & j){ pull(dp2[j], dp2[j ^ (1 << i)]); } } } int maj = n / 2; for(auto &x: vec){ int crit = 0, uncrit = 0; for(int i = 0; i < m; i++){ if(x & (1 << i)){ if(res[i] == maj + 1) crit += (1 << i); else if(res[i] > maj + 1) uncrit++; } else{ if(res[i] == maj) crit += (1 << i); else if(res[i] > maj) uncrit++; } } int mask = ((1 << m) - 1) ^ x; mask = (mask & crit); if(popcnt[mask] == dp2[crit].first.first) cout << dp2[crit].second.first + uncrit << "\n"; else cout << dp2[crit].first.first + uncrit << "\n"; //cout << dp2[crit].first.first << " " << dp2[crit].second.first << "\n"; } } // g++ -std=c++17 pB.cpp -Wall -Wextra -Wshadow -fsanitize=undefined -fsanitize=address -o run
#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...