Submission #887102

#	Time	Username	Problem	Language	Result	Execution time	Memory
887102		Litusiano	Council (JOI23_council)	C++17	100 / 100	2238 ms	147200 KiB

council

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define f first
#define s second
#define ii pair<int,int>
#define vi vector<int>
#define vvi vector<vi>
#define vvii vector<vector<ii>>
#define pb push_back
#define vpi vector<ii> 
#define forcin for(int i = 0; i<n; ++i) cin>>v[i];
#define ld long double
#define all(a) (a).begin(),(a).end()
#define For(i, n, x) for (int i = x; i < n; i++)
#define rsz(a,x) assign(a,x)

signed main(){
  int n,m; cin>>n>>m;
  
  vector<vector<int>> v(n,vector<int>(m));
  for(auto& x : v){
    for(auto& z : x) cin>>z;
  }
  
  if(n <= 300){
    vi cntones(m);
    For(i,m,0){
      For(j,n,0) cntones[i] += v[j][i]; 
    }
    //for(auto x : cntones) cout<<x<<" ";
    int tot = (n)/2;
    For(i,n,0){
      int mx = 0;
      For(j,n,0){
        if(i == j) continue;
        int tmp = 0;
        For(k,m,0){
          //if(i == 2) cerr<<i<<" "<<j<<" "<<k<<" "<<cntones[i]<<" "<<v[i][k]<<" "<<v[j][k]<<" "<<tot<<endl;
          if(cntones[k] - v[i][k] - v[j][k] >= tot && cntones[k] - v[i][k] - v[j][k] > 0) tmp++;
        }
        mx = max(mx,tmp);
      }
      cout<<mx<<endl;
      
    }
    return 0;
  }
  for(auto& x : v){
    for(auto& y : x) y^=1;
  }
  vector<int> dp(1ll<<m,0); 
  auto dp1 = dp;
  auto idx = dp; auto idx1 = dp;
  int cnt = 0;
  set<int> msks;
  for(auto x : v){
    int z = 0;
    int tot = 0;
    for(int i = 0; i<m; i++){
      z+= x[i] * (1ll<<i);
      tot += x[i];
    }
    msks.insert(z);
    if(dp[z] < tot){
      dp1[z] = dp[z]; idx1[z] = idx[z];
      dp[z] = tot; idx[z] = cnt;
    }
    else if(dp1[z] < tot){
      dp1[z] = tot; idx1[z] = cnt;
    }
    //cerr<<z<<" "<<dp[z]<<" "<<idx[z]<<endl;
    cnt++;
  }
  //cerr<<endl;
  priority_queue<pair<int,int>> pq;
  for(auto x : msks) pq.push({dp[x],x});
  while(!pq.empty()){
    pair<int,int> p = pq.top();
    bool b = 0;
    int tot = p.first; int u = p.second;
    if(u >= (1ll<<m)) b = 1, u -= (1ll<<m);
    pq.pop();
    //cerr<<"START "<<u<<" "<<tot<<" "<<dp[u]<<" "<<idx[u]<<" "<<dp1[u]<<" "<<idx1[u]<<" "<<b<<endl;
    if(tot < dp1[u]) continue;
    if(!b && tot < dp[u]) continue;
    //cerr<<"START LOOP"<<endl;
    for(int i = 0; i < m; i++){
      int z = u ^ (1ll<<i);
      // trec el bit del d'aixo que estic mirant
      int tmp;
      int IDX;
      if(!b) tmp = dp[u], IDX = idx[u];
      else tmp = dp1[u], IDX = idx1[u];
      if(v[IDX][i] && z < u) tmp--; // turning bit off and was active
      if(z > u && v[IDX][i]) tmp++; // turning bit on and was active
      //cerr<<u<<" "<<z<<" "<<tmp<<" "<<IDX<<" "<<i<<endl;
      int ok = 0;
      if(dp[z] < tmp){
        dp1[z] = dp[z]; idx1[z] = idx[z];
        dp[z] = tmp; idx[z] = IDX;
        ok = 1;
      }
      else if(dp1[z] < tmp && IDX != idx[z]){
        dp1[z] = tmp; idx1[z] = IDX;
        ok = 2;
      }
      if(ok == 1){
        pq.push({dp[z],z});
      }
      else if(ok == 2) pq.push({dp1[z],z + (1ll<<m)});
    }
    //cerr<<"END LOOP"<<endl;
  }
  vector<int> sumcols(m);
  for(int j = 0; j<m; j++){
    for(int i = 0; i<n; i++){
      sumcols[j] += v[i][j] == 0;
    }
  }
  for(int i = 0; i<n; i++){
    int good = 0;
    int msk = 0;
    int bits = 0;
    for(int j = 0; j<m; j++){
      int z = sumcols[j]; z-=1^v[i][j];
      if(z - 1>=(n)/2) good++;
      else if(z == (n)/2){
        msk+= (1ll<<j);
        bits++;
      }
    }
   //cerr<<i<<" "<<good<<" "<<msk<<" DP "<<dp[msk]<<" "<<idx[msk]<<" DP1 "<<dp1[msk]<<" "<<idx1[msk]<<endl;
    if(idx[msk] == i && idx1[msk] != i) good+=dp1[msk];
    else good+=dp[msk];
    cout<<good<<endl;
  }


}

• 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