제출 #1196199

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1196199		g4yuhg	Snake Escaping (JOI18_snake_escaping)	C++20	100 / 100	920 ms	33348 KiB

snake_escaping

#include<bits/stdc++.h>
typedef long long ll;
#define endl '\n'
#define fi first
#define se second
#define N 2000006
#define LOG 20
using namespace std;
ll getbit(ll mask, ll i) {
    return (mask >> i) & 1;
}
ll onbit(ll mask, ll i) {
    return mask | (1 << i);
}
ll a[N];
ll n, q, sub[N], super[N];
ll solve1(string s, ll n) {
    vector<ll> pos;
    ll tmask = 0;
    for (int i = 0; i < s.size(); i ++) {
        char it = s[i];
        if (it == '?') pos.push_back(i);
        else if (it == '1') tmask = onbit(tmask, i);
    }
    /*for (auto it : pos) {
        cout << it << " ";
    }
    cout << endl;*/
    ll ans = 0;
    for (int mask = 0; mask < (1 << n); mask ++) {
        ll gmask = tmask;
        for (int i = 0; i < n; i ++) {
            if (getbit(mask, i)) {
                gmask = onbit(gmask, pos[i]);
            }
        }
        /*for (int i = s.size() - 1; i >= 0; i --) {
            cout << getbit(gmask, i);
        }
        cout << endl;*/
        ans += a[gmask];
    }
    return ans;
}
ll solveB(string s, ll B) {
    ll maskB = 0, maskC = 0;
    for (int i = 0; i < s.size(); i ++) {
        char it = s[i];
        if (it == '?') maskC = onbit(maskC, i);
        else if (it == '1') maskB = onbit(maskB, i);
    }
    ll ans = 0;
    for (int mask = maskB; mask >= 0; mask = (mask - 1) & maskB) {
        ll hs = 1; if ((B - __builtin_popcount(mask)) % 2 == 1) hs = -1;
        ans = ans + hs * sub[maskC | mask];
        if (mask == 0) break;
    }
    return ans;
}
ll solveA(string s, ll A) {
    ll maskB = 0, maskA = 0;
    for (int i = 0; i < s.size(); i ++) {
        char it = s[i];
        if (it == '1') maskB = onbit(maskB, i);
        else if (it == '0') maskA = onbit(maskA, i);
    }
    ll ans = 0;
    for (int mask = maskA; mask >= 0; mask = (mask - 1) & maskA) {
        ll hs = 1; if ((__builtin_popcount(mask)) % 2 == 1) hs = -1;
        ans = ans + hs * super[maskB | mask];
        if (mask == 0) break;
    }
    return ans;
}
void pre() {
    for (int i = 0; i < n; i ++) {
        for (int mask = 0; mask < (1 << n); mask ++) {
            if (getbit(mask, i)) {
                sub[mask] += sub[mask ^ (1 << i)];
            }
        }
        for (int mask = (1 << n) - 1; mask >= 0; mask --) {
            if (getbit(mask, i)) {
                super[mask ^ (1 << i)] += super[mask];
            }
        }
    }
    return;
    for (int i = 0; i < n; i++) {
        for (int mask = 0; mask < (1 << n); mask++) {
            if (mask & (1 << i)) sub[mask] += sub[mask ^ (1 << i)];
            else super[mask] += super[mask ^ (1 << i)];
        }
    }
}
signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> q;
    for (int i = 0; i < (1 << n); i ++) {
        char u; cin >> u;
        a[i] = u - '0';
        sub[i] = a[i]; super[i] = a[i];
        //cout << a[i] << " ";
    }
    pre();
    //cout << endl;
    for (int id = 1; id <= q; id ++) {
        string u;
        cin >> u;
        reverse(u.begin(), u.end());
        //cout << "u: " << u << endl;
        ll A = 0, B = 0, C = 0;
        for (auto c : u) {
            if (c == '?') C ++ ;
            if (c == '1') B ++ ;
            if (c == '0') A ++ ;
        }
        if (C <= 6) {
            cout << solve1(u, C) << endl;
        }
        else if (A <= 6) {
            cout << solveA(u, A) << endl;
        }
        else {
            cout << solveB(u, B) << endl;
        }
    }
    return 0;
}

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