Submission #1100773

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100773		louis_no_pro	Snake Escaping (JOI18_snake_escaping)	C++14	0 / 100	1 ms	336 KiB

snake_escaping

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define ALL(v) (v).begin(), (v).end()
#define pb push_back
#define fu(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define fd(i, a, b) for (int i = (b), _a = (a); i >= _a; --i)
#define REP(i, n) for (int i = 1, _n = (n); i <= _n; ++i)
#define el cout << "\n"
#define MAX_SIZE 1000005
#define LOG 21
#define MOD (ll)(1e9 + 7)
#define INF (ll)(1e15)

using namespace std;
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());

template <class T1, class T2>
bool maximize(T1 &a, T2 b) {if (a < b){a = b; return true;} return false;}

template <class T1, class T2>
bool minimize(T1 &a, T2 b) {if (a > b){a = b; return true;} return false;}

template <class T1, class T2>
void add(T1 &a, T2 b) {a += b; if (a >= MOD) a -= MOD;}

template <class T1, class T2>
void sub(T1 &a, T2 b) {a -= b; if (a < 0) a += MOD;}

template <class T>
void dup_shot(vector <T> &v) {
    sort(ALL(v));
    v.erase(unique(ALL(v)), (v).end());
}

int l, q;
ll sum[MASK(20) + 3][2];
// 0: super
// 1: sub

void init() {
    cin >> l >> q;
    fu(i, 0, MASK(l) - 1) {
        char c; cin >> c;
        sum[i][0] = sum[i][1] = (c - '0');
    }
}

void run() {
    fu(i, 0, l - 1) {
        fu(mask, 0, MASK(l) - 1) if (BIT(mask, i)) sum[mask][1] += sum[mask ^ MASK(i)][1];
        fd(mask, 0, MASK(l) - 1) if (!BIT(mask, i)) sum[mask][0] += sum[mask ^ MASK(i)][0];
    }

    while (q--) {
        string s;
        cin >> s;
        reverse(ALL(s));

        int mask0 = 0, mask1 = 0, mask2 = 0;
        fu(i, 0, l - 1) {
            if (s[i] == '0') mask0 += MASK(i);
            if (s[i] == '1') mask1 += MASK(i);
            if (s[i] == '?') mask2 += MASK(i);
        }

        if (__builtin_popcount(mask0) <= 6) {
            ll res = 0;
            for (int mask = mask0; mask >= 0; mask = (mask - 1) & mask0) {
                if (__builtin_popcount(mask) & 1) res -= sum[mask + mask1][0];
                else res += sum[mask + mask1][0];
                if (mask == 0) break;
            }
            cout << res << "\n";
        }
        else if (__builtin_popcount(mask1) <= 6) {
            ll res = 0;
            for (int mask = mask0; mask >= 0; mask = (mask - 1) & mask1) {
                if (__builtin_popcount(mask) & 1) res -= sum[MASK(l) - 1 - mask0 - mask][1];
                else res += sum[MASK(l) - 1 - mask0 - mask][1];
                if (mask == 0) break;
            }
            cout << res << "\n";
        }
        else {
            ll res = 0;
            for (int mask = mask2; mask >= 0; mask = (mask - 1) & mask2) {
                res += sum[mask + mask1][1];
                if (mask == 0) break;
            }
            cout << res << "\n";
        }
    }
}

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

    init();
    clock_t start = clock();
    run();
    cerr << "\nTime run: " << clock() - start << " ms!\n";

    return 0;
}

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