Submission #600740

#	Time	Username	Problem	Language	Result	Execution time	Memory
600740		pakhomovee	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	940 ms	47464 KiB

snake_escaping

#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <iomanip>
#include <cassert>
#include <numeric>
#include <deque>
#include <functional>
#include <set>
#include <queue>
#include <unordered_map>
#include <map>
#include <bitset>
#include <iomanip>
#include <complex>
 
using namespace std;

const int maxn = 1 << 20;
int val[maxn];  //  just the value
int dir[maxn];  //  direct sum of subsets
int rev[maxn];  //  reversed sum of subsets (i -> ~i transform)
int popcnt[maxn];

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    for (int i = 1; i < maxn; ++i) {
        popcnt[i] = popcnt[i / 2] + (i & 1);
    }
    int l, q;
    cin >> l >> q;
    const int n = 1 << l;
    string s;
    cin >> s;
    for (int i = 0; i < n; ++i) {
        val[i] = dir[i] = rev[((1 << l) - 1) ^ i] = s[i] - '0';
    }
    for (int bit = 0; bit < l; ++bit) {
        for (int mask = 0; mask < (1 << l); ++mask) {
            if ((1 << bit) & mask) {
                dir[mask] += dir[mask ^ (1 << bit)];
                rev[mask] += rev[mask ^ (1 << bit)];
            }
        }
    }
    while (q--) {
        int mask0 = 0, mask1 = 0, mask2 = 0;
        string t;
        cin >> t;
        reverse(t.begin(), t.end());
        for (int i = 0; i < l; ++i) {
            if (t[i] == '0') mask0 |= (1 << i);
            else if (t[i] == '1') mask1 |= (1 << i);
            else mask2 |= (1 << i);
        }
        int ans = 0;
        if (popcnt[mask0] <= 6) {
            for (int mask = mask0; mask; mask = mask0 & (mask - 1)) ans += rev[mask | mask2] * (popcnt[mask ^ mask0] & 1 ? -1 : 1);
            ans += rev[mask2] * (popcnt[mask0] & 1 ? -1 : 1);
        } else if (popcnt[mask1] <= 6) {
            for (int mask = mask1; mask; mask = mask1 & (mask - 1)) ans += dir[mask | mask2] * (popcnt[mask ^ mask1] & 1 ? -1 : 1);
            ans += dir[mask2] * (popcnt[mask1] & 1 ? -1 : 1);
        } else {
            for (int mask = mask2; mask; mask = mask2 & (mask - 1)) ans += val[mask1 | mask];
            ans += val[mask1];
        }
        cout << ans << '\n';
    }
}

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