Submission #759589

#	Time	Username	Problem	Language	Result	Execution time	Memory
759589		bgnbvnbv	Snake Escaping (JOI18_snake_escaping)	C++14	100 / 100	1277 ms	39236 KiB

snake_escaping

#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<int,int>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=2e5;
const ll inf=1e18;
const ll mod=1e9+7;
int f[1<<20],g[1<<20];
string s;
ll L;
ll q;
int n(const int &x)
{
    ll ans=0;
    for(int i=0;i<L;i++)
    {
        if((x>>i&1)==0)
        {
            ans+=1<<i;
        }
    }
    return ans;
}
ll a[maxN];
void solve()
{
    cin >> L >> q;
    cin >> s;
    for(int i=0;i<(1<<L);i++)
    {
        f[i]=s[i]-'0';
    }
    for(int i=0;i<(1<<L);i++)
    {
        g[i]=s[n(i)]-'0';
    }
    for(int i = 0;i < L; ++i) for(int mask = 0; mask < (1<<L); ++mask){
        if((mask & (1<<i))==0)
            f[mask] += f[mask^(1<<i)];
    }
    for(int i = 0;i < L; ++i) for(int mask = 0; mask < (1<<L); ++mask){
        if((mask & (1<<i))==0)
            g[mask] += g[mask^(1<<i)];
    }
    while(q--)
    {
        string t;
        cin >> t;
        ll cnt[3]={0};
        for(int i=0;i<L;i++)
        {
            if(t[i]=='0') cnt[0]++;
            else if(t[i]=='1') cnt[1]++;
            else cnt[2]++;
        }
        ll mn=inf;
        for(int i=0;i<3;i++) mn=min(mn,cnt[i]);
        if(cnt[0]==mn)
        {
            ll ct=0,so=0;
            for(int i=0;i<L;i++)
            {
                if(t[i]=='0')
                {
                    a[ct]=L-i-1;
                    ct++;
                }
                else if(t[i]=='1')
                {
                    so+=1<<(L-i-1);
                }
            }
            ll ass=0,bs;
            for(int i=0;i<(1<<ct);i++)
            {
                bs=0;
                for(int j=0;j<ct;j++)
                {
                    if(i>>j&1)
                    {
                        bs+=1<<(a[j]);
                    }
                }
                if(__builtin_popcount(i)&1) ass-=f[so+bs];
                else ass+=f[so+bs];
            }
            cout << ass << '\n';
        }

        else if(cnt[1]==mn)
        {
            ll ct=0,so=0;
            for(int i=0;i<L;i++)
            {
                if(t[i]=='1')
                {
                    a[ct]=L-i-1;
                    ct++;
                }
                else if(t[i]=='0')
                {
                    so+=1<<(L-i-1);
                }
            }
            ll ans=0,bs;
            for(int i=0;i<1<<ct;i++)
            {
                bs=0;
                for(int j=0;j<ct;j++)
                {
                    if(i>>j&1)
                    {
                        bs+=1<<(a[j]);
                    }
                }
                if(__builtin_popcount(i)&1) ans-=g[so+bs];
                else ans+=g[so+bs];
            }
            cout << ans << '\n';
        }

        else
        {
            ll so=0,ct=0;
            for(int i=0;i<L;i++)
            {
                if(t[i]=='1')
                {
                    so+=1<<(L-i-1);
                }
                else if(t[i]=='?') a[ct]=L-i-1,ct++;
            }
            ll ans=0;
            for(int i=0;i<1<<ct;i++)
            {
                ll bs=0;
                for(int j=0;j<ct;j++)
                {
                    if(i>>j&1)
                    {
                        bs+=1<<a[j];
                    }
                }
                ans+=s[bs+so]-'0';
            }
            cout << ans << '\n';
        }
    }

}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

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