Submission #961215

#	Time	Username	Problem	Language	Result	Execution time	Memory
961215		efishel	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	662 ms	48020 KiB

snake_escaping

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;

const ll MAXN = 1.1E6;
ll dp1[MAXN], dp0[MAXN];

int main () {
    cin.tie(nullptr) -> sync_with_stdio(false);
    ll n, Q;
    cin >> n >> Q;
    ll ALL = (1<<n)-1;
    string str;
    cin >> str;
    for (ll i = 0; i <= ALL; i++)
        dp1[i] = str[i]-'0';
    for (ll bit = 0; bit < n; bit++)
        for (int mask = 0; mask <= ALL; mask++)
            if (mask>>bit&1) dp1[mask] += dp1[mask ^ (1<<bit)];
    for (ll i = 0; i <= ALL; i++)
        dp0[i] = str[i ^ ALL]-'0';
    for (ll bit = 0; bit < n; bit++)
        for (int mask = 0; mask <= ALL; mask++)
            if (mask>>bit&1) dp0[mask] += dp0[mask ^ (1<<bit)];
    while (Q--) {
        string q;
        cin >> q;
        reverse(q.begin(), q.end());
        int nul = 0, unu = 0, dem;
        for (ll i = 0; i < n; i++) nul |= (q[i] == '0') << i;
        for (ll i = 0; i < n; i++) unu |= (q[i] == '1') << i;
        dem = ALL ^ nul ^ unu;
        if (count(q.begin(), q.end(), '?') <= 6) {
            ll ans = 0;
            for (int mask = 0; mask <= ALL; mask++) {
                mask |= unu | nul;
                ans += str[mask ^ nul]-'0';
            }
            cout << ans << '\n';
            continue;
        }
        if (count(q.begin(), q.end(), '0') <= 6) {
            ll ans = 0;
            for (int mask = nul; ; mask--, mask &= nul) {
                bool addSub = __builtin_popcountll(mask ^ nul)%2 == 0;
                ans += (addSub ? 1 : -1) * dp0[dem | mask];
                if (!mask) break;
            }
            cout << ans << '\n';
            continue;
        }
        if (count(q.begin(), q.end(), '1') <= 6) {
            ll ans = 0;
            for (int mask = unu; ; mask--, mask &= unu) {
                bool addSub = __builtin_popcountll(mask ^ unu)%2 == 0;
                ans += (addSub ? 1 : -1) * dp1[dem | mask];
                if (!mask) break;
            }
            cout << ans << '\n';
            continue;
        }
        assert(false);
    }
    return 0;
}

/*

????? - ????0
= ????1

????? - ???00
= ???01
+ ???10
+ ???11

????? = ???00 + ???01 + ???10 + ???11
00??? = 00?00 + 00?01 + 00?10 + 00?11

iterate over all subsets of 1's, lets call it 'mask'
check the parity of 'mask^unu' and subtract/add accordingly:
    0: subtract
    1: add
what you work with is dp[maskQM^mask]

   ??????????
+dp1111111111
=
 + ???????000
+dp1111111000

 + ???????001
+dp1111111001
-dp1111111000

 + ???????010
+dp1111111010
-dp1111111000

 + ???????011
+dp1111111011
-dp1111111001
-dp1111111010
+dp1111111000

 + ???????100
+dp1111111100
-dp1111111000

 + ???????101
+dp1111111101
-dp1111111001
-dp1111111100
+dp1111111000

 + ???????110
+dp1111111110
-dp1111111010
-dp1111111100
+dp1111111000

 + ???????111
+dp1111111111
-dp1111111011
-dp1111111101
-dp1111111110
+dp1111111001
+dp1111111010
+dp1111111100
-dp1111111000


// tallied up

 + ???????000
 + ???????001
 + ???????010
 + ???????011
 + ???????100
 + ???????101
 + ???????110
 + ???????111
=
+dp1111111111


// 

-dp1111111111
+dp1111111011
+dp1111111101
+dp1111111110
-dp1111111001
-dp1111111010
-dp1111111100
+dp1111111000

// AHAHAHAHAH TEHWYW WEOUHWEOYHWE HUWHYYYYW HYYY WHYYYY WHYY TOAEUNOAEUNOHEUNSHOASENU HOANEHUOMG OMG WYH
 + ???????111
-dp1111111111
+dp1111111011
+dp1111111101
+dp1111111110
-dp1111111001
-dp1111111010
-dp1111111100
+dp1111111000


*/

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