Submission #1271358

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271358		VMaksimoski008	Snake Escaping (JOI18_snake_escaping)	C++20	22 / 100	2085 ms	13232 KiB

snake_escaping

#include <bits/stdc++.h>
#define ar array
//#define int long long

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const ll inf = 1e18;
const int N = 1e5 + 5;

signed main() {
    ios_base::sync_with_stdio(false);
    cout.tie(0); cin.tie(0);

    int n, q; cin >> n >> q;
    vector<int> a(1<<n);

    for(int i=0; i<(1<<n); i++) {
        char ch; cin >> ch;
        a[i] = ch - '0';
    }

    auto get_val = [&](const string &s) {
        int p = 0;
        for(int i=0; i<n; i++)
            if(s[i] == '1') p |= (1 << (n-i-1));
        return p;
    };

    vector<int> dp_up(1<<n), dp_down(1<<n);
    for(int s=0; s<(1<<n); s++) {
        for(int s2=s; s2; s2=(s2-1)&s) {
            dp_up[s2] += a[s];
            dp_down[s] += a[s2];
        }
        dp_up[0] += a[s];
        dp_down[s] += a[0];
    }

    while(q--) {
        string s; cin >> s;
        map<char, int> mp;
        for(char ch : s) mp[ch]++;

        if(mp['?'] == 0) {
            cout << a[get_val(s)] << '\n';
            continue;
        }

        if(mp['?'] <= 6) {
            int og = get_val(s);
            vector<int> pos;
            for(int i=0; i<n; i++)
                if(s[i] == '?') pos.push_back(n-i-1);

            int m = pos.size(), ans = 0;
            for(int mask=0; mask<(1<<m); mask++) {
                int v = og;
                for(int i=0; i<m; i++)
                    if(mask & (1 << i))
                        v += (1 << pos[i]);
                ans += a[v];
            }

            cout << ans << '\n';
            continue;
        }

        if(mp['0'] <= 6) {
            int ans = 0, og = get_val(s);
            vector<int> pos;
            for(int i=0; i<n; i++)
                if(s[i] == '0') pos.push_back(n-i-1);

            int m = pos.size();
            for(int mask=0; mask<(1<<m); mask++) {
                int v = og;
                for(int i=0; i<m; i++)
                    if(mask & (1 << i)) v |= (1 << pos[i]);
                
                if(__builtin_parity(mask)) ans -= dp_up[v];
                else ans += dp_up[v];
            }

            cout << ans << '\n';
            continue;
        }

        int ans = 0, og = get_val(s);
        vector<int> pos;
        for(int i=0; i<n; i++)
            if(s[i] == '1') pos.push_back(n-i-1);

        int m = pos.size();
        for(int mask=0; mask<(1<<m); mask++) {
            int v = og;
            for(int i=0; i<m; i++)
                if(mask & (1 << i)) v -= (1 << pos[i]);
                
            if(__builtin_parity(mask)) ans -= dp_down[v];
            else ans += dp_down[v];
        }

        cout << ans << '\n';
    }
}

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