Submission #1077666

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077666		vjudge1	Council (JOI23_council)	C++98	56 / 100	4078 ms	19244 KiB

council

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vii;
typedef pair<int,int> pii;
#define F first
#define S second
#define aint(v) v.begin(),v.end()
#define pb push_back
const int M=2e6+10;
const int inf=2e18+10;
const int mod=1e9+7;
int n,m,a[M],cnt[M],cntb[40],ans[M];
int main() {
  ios_base::sync_with_stdio(0),cin.tie(0);
  cin>>n>>m;
  for(int i=0;i<n;i++)
    for(int j=0;j<m;j++) {
      int x;
      cin>>x;
      a[i]+=(x*(1<<j));
      cntb[j]+=x;
    }
  for(int i=0;i<n;i++) {
    for(int j=a[i];j<(1<<m);j++,j|=a[i]) {
      cnt[j]++;
    }
  }
  for(int i=0;i<(1<<m);i++)
    ans[i]=-1;
  for(int i=0;i<n;i++) {
    int res=0,x=0;
    for(int j=0;j<m;j++) {
      if(cntb[j]-bool(((1<<j)&a[i])>0)>n/2)
        res++;
      else if(cntb[j]-bool(((1<<j)&a[i])>0)==n/2) {
        x+=(1<<j);
      }
    }
    if(ans[x]>-1) {
      cout<<ans[x]<<'\n';
      continue;
    }
    int res1=0;
    for(int j=x;j>=0;j--) {
      if(j<0)
        break;
      j&=x;
      int y=(j|(((1<<m)-1)^x));
      if((a[i]&y)==a[i])
        cnt[y]--;
      if(cnt[y]>0)
        res1=max(res1,__builtin_popcount(x)-__builtin_popcount(j));
      if((a[i]&y)==a[i])
        cnt[y]++;
    }
    ans[x]=res1+res;
    cout<<res1+res<<'\n';
  }
}

Compilation message (stderr)

council.cpp:11:19: warning: overflow in conversion from 'double' to 'int' changes value from '2.0e+18' to '2147483647' [-Woverflow]
   11 | const int inf=2e18+10;
      |               ~~~~^~~

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