Submission #1276547

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276547		sasde	Snake Escaping (JOI18_snake_escaping)	C++20	75 / 100	2095 ms	14864 KiB

snake_escaping

#include<bits/stdc++.h>
using namespace std;
#define sz(a) (int)a.size()
#define all(x) x.begin(),x.end()
#define emb emplace_back
const int N=2e6+5;
int node,query,ans;
string s,x;
int dpcha[N],dpcon[N],po[N];
vector<int>res;
void backtrack1(int i,bool c){
    if(i==sz(res)){
        int val=0;
        for(int j=0;j<node;++j){
            if(x[j]=='?'){
                val|=(1<<j);
                continue;
            }
            val|=((x[j]-'0')<<j);
        }
        // cout <<x<<'\n';   
        // cout <<val<<'\n';
        // cout <<val<<" "<<c<<" "<<dpcon[val]<<'\n';
        ans+=(c&1?-1:1)*dpcha[val];
        return;
    }
    x[res[i]]='0';
    backtrack1(i+1,c^1);
    x[res[i]]='1';
    backtrack1(i+1,c);
}
void backtrack0(int i,bool c){
    if(i==sz(res)){
        int val=0;
        for(int j=0;j<node;++j){
            if(x[j]=='?')continue;
            val|=((x[j]-'0')<<j);
        }
        // cout <<x<<'\n';   
        // cout <<val<<'\n';
        // cout <<val<<" "<<c<<" "<<dpcon[val]<<'\n';
        ans+=(c&1?-1:1)*dpcon[val];
        return;
    }
    x[res[i]]='0';
    backtrack0(i+1,c);
    x[res[i]]='1';
    backtrack0(i+1,c^1);
}
void backtrack(int i){
    if(i==sz(res)){
        int val=0;
        for(int j=0;j<node;++j){
            val|=((x[j]-'0')<<j);
        }
        // cout <<x<<'\n';   
        // cout <<val<<'\n';
        ans+=s[val]-'0';
        return;
    }
    x[res[i]]='0';
    backtrack(i+1);
    x[res[i]]='1';
    backtrack(i+1);
}
main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> node >> query >> s;
    for(int i=0;i<(1<<node);++i){
        dpcon[i]=s[i]-'0';
        dpcha[i]=s[i]-'0';
    }
    for(int j=0;j<node;++j){
    for(int mask=0;mask<(1<<node);++mask){
            if(mask>>j&1)dpcha[mask]+=dpcha[mask^(1<<j)];
            else dpcon[mask]+=dpcon[mask^(1<<j)];
        }
    }
    // cout <<dp[]
    while(query--){
        cin >> x;
        vector<int>vec[3];
        ans=0;
        reverse(all(x));
        for(int i=0;i<sz(x);++i){
            char y=x[i];
            if(y=='?')vec[0].emb(i);
            if(y=='0')vec[1].emb(i);
            if(y=='1')vec[2].emb(i);
        }


        if(sz(vec[1])<=sz(x)/3){
            // backtrack1(0,vec[2],0);
            res=vec[1];
            backtrack0(0,0);
        }
        else
        if(sz(vec[2])<=sz(x)/3){
            res=vec[2];
            // backtrack0(0,vec[1],0);
            backtrack1(0,0);
        }
        else 
        {
          res=vec[0];
          backtrack(0);
        }
        cout <<ans<<'\n';
    }
}

Compilation message (stderr)

snake_escaping.cpp:66:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   66 | main()
      | ^~~~

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