Submission #1239327

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239327		dwuy	Snake Escaping (JOI18_snake_escaping)	C++17	22 / 100	259 ms	9960 KiB

snake_escaping

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

const int MX = MASK(20);
int n, m;
string s;
int f[MX], rf[MX];

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

    cin >> n >> m;
    cin >> s;
    
    for(int i=0; i<MASK(n); i++) f[i] = rf[i] = s[i] - '0';
    for(int i=0; i<n; i++){
        for(int mask=0; mask<MASK(n); mask++){
            mask |= MASK(i);
            f[mask] += f[mask ^ MASK(i)];
            rf[mask ^ MASK(i)] += rf[mask];
        }
    }
    
    while(m--){
        string s; cin >> s;
        reverse(s.begin(), s.end());
        int m0, m1, m2; m0 = m1 = m2 = 0;
        for(int i=0; i<n; i++){
            if(s[i] == '0') m0 += MASK(i);
            if(s[i] == '1') m1 += MASK(i);
            if(s[i] == '?') m2 += MASK(i);
        }
        
        int ans = 0;
        if(__builtin_popcount(m0) < 7){
            for(int mask=m0; ;mask=(mask - 1)&m0){
                if(__builtin_popcount(mask)&1) ans -= rf[m1|mask];
                else ans += rf[m1|mask];
                if(mask == 0) break;
            }
        }
        else if(__builtin_popcount(m1) < 7){
            for(int mask=m1; ;mask=(mask - 1)&m1){
                if(__builtin_popcount(mask^m1   )&1) ans -= f[m2|mask];
                else ans += f[m2|mask];
                if(mask == 0) break;
            }
        }
        else{
            for(int mask=m2; ;mask=(mask - 1)&m2){  
                ans += s[m1 | mask] - '0';
                if(mask == 0) break;
            }
        }
        cout << ans << '\n';
    }
    
    return 0;
}

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