Submission #1137449

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137449		Otalp	Snake Escaping (JOI18_snake_escaping)	C++20	22 / 100	2094 ms	7948 KiB

snake_escaping

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
#define unm unordered_map

const ll mod = 1e9 + 7;
const int MAXN = 2e5 + 5;
const int MAXA = 2e5 + 5;

int a[2001000];
int dp[2][2001000], dk[2001000];



void solve(){
    int n, t;
    cin>>n>>t;
    
    for(int i=0; i<(1<<n); i++){
        char c;
        cin>>c;
        a[i] = c - '0';
        dp[0][0] += a[i];
        dp[1][0] += a[i];
    }
    for(int k=0; k<(1 << n); k++){
        dk[k] = 1;
        for(int i=0; i<n; i++){
            if(k & (1 << i)) dk[k] *= -1;
        }
        dp[1][k] = 0;
        dp[0][k] = 0;
        int g = (1 << n) - 1 - k;
        dp[1][k] = a[k];
        dp[0][k] = a[0];
        for(int r=g; r > 0; r = (g & (r-1))){
            dp[1][k] += a[r + k];
            dp[0][k] += a[r];
        }
    }
    map<string, int> us;
    while(t--){
        string s;
        cin>>s;
        // if(us[s]){
        //     cout<<us[s]<<'\n';
        //     continue;
        // }
        int cnt[3] = {0, 0, 0};
        for(int i=0; i<s.size(); i++){
            if(s[i] == '?') cnt[2] ++;
            else cnt[s[i]-'0'] ++;
        }
        if(cnt[2] <= 6){
            int h = 0, g = 0;
            for(int i=0; i<s.size(); i++){
                if(s[i] == '?') g += (1 << (n-1-i));
                else h += (1 << (n - i - 1)) * (s[i] - '0');
            }
            int ans = a[h];
            for(int k=g; k > 0; k = (g & (k-1))){
                ans += a[h + k];
                // cout<<g<<'\n';
            }
            cout<<ans<<'\n';
        }
        else if(cnt[0] <= 6){
            // cout<<"##############\n";
            // cout<<s<<'\n';
            int h = 0, g = 0;
            for(int i=0; i<s.size(); i++){
                if(s[i] == '0') g += (1 << (n-1-i));
                else h += (1 << (n - i - 1)) * (s[i] == '1' ?1 :0);
            }
            int ans = dp[1][h];
            // cout<<ans<<"\n";
            // cout<<h<<'\n';
            for(int k=g; k>0; k = (g & (k - 1))){
                ans += dk[k] * dp[1][h + k];
                // cout<<dk[k]<<'\n';
            }
            cout<<ans<<'\n';
        }
        else if(cnt[1] <= 6){
            int h = 0, g = 0;
            for(int i=0; i<s.size(); i++){
                if(s[i] == '1') g += (1 << (n-1-i));
                else h += (1 << (n - i - 1)) * (s[i] == '0' ?1 :0);
            }
            int ans = dp[0][h];
            for(int k=g; k>0; k = (g & (k - 1))){
                ans += dk[k] * dp[0][h + k];
            }
            cout<<ans<<'\n';
        }
        // us[s] = ans;
    }
}

int main(){
    ios_base::sync_with_stdio(NULL);cin.tie(NULL);cout.tie(NULL);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
        cout<<'\n';
    }
}

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