Submission #1247388

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247388		quannnguyen2009	Snake Escaping (JOI18_snake_escaping)	C++20	100 / 100	766 ms	32024 KiB

snake_escaping

#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pb push_back
#define ii pair<int, int>
#define pcnt __builtin_popcountll
#define sz(v) (int)v.size()
#define all(v) v.begin(), v.end()
using namespace std;

const int N = 2e5+5, L = 21, mod = 1e9+7, inf = 1e18;

int l, q;
string s;
int sub[1<<L], sup[1<<L];

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> l >> q >> s;
    int zero = 0, one = 0, und = 0;
    for (int i=0; i<(1<<l); i++) {
        sub[i] = sup[i] = s[i]-'0';
    }
    for (int j=0; j<l; j++) {
        for (int i=0; i<(1<<l); i++) {
            if (i>>j&1) sub[i] += sub[i^(1<<j)];
            else sup[i] += sup[i^(1<<j)];
        }
    }
    while (q--) {
        zero = one = und = 0;
        for (int i=0; i<l; i++) {
            char c; cin >> c;
            if (c=='0') zero |= (1<<(l-1-i));
            else if (c=='1') one |= (1<<(l-1-i));
            else und |= (1<<(l-1-i));
        }
        int ans = 0;
        if (pcnt(und)<=6) {
            for (int i=und; i>=0; i=(i-1)&und) {
                ans += (s[i|one]-'0');
                if (!i) break;    
            }
        } else if (pcnt(zero)<=6) {
            for (int i=zero; i>=0; i=(i-1)&zero) {
                if (pcnt(i)&1) ans -= sup[i|one];
                else ans += sup[i|one];
                if (!i) break;
            }
        } else {
            for (int i=one; i>=0; i=(i-1)&one) {
                if ((pcnt(one)-pcnt(i))&1) ans -= sub[i|und];
                else ans += sub[i|und];
                if (!i) break;
            }
        }
        cout << ans << '\n';
    }
}

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