Submission #1037892

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037892		vjudge1	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	1114 ms	47604 KiB

snake_escaping

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define pb                  push_back
#define all(x)              x.begin(), x.end()

const int mxn = 2e6 + 3;
const int lg = 21;

int n, q;

int A[mxn];
int dp[mxn], pd[mxn];

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> q;
    string s; cin >> s;
    for(int i = 0; i < (1 << n); i ++) {
        int x = (s[i] - '0');
        A[i] = x;
        dp[i] = pd[i] = x;
    }

    for(int i = 0; i < n; i ++)
        for(int mask = 0; mask < (1 << n); mask ++)
            if(mask >> i & 1)
                dp[mask] += dp[mask ^ (1 << i)];
            else
                pd[mask] += pd[mask ^ (1 << i)];

    while(q --) {
        vector<int> c0, c1, c2; int x = 0;
        string st; cin >> st;
        reverse(all(st));
        for(int i = 0; i < n; i ++) {
            char c = st[i];
            if(c == '1')
                x += (1 << i);
            if(c == '0') c0.pb(i);
            if(c == '1') c1.pb(i);
            if(c == '?') c2.pb(i);
        }
        if(c2.size() <= 6) {
            int f = c2.size(), ans = 0;
            for(int mask = 0; mask < (1 << f); mask ++) {
                int y = x;
                for(int i = 0; i < f; i ++)
                    if(mask >> i & 1)
                        y ^= (1 << c2[i]);
                ans += A[y];
            }
            cout << ans << '\n';
            continue;
        }
        if(c1.size() <= 6) {
            int f = c1.size();
            for(int i : c2)
                x ^= (1 << i);
            int ans = 0;
            for(int mask = 0; mask < (1 << f); mask ++) {
                int y = x;
                for(int i = 0; i < f; i ++)
                    if(mask >> i & 1)
                        y ^= (1 << c1[i]);
                if(__builtin_popcount(mask) & 1)
                    ans -= dp[y];
                else
                    ans += dp[y];
            }
            cout << ans << '\n';
            continue;
        }
        if(c0.size() <= 6) {
            int f = c0.size();
            int ans = 0;
            for(int mask = 0; mask < (1 << f); mask ++) {
                int y = x;
                for(int i = 0; i < f; i ++)
                    if(mask >> i & 1)
                        y ^= (1 << c0[i]);
                if(__builtin_popcount(mask) & 1)
                    ans -= pd[y];
                else
                    ans += pd[y];
            }
            cout << ans << '\n';
            continue;
        }
    }

    return 0;
}

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