Submission #1100416

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100416		imarn	Council (JOI23_council)	C++14	100 / 100	505 ms	53888 KiB

council

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define plx pair<ll,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vl vector<ll>
#define vvi vector<vi>
using namespace std;
const ll inf=1e9+7,mxn=2e5+5,B=17;
bool vis[1<<20]{0};
int cal(int x,int rs=0){
    while(x>0){
        if(x&1)rs++;x>>=1;
    }return rs;
}int dp[1<<20][2]{0};
int pr[1<<20][2]{0};
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n,m;cin>>n>>m;int a[n][m];
    int sum[m]={0};
    for(int i=0;i<n;i++){int rs=0;
        for(int j=0;j<m;j++){
            cin>>a[i][j];sum[j]+=a[i][j];
            if(a[i][j])rs+=1<<j;
        }if(!vis[rs])vis[rs]=1,pr[rs][0]=i+1;
        else pr[rs][1]=i+1;
    }int mm=(1<<m);
    for(int i=0;i<mm;i++){
        for(int j=0;j<m;j++){
            if((i&(1<<j))&&vis[i^(1<<j)]){
                if(!vis[i]){
                    vis[i]=1;
                    if(pr[i^(1<<j)][0])pr[i][0]=pr[i^(1<<j)][0];
                    if(pr[i^(1<<j)][1])pr[i][1]=pr[i^(1<<j)][1];
                }
                else {
                    if(pr[i^(1<<j)][0]&&pr[i^(1<<j)][0]!=pr[i][0])pr[i][1]=pr[i^(1<<j)][0];
                    if(pr[i^(1<<j)][1]&&pr[i^(1<<j)][1]!=pr[i][0])pr[i][1]=pr[i^(1<<j)][1];
                }
            }
        }
    }
    for(int i=mm-1;i>=0;i--){
        dp[i][0]=dp[i][1]=1e9;
        if(vis[i]&&pr[i][0])dp[i][0]=cal(i);
        if(vis[i]&&pr[i][1])dp[i][1]=cal(i);
        for(int j=0;j<m;j++){
            if(!(i&(1<<j))){
                int bt=i^(1<<j);
                if(pr[bt][0]){
                    int tmp=dp[bt][0],tmp2=pr[bt][0];
                    if(tmp<dp[i][0]){
                        swap(dp[i][0],tmp);
                        swap(pr[i][0],tmp2);
                    }
                    if(tmp<dp[i][1]&&tmp2!=pr[i][0]){
                        swap(dp[i][1],tmp);
                        swap(pr[i][1],tmp2);
                    }
                }
                if(pr[bt][1]){
                    int tmp=dp[bt][1],tmp2=pr[bt][1];
                    if(tmp<dp[i][0]){
                        swap(dp[i][0],tmp);
                        swap(pr[i][0],tmp2);
                    }
                    if(tmp<dp[i][1]&&tmp2!=pr[i][0]){
                        swap(dp[i][1],tmp);
                        swap(pr[i][1],tmp2);
                    }
                }
            }
        }
    }
    int go=n/2;
    for(int i=0;i<n;i++){
        int rs=0,ans=0;
        for(int j=0;j<m;j++){
            sum[j]-=a[i][j];
            if(sum[j]<go)rs+=1<<j;
            if(sum[j]>go)rs+=1<<j,ans++;
            if(sum[j]==go)ans++;
            sum[j]+=a[i][j];
        }
        if(pr[rs][0]!=i+1)cout<<ans-(dp[rs][0]-cal(rs))<<'\n';
        else cout<<ans-(dp[rs][1]-cal(rs))<<'\n';
    }
}

Compilation message (stderr)

council.cpp: In function 'int cal(int, int)':
council.cpp:18:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   18 |         if(x&1)rs++;x>>=1;
      |         ^~
council.cpp:18:21: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   18 |         if(x&1)rs++;x>>=1;
      |                     ^

• 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