Submission #1052150

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052150		vjudge1	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	1215 ms	55412 KiB

snake_escaping

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pi;
typedef pair<long long,long long> pl;

#define all(s) s.begin(),s.end()
#define F first
#define S second
#define sz(a) a.size()

const ll mod = 1e9+7;
const ll INF = 1e18;
const int inf = 1e9+200;
const int N=1e5 + 10;

int n,q;
ll a[11*N];
ll sub[11*N],sup[11*N];

void solve() {
    cin>>n>>q;
    for(int i=0;i<(1<<n);++i) {
        char cc;
        cin>>cc;
        a[i]=(cc-'0');
    }
    for(int i=0;i<(1<<n);++i) {
        sub[i]=a[i];
        sup[i]=a[i];
    }
    for(int i=0;i<n;++i) {
        for(int mask=0;mask<(1<<n);++mask) {
            if(mask & (1<<i)) {
                sub[mask] += sub[mask^(1<<i)];
            }
        }
    }
    for(int i=0;i<n;++i) {
        for(int mask=(1<<n)-1;mask>=0;--mask) {
            if(!(mask & (1<<i))) {
                sup[mask] += sup[mask^(1<<i)];
            }
        }
    }
    while(q--) {
        string s;
        cin>>s;
        int cnt[3];
        fill(cnt,cnt+3,0);
        ll sum=0;
        vector<int> b;
        reverse(all(s));
        vector<int> b1;
        vector<int> b2;
        for(int i=0;i<n;++i) {
            if(s[i]=='?') {
                cnt[2]++;
                b.push_back(i);
            }
            else if(s[i]=='1') {
                cnt[1]++;
                sum+=(1<<i);
                b1.push_back(i);
            }
            else {
                cnt[0]++;
                b2.push_back(i);
            }
        }
        if(cnt[2]<=6) {
            int ans = 0;
            for(int mask=0;mask<(1<<cnt[2]);++mask) {
                int t=0;
                for(int i=0;i<cnt[2];++i) {
                    if((mask>>i)&1) {
                         t+=(1<<(b[i]));
                    }
                }
                ans+=a[sum + t];
            }
            cout<<ans<<'\n';
        }
        else if(cnt[1]<=6) {
            int ans = 0;
            for(int i=0;i<n;++i) {
                if(s[i]=='?'){
                    sum+=(1<<i);
                }
            }
            for(int mask=0;mask<(1<<cnt[1]);++mask) {
                int t=0;
                for(int i=0;i<cnt[1];++i) {
                    if(!((mask>>i)&1)) {
                        t+=(1<<(b1[i]));
                    }
                }
                if((cnt[1]-__builtin_popcount(mask))&1) {
                    ans-=sub[sum-t];
                }
                else {
                    ans+=sub[sum-t];
                }
            }
            cout<<ans<<'\n';
        }
        else if(cnt[0]<=6) {
            int ans = 0;
            for(int mask=0;mask<(1<<cnt[0]);++mask) {
                int t=0;
                for(int i=0;i<cnt[0];++i) {
                    if(((mask>>i)&1)) {
                        t+=(1<<(b2[i]));
                    }
                }
                if((__builtin_popcount(mask))&1) {
                    ans-=sup[sum+t];
                }
                else {
                    ans+=sup[sum+t];
                }
            }
            cout<<ans<<'\n';
        }
    }
}  

int main() {
    ios_base::sync_with_stdio(0) , cin.tie(0) , cout.tie(0);
    int T=1;
    //cin>>T;
    while(T--) {
        solve();
    }
    return 0;
} 

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