Submission #1043045

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043045		ooscode	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	1521 ms	43344 KiB

snake_escaping

#include <bits/stdc++.h>

using namespace std;

// #define int long long
#define F first
#define S second
#define pb push_back
#define all(x) x.begin() , x.end()
#define debug while(1) cout << "Test\n"

#pragma GCC optimize ("O3,unroll-loops")
#pragma GCC target ("avx2")

const int N = (1ll << 20) + 10;
const int INF = 1e18 + 10;
const int mod = 1e9;

int n , q;
int sub[N];
int sup[N];
int a[N];

int main() {
    int n , q;
    cin >> n >> q;
    int l = n; n = (1ll << n);

    string s;
    cin >> s;
    for(int i = 0 ; i < n ; i++) {
        a[i] = s[i] - '0';
        sub[i] = a[i];
        sup[i] = a[i];
    }

    for(int i = 0 ; i < l ; i++) {
        for(int msk = n-1 ; ~msk ; msk--) if((1ll << i) & msk) sub[msk] += sub[msk ^ (1ll << i)];
        for(int msk = 0 ; msk < n ; msk++) if(!((1ll << i) & msk)) sup[msk] += sup[msk ^ (1ll << i)];
    }

    while(q--) {
        string t;
        cin >> t;
        
        int mask[3] = {0};
        int cnt[3] = {0};

        for(int i = 0 ; i < l ; i++) {
            int ty;
            if(t[t.size()-i-1] == '0') ty = 0;
            else if(t[t.size()-i-1] == '1') ty = 1;
            else ty = 2;

            mask[ty] |= (1ll << i);
            cnt[ty]++;
        }

        if(cnt[2] <= 6) {
            int ans = 0;
            for(int msk = mask[2] ; ; msk = (msk - 1) & mask[2]) {
                // cout << msk << " qu\n";
                ans += a[msk | mask[1]];
                if(msk == 0) break;
            }
            cout << ans << "\n";
            continue;
        }

        if(cnt[1] <= 6) {
            int ans = 0;
            for(int msk = mask[1] ; ; msk = (msk - 1) & mask[1]) {
                if(__builtin_popcount(msk) & 1) ans -= sub[(mask[1] ^ msk) | mask[2]];
                else ans += sub[(mask[1] ^ msk) | mask[2]];
                if(msk == 0) break;
            }
            cout << ans << "\n";
            continue;
        }

        int ans = 0;
        for(int msk = mask[0] ; ; msk = (msk - 1) & mask[0]) {
            if(__builtin_popcount(msk) & 1) ans -= sup[msk | mask[1]];
            else ans += sup[msk | mask[1]];
            if(msk == 0) break;
        }
        cout << ans << "\n";
    }
}

Compilation message (stderr)

snake_escaping.cpp:16:22: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   16 | const int INF = 1e18 + 10;
      |                 ~~~~~^~~~

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