Submission #1190325

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190325		AlgorithmWarrior	Snake Escaping (JOI18_snake_escaping)	C++20	100 / 100	1815 ms	28828 KiB

snake_escaping

#include <bits/stdc++.h>

using namespace std;

int const MAX=1050000;
int const LOG=23;
int n,q;
int val[MAX];
char qry[LOG];
int dpsub[MAX][2],dpsupra[MAX][2];

void read(){
    cin>>n>>q;
    int i;
    for(i=0;i<(1<<n);++i){
        char ch;
        cin>>ch;
        val[i]=ch-'0';
        dpsub[i][0]=ch-'0';
        dpsupra[i][0]=ch-'0';
    }
}

void precalc(){
    int i,mask;
    for(i=1;i<=n;++i)
        for(mask=0;mask<(1<<n);++mask)
            if(mask&(1<<(i-1)))
                dpsub[mask][i&1]=dpsub[mask][!(i&1)]+dpsub[mask^(1<<(i-1))][!(i&1)];
            else
                dpsub[mask][i&1]=dpsub[mask][!(i&1)];
    for(i=1;i<=n;++i)
        for(mask=0;mask<(1<<n);++mask)
            if(mask&(1<<(i-1)))
                dpsupra[mask][i&1]=dpsupra[mask][!(i&1)];
            else
                dpsupra[mask][i&1]=dpsupra[mask][!(i&1)]+dpsupra[mask^(1<<(i-1))][!(i&1)];
}

int solve_brut(){
    int nr=0,mask=0;
    int i;
    for(i=0;i<n;++i)
        if(qry[i]=='?')
            mask|=(1<<(n-i-1));
        else
            nr|=(1<<(n-i-1))*(qry[i]-'0');
    int submask=mask;
    int sum=0;
    do{
        sum+=val[nr|submask];
        submask=((submask-1)&mask);
    }while(submask!=mask);
    return sum;
}

int solve_pinex1(){
    int nr=0,mask=0;
    int i;
    for(i=0;i<n;++i)
        if(qry[i]=='?')
            nr|=(1<<(n-i-1));
        else
            mask|=(1<<(n-i-1))*(qry[i]-'0');
    int sum=0;
    int submask=mask;
    int nrb=__builtin_popcount(mask);
    do{
        int nrbs=__builtin_popcount(submask);
        int semn;
        if(nrb%2==nrbs%2)
            semn=1;
        else
            semn=-1;
        sum+=semn*dpsub[nr|submask][n&1];
        submask=(submask-1)&mask;
    }while(submask!=mask);
    return sum;
}

int solve_pinex0(){
    int nr=0,mask=0;
    int i;
    for(i=0;i<n;++i)
        if(qry[i]!='?'){
            nr|=(1<<(n-i-1))*(qry[i]-'0');
            mask|=(1<<(n-i-1))*('1'-qry[i]);
        }
    int sum=0;
    int submask=mask;
    do{
        int nrbs=__builtin_popcount(submask);
        int semn;
        if(nrbs%2==0)
            semn=1;
        else
            semn=-1;
        sum+=semn*dpsupra[nr|submask][n&1];
        submask=(submask-1)&mask;
    }while(submask!=mask);
    return sum;
}

void process_queries(){
    int i,j;
    for(i=1;i<=q;++i){
        int cnt=0,cnt0=0,cnt1=0;
        for(j=0;j<n;++j){
            cin>>qry[j];
            if(qry[j]=='?')
                ++cnt;
            if(qry[j]=='0')
                ++cnt0;
            if(qry[j]=='1')
                ++cnt1;
        }
        if(cnt<=6)
            cout<<solve_brut()<<'\n';
        else
            if(cnt0<=6)
                cout<<solve_pinex0()<<'\n';
            else
                cout<<solve_pinex1()<<'\n';
    }
}

int main()
{
    read();
    precalc();
    process_queries();
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 10 / 10
• Subtask 4: 53 / 53
• Subtask 5: 25 / 25