Submission #126930

#	Time	Username	Problem	Language	Result	Execution time	Memory
126930		EntityIT	Snake Escaping (JOI18_snake_escaping)	C++14	100 / 100	1070 ms	39284 KiB

snake_escaping

#include<bits/stdc++.h>

using namespace std;

const int MAX_L = 20;
int L, q, sum[2][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[0][i] = sum[1][i] = s[i] - '0';
    for (int i = 0; i < L; ++i) {
        for (int j = 0; j < (1 << L); ++j) {
            if (checkBit(j, i) ) sum[0][j] += sum[0][j ^ (1 << i)];
            else sum[1][j] += sum[1][j ^ (1 << i)];
        }
    }

    while (q --) {
        string t; cin >> t; reverse(t.begin(), t.end() );
        int maskQ = 0, maskO1 = 0, maskO0 = 0;
        for (int i = 0; i < L; ++i) {
            if (t[i] == '?') maskQ |= (1 << i);
            else if (t[i] == '1') maskO1 |= (1 << i);
            else maskO0 |= (1 << i);
        }
        int ans = 0;
        if (__builtin_popcount(maskQ) <= L / 3) {
            for (int subMask = maskQ; ; subMask = (subMask - 1) & maskQ) {
                ans += s[subMask | maskO1] - '0';
                if (!subMask) break ;
            }
        }
        else if (__builtin_popcount(maskO1) <= L / 3) {
            for (int subMask = maskO1; ; subMask = (subMask - 1) & maskO1) {
                if ( (__builtin_popcount(maskO1) - __builtin_popcount(subMask & maskO1) ) & 1) ans -= sum[0][maskQ | subMask];
                else ans += sum[0][maskQ | subMask];
                if (!subMask) break ;
            }
        }
        else {
            for (int subMask = maskO0; ; subMask = (subMask - 1) & maskO0) {
                if (__builtin_popcount(subMask) & 1) ans -= sum[1][maskO1 | subMask];
                else ans += sum[1][maskO1 | 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: 25 / 25