Submission #885746

#	Time	Username	Problem	Language	Result	Execution time	Memory
885746		huutuan	Council (JOI23_council)	C++14	100 / 100	928 ms	78876 KiB

council

#include<bits/stdc++.h>

using namespace std;

#define int long long
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define isz(x) ((int)(x).size())
#define sumof(x) accumulate(all(x), 0ll)

const int N=3e5+1, M=20;
int n, m, a[N][M], cnt[M], msk[N];
pair<int, int> f[1<<M];

int get_val(int idx, int val){
   return val==-1?-1:__builtin_popcount(idx&(~msk[val]));
}

void optimize(int idx, int val){
   int t1=get_val(idx, val);
   int t2=get_val(idx, f[idx].first);
   int t3=get_val(idx, f[idx].second);
   if (t1>t2){
      f[idx].second=f[idx].first;
      f[idx].first=val;
   }else if (t1>t3 && val!=f[idx].first){
      f[idx].second=val;
   }
}

void optimize(int idx, pair<int, int> val){
   optimize(idx, val.first);
   optimize(idx, val.second);
}

void solve(){
   cin >> n >> m;
   for (int j=0; j<(1<<m); ++j) f[j]={-1, -1};
   for (int i=1; i<=n; ++i) for (int j=0; j<m; ++j) cin >> a[i][j], msk[i]^=a[i][j]<<j, cnt[j]+=a[i][j];
   for (int i=1; i<=n; ++i) optimize((~msk[i])&((1<<m)-1), i);
   for (int i=(1<<m)-1; i>=0; --i) for (int j=0; j<m; ++j) if (i>>j&1) optimize(i^(1<<j), f[i]);
   for (int i=0; i<(1<<m); ++i) for (int j=0; j<m; ++j) if (i>>j&1) optimize(i, f[i^(1<<j)]);
   int val=n/2;
   for (int i=1; i<=n; ++i){
      int ans=0;
      int mask=0;
      for (int j=0; j<m; ++j){
         cnt[j]-=a[i][j];
         if (cnt[j]>val) ++ans;
         if (cnt[j]==val) mask^=1<<j;
      }
      int t=f[mask].first;
      if (t==i) t=f[mask].second;
      if (t!=-1) ans+=get_val(mask, t);
      cout << ans << '\n';
      for (int j=0; j<m; ++j) cnt[j]+=a[i][j];
   }
}

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   int ntests=1;
   // cin >> ntests;
   for (int i=1; i<=ntests; ++i) solve();
   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