Submission #227611

#	Time	Username	Problem	Language	Result	Execution time	Memory
227611		dolphingarlic	Snake Escaping (JOI18_snake_escaping)	C++14	100 / 100	1402 ms	39320 KiB

snake_escaping

#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

int l, q, a, b, c, sos[1 << 20], rsos[1 << 20];
string s, k;

int solve_a() { // Brute force over '?'
    int ans = 0, base = 0, mask = 0;
    FOR(i, 0, l) {
        if (k[i] == '?') mask += 1 << i;
        else if (k[i] == '1') base += 1 << i;
    }
    for (int i = mask; i; i = mask & (i - 1)) ans += s[i | base] - '0';
    ans += s[base] - '0';
    return ans;
}

int solve_b() { // Brute force over '0'
    int ans = 0, base = 0, mask = 0;
    FOR(i, 0, l) {
        if (k[i] == '0') mask += 1 << i;
        else if (k[i] == '?') base += 1 << i;
    }
    for (int i = mask; i; i = mask & (i - 1)) ans += ((b - __builtin_popcount(i)) & 1 ? -1 : 1) * rsos[i | base];
    ans += (b & 1 ? -1 : 1) * rsos[base];
    return ans;
}

int solve_c() { // Brute force over '1'
    int ans = 0, base = 0, mask = 0;
    FOR(i, 0, l) {
        if (k[i] == '1') mask += 1 << i;
        else if (k[i] == '?') base += 1 << i;
    }
    for (int i = mask; i; i = mask & (i - 1)) ans += ((c - __builtin_popcount(i)) & 1 ? -1 : 1) * sos[i | base];
    ans += (c & 1 ? -1 : 1) * sos[base];
    return ans;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> l >> q >> s;
    FOR(i, 0, 1 << l) sos[i] = s[i] - '0', rsos[i] = s[(1 << l) - i - 1] - '0';
    FOR(i, 0, l) FOR(j, 0, (1 << l)) if (j & (1 << i))
        sos[j] += sos[j ^ (1 << i)], rsos[j] += rsos[j ^ (1 << i)];

    while (q--) {
        cin >> k;
        reverse(k.begin(), k.end());
        a = b = c = 0;
        FOR(i, 0, l) {
            if (k[i] == '?') a++;
            if (k[i] == '0') b++;
            if (k[i] == '1') c++;
        }
        
        if (a < 7) cout << solve_a() << '\n';
        else if (b < 7) cout << solve_b() << '\n';
        else cout << solve_c() << '\n';
    }
    return 0;
}

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