Submission #1180524

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180524		user736482	Snake Escaping (JOI18_snake_escaping)	C++20	75 / 100	2095 ms	38424 KiB

snake_escaping

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 1000000009
#define INF 1000000019
#define INFL 1000000000000000099LL

ll n,q,s,t,a,b,c,d,ans=INFL,bst,k,e,m,pier,h,w,u,v;

ll ile[1<<20];
ll dp1[1<<20],dp2[1<<20];

ll brt(ll s,vector<ll>v){
    if(v.empty()){
   //     cout<<s<<" ";
        return ile[s];}
    ll i=v.back();
    v.pop_back();
    ll pom=brt(s,v);
    s+=(1<<i);
    return pom+brt(s,v);
        
    
    
}

ll brt2(ll s,vector<ll>v){
    if(v.empty()){
      //  cout<<s<<" "<<dp1[s][0]<<"\n";
        return dp1[s];}
    ll i=v.back();
    v.pop_back();
    ll pom=brt2(s,v);
    s-=(1<<i);
    return pom-brt2(s,v);
        
    
    
}

ll brt3(ll s,vector<ll>v){
    if(v.empty()){
       // cout<<s<<" "<<dp2[s][0]<<"\n";
        return dp2[s];}
    ll i=v.back();
    v.pop_back();
    ll pom=brt3(s,v);
    s+=(1<<i);
    return pom-brt3(s,v);
        
    
    
}

ll dpp[(1<<20)];
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>q;
    for(ll i=0;i<(1<<n);i++){
        char ch;
        cin>>ch;
        ch-='0';
        ile[i]=ch;
        //ile2[(1<<n)-i-1]=ch;
    }
    for(ll i=0;i<(1<<n);i++){
        dp1[i]=ile[i];
        dp2[i]=ile[i];
        
    }
    for(ll j=n-1;j>=0;j--){
        //cout<<j<<" "<<flush;
       // return 0;
        
        for(ll i=0;i<(1<<n);i++){
            if(i & (1<<j)){
                dpp[i]=dp1[i]+dpp[i-(1<<j)];
          //      dp2[i][j]=dp2[i][j+1];
            }
            else{
             //   dp2[i][j]=dp2[i][j+1]+dp2[i+(1<<j)][j];
                dpp[i]=dp1[i];
            }
        }
        swap(dp1,dpp);
      //  for(ll i=0;i<(1<<20);i++)dp1[i]=dpp[i];
    }
    //return 0;
        for(ll j=n-1;j>=0;j--){
           // ll dpp[(1<<20)];
            for(ll i=(1<<n)-1;i>=0;i--){
                if(i & (1<<j)){
                    dpp[i]=dp2[i];
                }
                else{
                    dpp[i]=dp2[i]+dpp[i+(1<<j)];
                }
            }
            swap(dp2,dpp);
            //for(ll i=0;i<(1<<20);i++)dp2[i]=dpp[i];
        }
     //   cout<<dp2[i][0]<<" ";
    
    string s;
    for(ll i=0;i<q;i++){
        cin>>s;
        ll l1=0,l2=0,l3=0;
        for(char j : s){
            if(j=='?')
                l3++;
            else if(j=='0')
                l1++;
            else
                l2++;
        }
        if(l3<=6){
            a=0;
            vector<ll>v;
            for(ll j=0;j<n;j++){
                a*=2;
                if(s[j]=='1')a++;
                if(s[j]=='?')v.pb(n-1-j);
            }
            reverse(v.begin(),v.end());
            
            cout<<brt(a,v)<<"\n";
        }
        else if(l2<=6){
            //cout<<i<<"    ";
            a=0;
            vector<ll>v;
            for(ll j=0;j<n;j++){
                a*=2;
                if(s[j]=='1')v.pb(n-1-j);
                if(s[j]=='?' || s[j]=='1')a++;
                
            }
            reverse(v.begin(),v.end());
        //    cout<<a<<"     "  ;
            cout<<brt2(a,v)<<"\n";
        }
        else{
            a=0;
            vector<ll>v;
            for(ll j=0;j<n;j++){
                a*=2;
                if(s[j]=='0')v.pb(n-1-j);
                if(s[j]=='1')a++;
                
            }
            reverse(v.begin(),v.end());
            cout<<brt3(a,v)<<"\n";
        }
    }
    
    
}

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