Submission #1260860

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260860		new_acc	Council (JOI23_council)	C++20	100 / 100	422 ms	20088 KiB

council

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define st first
#define nd second
#define pb push_back    

const int maxn = 3e5+7;

struct opt{
    int maks1;
    int maks2;
    int ind1;
    int ind2;
};

int glosowanie[maxn];
int ustawa[maxn];
opt dp[1024*1024+7];
int wyniki[maxn];

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n,m;
    cin>>n>>m;

    int liczba,x,zapalone;
    opt akt;

    for(int i=0;i<(1<<m);i++){
        dp[i].maks1 = 0;
        dp[i].maks2 = 0;
        dp[i].ind1 = 0;
        dp[i].ind2 = 0;
    }

    for(int i=1;i<=n;i++){
        liczba = 0;
        zapalone = 0;
        for(int j=m-1;j>=0;j--){
            cin>>x;
            if(x == 1){
                liczba += (1<<j);
                ustawa[j]++;
                zapalone++;
            }
        }
        glosowanie[i] = liczba;
        if(dp[liczba^((1<<m)-1)].maks1 != 0){
            dp[liczba^((1<<m)-1)].maks2 = m-zapalone;
            dp[liczba^((1<<m)-1)].ind2 = i;
        }
        else{
            akt.maks1 = m-zapalone;
            akt.ind1 = i;
            akt.maks2 = 0;
            akt.ind2 = 0;     
            dp[liczba^((1<<m)-1)] = akt;
        }
    }
    for(int i=(1<<m)-1;i>=1;i--){
        for(int j=m-1;j>=0;j--){
            if(i&(1<<j)){
                akt = dp[i];
                akt.maks1 = max((int)0,akt.maks1-1);
                akt.maks2 = max((int)0,akt.maks2-1);
                if(akt.maks1 > dp[i^(1<<j)].maks1){
                    if(akt.maks2 > dp[i^(1<<j)].maks2){
                        dp[i^(1<<j)].maks1 = akt.maks1;
                        dp[i^(1<<j)].ind1 = akt.ind1;
                        dp[i^(1<<j)].maks2 = akt.maks2;
                        dp[i^(1<<j)].ind2 = akt.ind2;
                    }
                    else if(akt.ind1 != dp[i^(1<<j)].ind1){
                        dp[i^(1<<j)].maks2 = dp[i^(1<<j)].maks1;
                        dp[i^(1<<j)].ind2 = dp[i^(1<<j)].ind1;
                        dp[i^(1<<j)].maks1 = akt.maks1;
                        dp[i^(1<<j)].ind1 = akt.ind1;
                    }
                    else if(akt.ind1 != dp[i^(1<<j)].ind2){
                        dp[i^(1<<j)].maks1 = akt.maks1;
                        dp[i^(1<<j)].ind1 = akt.ind1;
                    }
                }
                else if(akt.maks1 > dp[i^(1<<j)].maks2 && akt.ind1 != dp[i^(1<<j)].ind1){
                    dp[i^(1<<j)].maks2 = akt.maks1;
                    dp[i^(1<<j)].ind2 = akt.ind1;
                }
                else if(akt.maks2 > dp[i^(1<<j)].maks2 && akt.ind2 != dp[i^(1<<j)].ind1){
                    dp[i^(1<<j)].maks2 = akt.maks2;
                    dp[i^(1<<j)].ind2 = akt.ind2;
                }
            }
        }
    }

    for(int i=1;i<(1<<m);i++){
        for(int j=m-1;j>=0;j--){
            if(i&(1<<j)){
                akt = dp[i^(1<<j)];
                if(akt.maks1 > dp[i].maks1){
                    if(akt.maks2 > dp[i].maks2){
                        dp[i].maks1 = akt.maks1;
                        dp[i].ind1 = akt.ind1;
                        dp[i].maks2 = akt.maks2;
                        dp[i].ind2 = akt.ind2;
                    }
                    else if(akt.ind1 != dp[i].ind1){
                        dp[i].maks2 = dp[i].maks1;
                        dp[i].ind2 = dp[i].ind1;
                        dp[i].maks1 = akt.maks1;
                        dp[i].ind1 = akt.ind1;
                    }
                    else if(akt.ind1 != dp[i].ind2){
                        dp[i].maks1 = akt.maks1;
                        dp[i].ind1 = akt.ind1;
                    }
                }
                else if(akt.maks1 > dp[i].maks2 && akt.ind1 != dp[i].ind1){
                    dp[i].maks2 = akt.maks1;
                    dp[i].ind2 = akt.ind1;
                }
                else if(akt.maks2 > dp[i].maks2 && akt.ind2 != dp[i].ind1){
                    dp[i].maks2 = akt.maks2;
                    dp[i].ind2 = akt.ind2;
                }
            }
        }
    }

    for(int i=1;i<=n;i++){
        liczba = 0;
        for(int j=m-1;j>=0;j--){
            if(glosowanie[i]&(1<<j)){
                x = ustawa[j]-1;
            }
            else{
                x = ustawa[j];
            }
            if(x*2 > n-2 && (x-1)*2 <= n-2){
                liczba += (1<<j);
            }
            else if((x-1)*2 > n-2){
                wyniki[i]++;
            }
        }
        if(dp[liczba].ind1 == i){
            wyniki[i] += dp[liczba].maks2;
        }
        else{
            wyniki[i] += dp[liczba].maks1;
        }
        
    }

    for(int i=1;i<=n;i++){
        cout<<wyniki[i]<<"\n";
    }

    return 0;
}

• 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