Submission #126920

#	Time	Username	Problem	Language	Result	Execution time	Memory
126920		EntityIT	Snake Escaping (JOI18_snake_escaping)	C++14	75 / 100	2047 ms	31552 KiB

snake_escaping

#include<bits/stdc++.h>

using namespace std;

const int MAX_L = 20;
int L, q, sum[1 << MAX_L];
string s;

bool checkBit (int _a, int _bit) { return (_a >> _bit) & 1; }

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

//    freopen("test.INP", "r", stdin);

    cin >> L >> q >> s;

    for (int i = 0; i < (1 << L); ++i) sum[i] = s[i] - '0';
    for (int i = 0; i < L; ++i) {
        for (int j = 0; j < (1 << L); ++j) if (checkBit(j, i) ) sum[j] += sum[j ^ (1 << i)];
    }

    while (q --) {
        string t; cin >> t; reverse(t.begin(), t.end() );
        int maskQ = 0, maskO = 0;
        for (int i = 0; i < L; ++i) {
            if (t[i] == '?') maskQ |= (1 << i);
            if (t[i] == '1') maskO |= (1 << i);
        }
        int ans = 0;
        if (__builtin_popcount(maskQ) <= L / 2) {
            for (int subMask = maskQ; ; subMask = (subMask - 1) & maskQ) {
                ans += s[subMask | maskO] - '0';
                if (!subMask) break ;
            }
        }
        else {
            for (int subMask = maskO; ; subMask = (subMask - 1) & maskO) {
                if ( (__builtin_popcount(maskO) - __builtin_popcount(subMask & maskO) ) & 1) ans -= sum[maskQ | subMask];
                else ans += sum[maskQ | subMask];
                if (!subMask) break ;
            }
        }
        cout << ans << '\n';
    }

    return 0;
}

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