제출 #1147399

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1147399		Hamed_Ghaffari	Council (JOI23_council)	C++20	100 / 100	347 ms	18908 KiB

council

#include<bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;
using ppp = pair<pii, pii>;

#define X first
#define Y second
#define maxs(a,b) (a=max(a,b))

const int MXN = 3e5+3;
const int MXM = 20;

int n, m, cnt[MXM];
int a[MXN];

ppp dp[1<<MXM];

void upd(ppp &x, pii y) {
  if(y.X>x.X.X) {
    if(x.X.Y!=y.Y) {
      x.Y = x.X;
    }
    x.X = y;
  }
  else if(y.X>x.Y.X && y.Y!=x.X.Y)
    x.Y = y;
}
void upd(ppp &x, ppp y) {
  upd(x, y.X);
  upd(x, y.Y);
}

int32_t main() {
  cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
  cin >> n >> m;
  for(int msk=0; msk<(1<<m); msk++) dp[msk] = {{-1,-1}, {-1,-1}};
  for(int i=0; i<n; i++) {
    for(int j=0,x; j<m; j++) {
      cin >> x;
      if(x) {
        a[i] ^= 1<<j;
        cnt[j]++;
      }
    }
    upd(dp[((1<<m)-1)^a[i]], {__builtin_popcount(((1<<m)-1)^a[i]), i});
  }
  for(int i=0; i<m; i++)
    for(int msk=0; msk<(1<<m); msk++)
      if(!(msk>>i&1))
        upd(dp[msk], {{dp[msk^(1<<i)].X.X-1, dp[msk^(1<<i)].X.Y},
                      {dp[msk^(1<<i)].Y.X-1, dp[msk^(1<<i)].Y.Y}});
  for(int i=0; i<m; i++)
    for(int msk=0; msk<(1<<m); msk++)
      if(msk>>i&1)
        upd(dp[msk], dp[msk^(1<<i)]);
  for(int msk=0; msk<(1<<m); msk++) {
    if(dp[msk].X.Y!=-1) dp[msk].X.X = __builtin_popcount(msk) - dp[msk].X.X;
    if(dp[msk].Y.Y!=-1) dp[msk].Y.X = __builtin_popcount(msk) - dp[msk].Y.X;
  }
  for(int i=0; i<n; i++) {
    int ans = 0, msk=0;
    for(int j=0; j<m; j++)
      if(cnt[j]-(a[i]>>j&1) > n/2) ans++;
      else if(cnt[j]-(a[i]>>j&1) == n/2) msk ^= 1<<j;
    if(dp[msk].X.Y==i) cout << ans + __builtin_popcount(msk) - dp[msk].Y.X << '\n';
    else cout << ans + __builtin_popcount(msk) - dp[msk].X.X << '\n';
  }
  return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 8 / 8
• Subtask 3: 6 / 6
• Subtask 4: 19 / 19
• Subtask 5: 15 / 15
• Subtask 6: 22 / 22
• Subtask 7: 22 / 22