제출 #1147394

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1147394		manizare	Council (JOI23_council)	C++20	100 / 100	541 ms	350948 KiB

council

#include <bits/stdc++.h> 
#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define pii pair<int,int> 
#define all(a) a.begin(),a.end()
#define S second 
#define sz(a) (int)a.size()
#define rep(i , a , b) for(int i = (a) ; i <= (b) ; i++)
#define per(i , a , b) for(int i = (a) ; i >= (b) ; i--)
using namespace std ;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 2e6+20 , maxm = 2e4 + 220, sq = 500 , inf = 1e9+10 , mod =998244353 ; 
int a[maxn] , ted[maxn] , t[maxn] , f1[maxn] , f2[maxn] , m1 , m2 , x[maxn]; 
pair<pii,pii>  dp[22][maxn] ;

void upd(pair<pii,pii > &a , pii x){
    if(a.F.F <= x.F){
        if(x.S == a.F.S){
            a.F = x;
        }else{
            swap(a.F , a.S) ;
            a.F =x;  
        }
    }else if(a.S.F <= x.F && x.S != a.F.S){
        a.S =x;
    }
}

signed main(){
    ios_base::sync_with_stdio(false) ; cin.tie(0) ;
    int n , m ;
    cin >> n >> m ;
    rep(i ,1 , n){
        rep(j ,0 ,m-1){
            int x;
            cin >> x ;
            if(x==1){
                a[i] += (1<<j) ;
                ted[j]++;
            }
        }
    }
    int fix = 0 , f =0 ; 
    rep(j , 0 ,m-1){
        if(ted[j] < n/2)continue ;
        if(ted[j] >= n/2+2){
            fix++;
            continue ;
        }
        if(ted[j] == n/2+1){
            m2++;
            rep(i , 1 ,n){
                f2[i] = f2[i] * 2 + (a[i]>>j&1);  
            }
            fix++;
        }else{
            m1++;
            rep(i ,1 ,n){
                f1[i] = f1[i]*2 + (1^(a[i]>>j&1)) ; 
            }
        }
    }
    int s = m1+m2 ; 
    rep(i , 0, (1<<s)-1){
        dp[0][i] = {{-inf , 0} , {-inf , 0}} ;
    }
    rep(i , 1, n){
        x[i] = f1[i]+(1<<m1)*f2[i] ;
        upd(dp[0][x[i]] , {0,i});
    }
    rep(r , 1, s){
        int i = r-1 ;
        rep(j , 0, (1<<s)-1){
            dp[r][j] = {{-inf, 0} , {-inf,0}} ;
            if(i < m1){
                rep(z , 0 ,1){
                    int j2 = j ;
                    if(j>>i&1){
                        j2 ^= (1<<i) ;
                    }
                    if(z==1){
                        j2 ^= (1<<i) ; 
                    }
                    pii x = dp[i][j2].F ;
                    if(z==1 && (j>>i&1)){
                        x.F++;
                    } 
                    upd(dp[r][j] , x);
                    x = dp[i][j2].S ;
                    if(z==1 && (j>>i&1)){
                        x.F++ ;
                    }
                    upd(dp[r][j] , x);
                }
            }else{
                rep(z , 0 , 1){
                    int j2 = j ;
                    if(j>>i&1){
                        j2 ^= (1<<i) ;
                    }
                    if(z==1){
                        j2 ^= (1<<i) ; 
                    }
                    pii x = dp[i][j2].F ;
                    if(z==1 && (j>>i&1)){
                        x.F--;
                    } 
                    upd(dp[r][j] , x);
                    x = dp[i][j2].S ;
                    if(z==1 && (j>>i&1)){
                        x.F--;
                    }
                    upd(dp[r][j] , x);            
                }
            }
        }
    }
    rep(i ,1 ,n){
        if(dp[s][x[i]].F.S != i){
            cout << dp[s][x[i]].F.F+fix << "\n"; 
    //        cout << dp[s+1][x[i]].F.F+fix << "\n";
        }else{
            cout << dp[s][x[i]].S.F+fix << "\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