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<bits/stdc++.h>
using namespace std;
vector<pair<int,int>> bruh((1 << 20),{-1,-1});
vector<pair<int,int>> dp((1 << 20),{-1,-1});
vector<pair<int,int>> idk((1 << 20),{-1,-1});
vector<pair<int,int>> pos((1 << 20),{-1,-1});
void merge(int x, int c, int d) {
if(c == -1) {
return;
}
if(pos[x].first == c) {
idk[x] = {max(d,idk[x].first),idk[x].second};
}
else if(pos[x].second == c) {
idk[x] = {idk[x].first,max(idk[x].second,d)};
}
else {
if(d > idk[x].first) {
idk[x] = {d,idk[x].first};
pos[x] = {c,pos[x].first};
}
else if(d > idk[x].second) {
idk[x] = {idk[x].first,d};
pos[x] = {pos[x].first,c};
}
}
}
pair<int,int> calc(pair<int,int> a, int b) {
if(b == -1) {
return a;
}
if(a.first == -1) {
return {b,-1};
}
else if(a.second == -1 && a.first != b) {
return {a.first,b};
}
return a;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n,m,a;
cin >> n >> m;
vector<int> br(m);
vector<int> haha(n);
for(int i = 0; i < n; i++) {
int c = 0;
for(int j = 0; j < m; j++) {
cin >> a;
br[j]+=a;
c+=a*(1 << j);
}
bruh[c] = calc(bruh[c],i);
haha[i] = c;
}
for(int i = 0; i < (1 << m); i++) {
dp[i] = bruh[i];
for(int j = 0; j < m; j++) {
if((1 << j)&i) {
dp[i] = calc(dp[i],dp[i-(1 << j)].first);
dp[i] = calc(dp[i],dp[i-(1 << j)].second);
}
}
}
for(int i = (1 << m)-1; i >= 0; i--) {
int br = 0;
for(int j = 0; j < m; j++) {
if(((1 << j)&i) == 0) {
br++;
}
}
if(dp[i].first != -1) {
merge(i,dp[i].first,br);
}
if(dp[i].second != -1) {
merge(i,dp[i].second,br);
}
for(int j = 0; j < m; j++) {
if(((1 << j)&i) == 0) {
merge(i,pos[i+(1 << j)].first,idk[i+(1 << j)].first);
merge(i,pos[i+(1 << j)].second,idk[i+(1 << j)].second);
}
}
}
for(int i = 0; i < n; i++) {
int x = 0,ans = 0;
for(int j = 0; j < m; j++) {
int c = br[j];
if((1 << j)&haha[i]) {
c--;
}
if(c == n/2) {
x+=(1 << j);
}
if(c > n/2) {
ans++;
}
}
x = (1 << m)-1-x;
if(pos[x].first == i) {
cout << ans+idk[x].second << "\n";
}
else {
cout << ans+idk[x].first << "\n";
}
}
return 0;
}
# | 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... |