Submission #674599

#	Time	Username	Problem	Language	Result	Execution time	Memory
674599		beedle	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	1271 ms	51156 KiB

snake_escaping

#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <set>
#include <iterator>
#include <stack>
#include <map>
#include <math.h>
#include <bitset>
#include <deque>
#include <string>
#include <tuple>
#include <queue>
#include <numeric>
#include <complex>
#include <assert.h>
#include <unordered_set>
#include <unordered_map>
#define ll long long
#define ld long long double
#define rep(i, a, b) for (long long i = a; i <= b; i++)
#define mod 1000000007ll
#define INF 1e18
#define pb push_back
#define ff first
#define ss second
#define endl '\n'
#define all(x) (x).begin (), (x).end ()
#define sz(x) (ll) (x).size ()
#define reunique(v) v.resize(std::unique(v.begin(), v.end()) - v.begin())
#define rank rnk
#define log lg
#define fast                                                                  \
    ios_base::sync_with_stdio (false);                                        \
    cin.tie (NULL);                                                           \
    cout.tie (NULL)
 
using namespace std;

signed main()
{
    fast;

    ll l,q;
    cin>>l>>q;

    ll dp[1ll<<20], dp2[1ll<<20], v[1ll<<20];

    string s;
    cin>>s;
    rep(i,0,sz(s)-1)
    dp[(~i)&((1ll<<l)-1)]=s[i]-'0', dp2[i]=s[i]-'0', v[i]=s[i]-'0';

    rep(i,0,l-1)
    rep(mask,0,(1ll<<l)-1)
    if(mask&(1ll<<i))
    dp[mask]+=dp[mask^(1ll<<i)];

    rep(i,0,l-1)
    rep(mask,0,(1ll<<l)-1)
    if(mask&(1ll<<i))
    dp2[mask]+=dp2[mask^(1ll<<i)];

    while(q--)
    {
        string str;
        cin>>str;
        reverse(all(str));

        ll c0=0, c1=0, cq=0;
        for(auto x:str)
        if(x=='0')
        c0++;
        else if(x=='1')
        c1++;
        else
        cq++;

        ll c=min({c0,c1,cq});

        ll ans=0;

        if(c0==c)
        {
            ll mask=0, base=0;
            rep(i,0,l-1)
            if(str[i]=='?')
            base^=(1ll<<i);
            else if(str[i]=='0')
            mask^=(1ll<<i);

            for(ll submask=mask;;submask=(submask-1)&mask)
            {
                ll dir=__builtin_popcount(mask)-__builtin_popcount(submask);
                if(dir&1)
                ans-=dp[base^submask];
                else
                ans+=dp[base^submask];

                if(!submask)
                break;
            }
        }
        else if(c1==c)
        {
            ll mask=0, base=0;
            rep(i,0,l-1)
            if(str[i]=='1')
            mask^=(1ll<<i);
            else if(str[i]=='?')
            base^=(1ll<<i);

            for(ll submask=mask;;submask=(submask-1)&mask)
            {
                ll dir=__builtin_popcount(mask)-__builtin_popcount(submask);
                if(dir&1)
                ans-=dp2[base^submask];
                else
                ans+=dp2[base^submask];

                if(!submask)
                break;
            }
        } 
        else if(cq==c)
        {
            ll mask=0, base=0;
            rep(i,0,l-1)
            if(str[i]=='1')
            base^=(1ll<<i);
            else if(str[i]=='?')
            mask^=(1ll<<i);

            for(ll submask=mask;;submask=(submask-1)&mask)
            {
                ans+=v[base^submask];
                if(!submask)
                break;
            }
        }

        cout<<ans<<endl;
    }

    return 0;
}

/*
3 6
12345678 
011
000
0??
1?0
?11
???
*/

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