Submission #535429

#	Time	Username	Problem	Language	Result	Execution time	Memory
535429		getac	Snake Escaping (JOI18_snake_escaping)	C++14	100 / 100	1316 ms	24716 KiB

snake_escaping

//InTheNameOfGOD 
//PRS;) 
#include<iostream> 
#define Fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); 
using namespace std; 
typedef int ll; 
const ll xn = (1 << 20) + 5; 
ll dp[xn][2], a[xn], cnt[xn]; 
int main() 
{ 
    Fast 
    ll n, q; 
    cin >> n >> q; 
    for(ll i = 1; i < (1 << n); i++) cnt[i] = cnt[i - (i & -i)] + 1; 
    for(ll i = 0; i < (1 << n); i++) 
    { 
        char c; 
        cin >> c; 
        dp[i][0] = dp[i][1] = a[i] = c - '0'; 
    } 
    for(ll j = 0; j < n; j++) for(ll i = 0; i < (1 << n); i++) 
        if((i >> j) & 1) dp[i][0] += dp[i ^ (1 << j)][0], dp[i ^ (1 << j)][1] += dp[i][1]; 
    while(q--) 
    { 
        ll t0 = 0, t1 = 0, t2 = 0, ans = 0; 
        for(ll i = 0, j = n - 1; i < n; i++, j--) 
        { 
            char c; 
            cin >> c; 
            if(c == '0') t0 |= (1 << j); 
            if(c == '1') t1 |= (1 << j); 
            if(c == '?') t2 |= (1 << j); 
        } 
        if(cnt[t0] <= n / 3) 
        { 
            for(ll prs = t0; ;prs = t0 & (prs - 1)) 
            { 
                (cnt[prs] & 1) ? ans -= dp[t1 | prs][1] : ans += dp[t1 | prs][1]; 
                if(!prs) break; 
            } 
        } 
        else if(cnt[t1] <= n / 3) 
        { 
            for(ll prs = t1; ;prs = t1 & (prs - 1)) 
            { 
                (cnt[prs ^ t1] & 1) ? ans -= dp[t2 | prs][0] : ans += dp[t2 | prs][0]; 
                if(!prs) break; 
            } 
        } 
        else
        { 
            for(ll prs = t2; ;prs= t2 & (prs - 1)) 
            { 
                ans += a[t1 | prs]; 
                if(!prs) break; 
            } 
        } 
        cout << ans << '\n'; 
    } 
    return 0; 
}

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