Submission #1031324

#	Time	Username	Problem	Language	Result	Execution time	Memory
1031324		dwuy	Snake Escaping (JOI18_snake_escaping)	C++14	100 / 100	521 ms	39576 KiB

snake_escaping

#include <bits/stdc++.h>
#define MASK(x) (1LL<<(x))
#define endl '\n'
using namespace std;

const int MX = MASK(20) + 5;
int n, q;
string a;

int f1[MX];
int f2[MX];

void nhap(){
    cin >> n >> q;
    cin >> a;
}

void solve(){
    for(int i=0; i<MASK(n); i++){
        f1[i] = f2[i] = a[i] - '0';
    }
    for(int i=0; i<n; i++){
        for(int mask=0; mask<MASK(n); mask++){
            if(mask&MASK(i)) f2[mask] += f2[mask^MASK(i)];
            else f1[mask] += f1[mask^MASK(i)];
        }
    }
    while(q--){
        string s; cin >> s;
        int m0 = 0;
        int m1 = 0;
        int m2 = 0;
        for(char c: s){
            m0 = (m0 << 1) | (c == '0'? 1 : 0);
            m1 = (m1 << 1) | (c == '1'? 1 : 0);
            m2 = (m2 << 1) | (c == '?'? 1 : 0);
        }
        #define cntbit(x) __builtin_popcount(x)
        int ans = 0;
        if(cntbit(m0) < 7){
            for(int mask=m0; ; mask=(mask - 1)&m0){
                ans += cntbit(mask)&1? -f1[m1|mask] : f1[m1|mask];
                if(mask == 0) break;
            }
        }
        else if(cntbit(m1) < 7){
            for(int mask=m1; ; mask=(mask - 1)&m1){
                ans += (cntbit(m1) - cntbit(mask))&1? -f2[m2|mask] : f2[m2|mask];
                if(mask == 0) break;
            }
        }
        else if(cntbit(m2) < 7){
            for(int mask=m2; ; mask=(mask - 1)&m2){
                ans += a[mask|m1] - '0';
                if(mask == 0) break;
            }
        }
        cout << ans << endl;
    }
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    nhap();
    solve();

    return 0;
}

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