Submission #926985

#	Time	Username	Problem	Language	Result	Execution time	Memory
926985		manizare	Snake Escaping (JOI18_snake_escaping)	C++14	100 / 100	653 ms	49832 KiB

snake_escaping

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define S second 
#define ld long double
#define all(a) a.begin(),a.end()
#define int long long 
#define pii pair <int,int>
#define PII pair<pii , pii>
#define sz(v) (int)v.size()
#define rep(i , a , b) for(int i=a;i <= (b);i++)
#define per(i , a , b) for(int i=a;i >= (b);i--)
#define deb(x) cout <<#x << " : " << x << "\n" ;
using namespace std ;
const int maxn = 2e6 + 10  , c = 6 , maxp = 15e5 + 10 , inf=  1e18+10 ;
int d1[maxn] , d2[maxn] ;
signed main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n  ,q ;
    cin >> n >> q; 
    string s;
    cin >> s ;
    rep(i , 0 , (1<<n)-1){
        d1[i] = (s[i]-'0'); 
        d2[i] = (s[i]-'0');
    }
    rep(i , 0 , n-1){
        rep(j , 0 , (1<<n)-1){
            if(j>>i&1){
                d2[j]+=d2[j^(1<<i)] ;
            }else{
                d1[j]+=d1[j^(1<<i)] ;
            }
        }
    }
    while(q--){
        string t;
        cin >> t ;
        reverse(all(t)) ;
        int a=0,b=0,c=0;
        rep(i , 0 ,n-1){
            if(t[i]=='?')a+=(1<<i);
            if(t[i]=='0')b+=(1<<i);
            if(t[i]=='1')c+=(1<<i);
        }
        if(__builtin_popcount(a) <=6){
            int ans =0;
            for(int ms = a ; ; ms = (ms-1)&a){
                ans += s[ms|c]-'0' ;
                if(ms == 0)break ;
            }
            cout << ans << "\n";
            continue;
        }
        if(__builtin_popcount(b) <= 6){
            int ans =0 ;
            for(int ms = b ; ; ms = (ms-1)&b){
                if(__builtin_popcount(ms)%2){
                    ans -= d1[ms|c]; 
                }else{
                    ans += d1[ms|c] ;
                }
                if(ms==0)break ;
            }
            cout << ans << "\n";
            continue ;
        }
        int ans = 0 ;
        for(int ms = c ;  ;ms = (ms-1)&c){
            if((__builtin_popcount(c)-__builtin_popcount(ms))%2){
                ans -= d2[ms|a] ;
            }else{
                ans += d2[ms|a] ;
            }
            if(ms==0)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