Submission #533930

#	Time	Username	Problem	Language	Result	Execution time	Memory
533930		radal	Snake Escaping (JOI18_snake_escaping)	C++14	75 / 100	1652 ms	65540 KiB

snake_escaping

#include <bits/stdc++.h>
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pll;
constexpr int N = (1 << 20)+20,mod = 1e9+7,inf = 1e9+10,maxm = 1e6;
inline int mkay(int a,int b){
    if (a+b >= mod) return a+b-mod;
    if (a+b < 0) return a+b+mod;
    return a+b;
}

inline int poww(int a,int k){
    if (k < 0) return 0;
    int z = 1;
    while (k){
        if (k&1) z = 1ll*z*a%mod;
        a = 1ll*a*a%mod;
        k >>= 1;
    }
    return z;
}
int sos[N][2][2];
map<ll,int> mp;
ll pw[40];
int main(){
    ios :: sync_with_stdio(0); cin.tie(0);
    int l,q;
    cin >> l >> q;
    pw[0] = 1;
    rep(i,1,l) pw[i] = 3*pw[i-1];
    string s;
    cin >> s;
    int n = s.size();
    rep(i,0,n)
        sos[i][(l&1)][1] = sos[i][(l&1)][0] = (s[i]-'0');
    repr(j,l-1,0){
        bool d = (j&1);
        rep(i,0,n){
            sos[i][d][0] = sos[i][1-d][0];
            sos[i][d][1] = sos[i][1-d][1];
            if (i&(1 << j))
                sos[i][d][1] += sos[i-(1 << j)][!d][1];
            else
                sos[i][d][0] += sos[i+(1 << j)][!d][0];
        }
    }
    while (q--){
        string t;
        cin >> t;
        ll jam = 0;
        reverse(t.begin(),t.end());
        int t0 = 0,t2 = 0,t1 = 0,mask = 0;
        vector<int> ve;
        rep(i,0,l){
            if (t[i] == '1'){
                t1++;
                jam += pw[i];
                mask += (1 << i);
            }
            else if (t[i] == '0') t0++;
            else{
                t2++;
                jam += 2*pw[i];
            }
        }
        if (mp.find(jam) != mp.end()){
            cout << mp[jam] << endl;
            continue;
        }
        if (t2 < 7){
            rep(i,0,l) if (t[i] == '?') ve.pb(i);
            int y = (1 << t2);
            int ans = 0;
            rep(j,0,y){
                int sum = mask;
                rep(k,0,t2)
                    if (j&(1 << k)) 
                        sum += (1 << ve[k]);
                ans += (s[sum]-'0');
            }
            cout << ans << endl;
            mp[jam] = ans;
            continue;
        }
        if (t1 <= t0){
            rep(i,0,l){
                if (t[i] == '1') ve.pb(i);
                if (t[i] == '?') mask += (1 << i);
            }
            int y = (1 << t1),ans = 0;
            rep(i,0,y){
                int cnt = 0,sum = mask;
                rep(j,0,t1){
                    if ((1 << j)&i){
                        sum -= (1 << ve[j]);
                        cnt ^= 1;
                    }
                }
                if (cnt) ans -= sos[sum][0][1];
                else ans += sos[sum][0][1];
            }
            cout << ans << endl;
            mp[jam] = ans;
            continue;
        }
        rep(i,0,l)
            if (t[i] == '0')
                ve.pb(i);
        int y = (1 << t0),ans = 0;
        rep(i,0,y){
            int cnt = 0,sum = mask;
            rep(j,0,t0)
                if ((1 << j)&i){
                    sum += (1 << ve[j]);
                    cnt ^= 1;
                }
            if (cnt) ans -= sos[sum][0][0];
            else ans += sos[sum][0][0];
        }
        cout << ans << endl;
        mp[jam] = ans;
    }
}

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