Submission #1014561

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014561		vjudge1	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	1097 ms	43320 KiB

snake_escaping

#include<bits/stdc++.h>
using namespace std;
int dp1[1<<20],dp2[1<<20],orig[1<<20];
void readst(string &str){
    char c=getchar();
    while(c==' '||c=='\n')
        c=getchar();
    while(c!=' '&&c!='\n')
        str+=c,c=getchar();
}
void brute(string a){
    vector<int>can;
    int k=0,l=a.size()-1,ans=0;
    for(int i=0;i<=l;i++)
        if(a[i]=='?') k<<=1,
            can.push_back(l-i);
        else k<<=1,k+=a[i]-48;
    int x=can.size();
    for(int i=0;i<1<<x;i++){
        int k2=k;
        for(int j=0;j<x;j++)
            k2|=(i>>j&1)<<can[j];
        ans+=orig[k2];
    }
    cout<<ans<<'\n';
}
void subs(string a){
    vector<int>can;
    int k=0,l=a.size()-1,ans=0;
    for(int i=0;i<=l;i++)
        if(a[i]=='?') k=k<<1|1;
        else if(a[i]=='0') k<<=1;
        else can.push_back(l-i),k=k<<1|1;
    int x=can.size();
    for(int i=0;i<1<<x;i++){
        int k2=k;
        for(int j=0;j<x;j++)
            k2^=(i>>j&1)<<can[j];
        int y=__builtin_popcount(i)%2;
        ans+=(-y*2+1)*dp1[k2];
    }
    cout<<ans<<'\n';
}
void sups(string a){
    vector<int>can;
    int k=0,l=a.size()-1,ans=0;
    for(int i=0;i<=l;i++)
        if(a[i]=='?') k<<=1;
        else if(a[i]=='1')k=k<<1|1;
        else can.push_back(l-i),k<<=1;
    int x=can.size();
    for(int i=0;i<1<<x;i++){
        int k2=k;
        for(int j=0;j<x;j++)
            k2^=(i>>j&1)<<can[j];
        int y=__builtin_popcount(i)%2;
        ans+=(-y*2+1)*dp2[k2];
    }
    cout<<ans<<'\n';
}
int main(){
    int n,m;
    string str;
    cin>>n>>m;
    readst(str);
    for(int i=0;i<1<<n;i++)
        dp1[i]=dp2[i]=orig[i]=str[i]-48;
    for(int i=0;i<n;i++) for(int j=0;j<1<<n;j++)
        if(j&1<<i) dp1[j]+=dp1[j^1<<i],dp2[j^1<<i]+=dp2[j];
    while(m--){
        string qr;
        readst(qr);
        int a=0,b=0,c=0;
        for(auto i:qr)
            if(i=='0')
                a++;
            else if(i=='1')
                b++;
            else c++;
        if(c<=6)brute(qr);
        else if(b<=6)subs(qr);
        else sups(qr);
    }
}

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