Submission #1094545

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094545		BLOBVISGOD	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	527 ms	43512 KiB

snake_escaping

#include "bits/stdc++.h"
using namespace std;
#define rep(i,a,b) for(int i=(a); i<(b); ++i)
#define all(x) x.begin(),x.end()
#define sz(x) int(x.size())
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;

const int L = 20;
int SOS[3][1<<L];


int main(){
    cin.tie(NULL),cin.sync_with_stdio(false);
    
    int l,q; cin >> l >> q;
    int msk_all = (1<<l)-1;
    string s; cin >> s;
    rep(i,0,1<<l){
        // ones
        SOS[1][i] = SOS[2][i] = int(s[i]-'0');
        SOS[0][msk_all^i] = int(s[i]-'0');
    }

    rep(X,0,2) rep(i,0,l) rep(mask,0,1<<l) if (mask&(1<<i)) SOS[X][mask] += SOS[X][mask^(1<<i)]; 
    
    while (q--){
        string s; cin >> s;
        reverse(all(s));
        if (count(all(s),'?') < 7){
            int qmask = 0, omask = 0;
            rep(i,0,l) {
                if (s[i] == '?') qmask |= 1<<i;
                else if (s[i] == '1') omask |= 1<<i;
            }
            int ans = 0, msk = qmask;
            while (msk){
                ans += SOS[2][msk|omask];
                msk = (msk-1)&qmask;
            } ans += SOS[2][omask];
            cout << ans << '\n';
        }else if (count(all(s),'1') < 7){
            int ans = 0, qmask = 0, omask = 0;
            rep(i,0,l) {
                if (s[i] == '?') qmask |= 1<<i;
                else if (s[i] == '1') omask |= 1<<i;
            }
            int msk = omask;
            while (msk){
                ans += (1-2*(__builtin_popcount(msk)&1))*SOS[1][msk|qmask];
                msk = (msk-1)&omask;
            } ans += SOS[1][qmask];
            cout << abs(ans) << '\n';
        }else{
            int ans = 0, qmask = 0, omask = 0;
            rep(i,0,l) {
                if (s[i] == '?') qmask |= 1<<i;
                else if (s[i] == '0') omask |= 1<<i;
            }
            int msk = omask;
            while(msk){
                ans += (1-2*(__builtin_popcount(msk)&1))*SOS[0][msk|qmask];
                msk = (msk-1)&omask;
            } ans += SOS[0][qmask];
            cout << abs(ans) << '\n';
        }
    }




    

}

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