Submission #1034413

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034413		Shayan86	Snake Escaping (JOI18_snake_escaping)	C++14	100 / 100	588 ms	43508 KiB

snake_escaping

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

#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// Ofast, O0, O1, O2, O3, unroll-loops, fast-math, trapv

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

#define Mp          make_pair
#define sep         ' '
#define endl        '\n'
#define F	        first
#define S	        second
#define pb          push_back
#define SZ(x)       (int)x.size()
#define all(x)      (x).begin(),(x).end()
#define kill(res)	cout << res << '\n', exit(0);
#define set_dec(x)	cout << fixed << setprecision(x);
#define fast_io     ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io     freopen("input.txt", "r", stdin) ; freopen("output.txt", "w", stdout);

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll N = 22;
const ll Mod = 1e9 + 7;

int n, q, cnt[(1 << N)], sos[2][(1 << N)];

string s;

int main(){
    fast_io;
    
    cin >> n >> q >> s;

    for(int i = 0; i < (1 << n); i++){
        cnt[i] = s[i] - '0';
        sos[0][i] = sos[1][i] = cnt[i];
    }

    for(int i = 0; i < n; i++) for(int mask = (1 << n)-1; mask >= 0; mask--) if(mask >> i & 1) sos[0][mask] += sos[0][mask^(1 << i)];
    for(int i = 0; i < n; i++) for(int mask = 0; mask < (1 << n); mask++) if((mask >> i & 1) == 0) sos[1][mask] += sos[1][mask^(1 << i)];

    while(q--){
        string t; cin >> t;
        reverse(all(t));

        int c[3] = {0, 0, 0};
        for(int i = 0; i < n; i++){
            if(t[i] == '?') c[2]++;
            else c[t[i]-'0']++;
        }

        int mask[3] = {0, 0, 0}, num[2];
        for(int i = 0; i < n; i++){
            if(t[i] == '?') mask[2] += (1 << i);
            else mask[t[i]-'0'] += (1 << i);
        }
        num[0] = mask[1];
        num[1] = mask[1] | mask[2];

        int res = 0;
        if(c[0] <= 6){
            res = sos[1][num[0]];
            for(int i = mask[0]; i > 0; i = (i-1)&mask[0]) res += (__builtin_popcount(i) & 1 ? -1 : 1) * sos[1][num[0]|i];
        }
        else if(c[1] <= 6){
            res = sos[0][num[1]];
            for(int i = mask[1]; i > 0; i = (i-1)&mask[1]) res += (__builtin_popcount(i) & 1 ? -1 : 1) * sos[0][num[1]^i];
        }
        else{
            res = cnt[num[0]];
            for(int i = mask[2]; i > 0; i = (i-1)&mask[2]) res += cnt[num[0]|i];
        }

        cout << res << endl;
    }

}

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