Submission #783348

#	Time	Username	Problem	Language	Result	Execution time	Memory
783348		fuad27	Council (JOI23_council)	C++17	100 / 100	197 ms	59832 KiB

council

#include<bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
const int M=20, N=300'010;
const int INF=1e9;
struct i2 {
  int mx=0, mx2=0;
  int i=-1,j=-2;
};
int m;
i2 max(i2 a, i2 b) {
  if(a.mx<b.mx)swap(a,b);
  i2 res=a;
  if(b.i==a.i){
    swap(b.mx,b.mx2);
    swap(b.i,b.j);
  }
  if(a.mx2<b.mx) {
    res.mx2=b.mx;
    res.j=b.i;
  }
  else {
    res.mx2=a.mx2;
    res.j=a.j;
  }
  return res;
}
struct bf {
  vector<int> point;
  vector<pair<int,int>> all;
  i2 dp[(1<<M)];
  bf() {
  }
  void build() {
    for(auto i:all) {
      if(dp[(1<<m)-i.first-1].i<0) {
        dp[(1<<m)-i.first-1].mx=__builtin_popcount(i.first);
        dp[(1<<m)-i.first-1].i=i.second;
      }
      else {
        dp[(1<<m)-i.first-1].mx2=__builtin_popcount(i.first);
        dp[(1<<m)-i.first-1].j=i.second;
      }
    }
    for(int j = 0;j<m;j++) {
      for(int mask=0;mask<(1<<m);mask++) {
        if(mask&(1<<j)) {
          i2 tmp=dp[mask^(1<<j)];
          tmp.mx--,tmp.mx2--;
          dp[mask]=max(dp[mask],tmp);
        }
      }
    }
    reverse(dp,dp+(1<<m));
    for(int i = 0;i<m;i++) {
      for(int mask=0;mask<(1<<m);mask++) {
        if(mask&(1<<i)) {
          dp[mask]=max(dp[mask], dp[mask^(1<<i)]);
        }
      }
    }
  }
  void add(int x, int i) {
    all.push_back({x,i});
  }
  int get(int x, int i) {
    i2 mx;
    mx=max(mx, dp[x]);
    if(mx.i==i)return mx.mx2;
    return mx.mx;
  }
};
int tot[M], kek[N][M];
int a[N], b[N];
int main () {
  cin.tie(0)->sync_with_stdio(0);
  int n;
  cin >> n >> m;
  for(int i = 0;i<n;i++) {
    string s;
    if(i==0)getline(cin,s);
    getline(cin,s);
    for(int j = 0;j<m;j++) {
      kek[i][j]=s[2*j]-'0';
      a[i]*=2;
      a[i]+=!kek[i][j];
      tot[j]+=kek[i][j];
    }
  }
  for(int i = 0;i<n;i++) {
    for(int j = 0;j<m;j++) {
      b[i]*=2;
      b[i]+=(tot[j]-kek[i][j])==(n/2);
    }
  }
  int res[n];
  bf c;
  for(int i = 0;i<n;i++) {
    c.add(a[i],i);
  }
  c.build();
  for(int i = 0;i<n;i++) {
    res[i]=c.get(b[i],i);
  }
  for(int i = 0;i<n;i++) {
    for(int j = 0;j<m;j++) {
      b[i]*=2;
      if((tot[j]-kek[i][j]-1)>=(n/2)) {
        res[i]++;
      }
    }
    cout << res[i] << "\n";
  }
}

• 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