Submission #1304116

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304116		trung_tin	Snake Escaping (JOI18_snake_escaping)	C++20	100 / 100	1079 ms	17688 KiB

snake_escaping

#include<bits/stdc++.h>
using namespace std;


typedef long long ll;
typedef pair<ll, ll> ii;
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x.size())
#define MASK(i) (1ll << i)
#define debug cout << "[Debug line] " << __LINE__ << ": "


const int N = 20;
const int M = 2e3 + 5;
const int INF = INT_MAX;


int L, q;
string s;
int a[MASK(N) + 5], f[MASK(N) + 5];


void solve() {
    cin >> L >> q >> s;

    for (int i = 0; i < sz(s); i++) {
        f[i] = a[i] = s[i] - '0';
    }

    int full = MASK(L) - 1;
    for (int i = 0; i < L; i++) {
        for (int mask = 0; mask <= full; mask++) {
            if (!(mask >> i & 1)) {
                f[mask] += f[mask ^ MASK(i)];
            }
        }
    }

    for (int i = 1; i <= q; i++) {
        string T; cin >> T;

        int mask0, mask1, maskQues;
        mask0 = mask1 = maskQues = 0;

        int c0, cQ;
        c0 = cQ = 0;

        for (int j = L - 1; j >= 0; j--) {
            if (T[j] == '0') {
                c0++; mask0 += MASK(L - j - 1);
            }
            else if (T[j] == '1') {
                mask1 += MASK(L - j - 1);
            }
            else {
                cQ++; maskQues += MASK(L - j - 1);
            }
        }

        int res = 0;
        if (c0 < cQ) {
            res = f[mask1];
            for (int sub = mask0; sub != 0; sub = (sub - 1) & mask0) {
                if (__builtin_popcount(sub) & 1) res -= f[sub | mask1];
                else res += f[sub | mask1];
            }
        }
        else {
            res = a[mask1];
            for (int sub = maskQues; sub != 0; sub = (sub - 1) & maskQues) {
                res += a[mask1 | sub];
            }
        }

        cout << res << '\n';
    }

}


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

//    #define TASK "PERMATRIX"
//    freopen(TASK".inp", "r", stdin);
//    freopen(TASK".out", "w", stdout);

    int T = 1;
//    cin >> T;
    while (T--) {
        solve();
    }
}

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