Submission #1136440

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136440		Otalp	Snake Escaping (JOI18_snake_escaping)	C++20	75 / 100	2097 ms	62124 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];

void solve(){
    int n, t;
    cin>>n>>t;
    for(int i=0; i<(1<<n); i++){
        char c;
        cin>>c;
        a[i] = c - '0';
    }
    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';
        // }

        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: 53 / 53
• Subtask 5: 0 / 25