Submission #1271370

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271370		VMaksimoski008	Snake Escaping (JOI18_snake_escaping)	C++20	12 / 100	2096 ms	12744 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];
    }

    for(int i=0; i<(1<<n); i++)
        dp_down[i] = a[i];

    for(int i=0; i<n; i++)
        for(int s=0; s<(1<<n); s++)
            if(s & (1 << i)) dp_down[s] += dp_down[s^(1<<i)];

    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);
            else if(s[i] == '?') og |= (1 << (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: 0 / 10
• Subtask 4: 0 / 53
• Subtask 5: 0 / 25