Submission #522324

#	Time	Username	Problem	Language	Result	Execution time	Memory
522324		fallingstar	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	686 ms	47960 KiB

snake_escaping

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 1e6 + 2;

int f[1 << 20];
int ans[N];
unsigned char type[N];       // 255 if ?, otherwise 0/1 for majority
long long masks[N];

int get_mask(const string& s, char target)
{
    int mask = 0;
    for (auto ch : s) {
        mask <<= 1;
        mask |= ch == target;
    }
    return mask;
}

int main()
{
    cin.tie(NULL); ios_base::sync_with_stdio(false);
    int l, q; cin >> l >> q;
    string toxicity; cin >> toxicity;

    for (int i = 0; i < q; ++i) {
        string s; cin >> s;
        long long maskQ = get_mask(s, '?');
        long long mask0 = get_mask(s, '0');
        long long mask1 = get_mask(s, '1');
        masks[i] = (maskQ << 40) | (mask1 << 20) | mask0;

        int cnt[3] = {};
        for (auto ch : s)
            ++cnt[ch == '?' ? 2 : ch - '0'];
        int mn = *min_element(cnt, cnt + 3);
        if (cnt[2] == mn) {
            int maskQ = masks[i] >> 40;
            int mask1 = (masks[i] >> 20) & ((1 << 20) - 1);
            for (int submask = maskQ; submask > 0; submask = (submask - 1) & maskQ)
                ans[i] += toxicity[mask1 | submask] - '0';
            ans[i] += toxicity[mask1] - '0';    // all 0
            type[i] = 255;
        }
        else
            type[i] = cnt[0] > cnt[1];
    }

    transform(toxicity.begin(), toxicity.end(), f, [](char ch) { return ch - '0'; });
    for (int b = 0; b < l; ++b)
        for (int i = 0; i < 1 << l; ++i)
            if ((i >> b) & 1)
                f[i] += f[i ^ (1 << b)];
    for (int i = 0; i < q; ++i)
        if (type[i] == 1) {
            int maskQ = masks[i] >> 40;
            int mask1 = (masks[i] >> 20) & ((1 << 20) - 1);
            for (int submask = mask1; submask > 0; submask = (submask - 1) & mask1) // mask of 0 within 1
                ans[i] += f[maskQ | (mask1 ^ submask)] * (__builtin_popcount(submask) & 1 ? -1 : 1);
            ans[i] += f[maskQ | mask1];     // base: all 1 are ?
        }

    transform(toxicity.begin(), toxicity.end(), f, [](char ch) { return ch - '0'; });
    for (int b = 0; b < l; ++b)
        for (int i = (1 << l) - 1; i >= 0; --i)
            if (!((i >> b) & 1))
                f[i] += f[i ^ (1 << b)];
    int fullmask = (1 << l) - 1;
    for (int i = 0; i < q; ++i)
        if (type[i] == 0) {
            int maskQ = masks[i] >> 40;
            int mask0 = masks[i] & ((1 << 20) - 1);
            for (int submask = mask0; submask > 0; submask = (submask - 1) & mask0) // mask of 1 within 0
                ans[i] += f[fullmask ^ (maskQ | (mask0 ^ submask))] * (__builtin_popcount(submask) & 1 ? -1 : 1);
            ans[i] += f[fullmask ^ (maskQ | mask0)];     // base: all 0 are ?
        }

    for (int i = 0; i < q; ++i) cout << ans[i] << '\n';
    return 0;
}

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