This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |