Submission #431860

#	Time	Username	Problem	Language	Result	Execution time	Memory
431860		hackerbhaiya	Snake Escaping (JOI18_snake_escaping)	C++14	0 / 100	1 ms	332 KiB

snake_escaping

#include<bits/stdc++.h>
// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx,avx2,fma")
// #pragma GCC optimization("unroll-loops")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC optimize("fast-math")
// #pragma GCC optimize("no-stack-protector")
#define ll long long
// #define ll ll
#define f(i,a,b) for(ll i=a;i<b;i++)
// #define mod 1000000007
#define mod 998244353
#define mp make_pair
#define uniq(v) (v).erase(unique(all(v)),(v).end())
#define ff first
#define ss second
#define rf(i,a,b) for(ll i=a;i>=b;i--)
#define sc(a) scanf("%lld",&a)
#define pf prllf
#define sz(a) (ll)(a.size())
#define psf push_front
#define ppf pop_front
#define ppb pop_back
#define pb push_back
#define pq priority_queue
#define all(s) s.begin(),s.end()
#define sp(a) setprecision(a)
#define rz resize
#define ld long double
#define inf (ll)1e18
#define ub upper_bound
#define lb lower_bound
#define bs binary_search
#define eb emplace_back
const double pi = acos(-1);
// ll binpow(ll a, ll b){ll res=1;while(b!=0){if(b&1)res*=a;a*=a;b>>=1;}return res;}
ll binpow(ll a, ll b, ll md){ll res=1;while(b!=0){if(b&1)res*=a,res%=md;a*=a,a%=md;b>>=1;}return res%md;}
 
using namespace std; 

int n,q;
string s;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // freopen("gift1.in","r",stdin);
    // freopen("gift1.out","w",stdout);
// #ifndef ONLINE_JUDGE
//     freopen("input.txt","r",stdin);
//     freopen("output.txt","w",stdout);
// #endif
    int z=1;
    // cin>>z;
    while(z--)
    {     
        cin>>n>>q>>s;
        int sup[1<<n|1],sub[1<<n|1],cnt[1<<n|1];
        for(int mask=0;mask<(1<<n);mask++)
            sub[mask]=sup[mask]=(s[mask]-'0'),cnt[mask]=__builtin_popcount(mask);
        f(i,0,n)
        {
            for(int mask=0;mask<(1<<n);mask++)
            {
                if(mask&(1<<i))
                    sub[mask]+=sub[mask^(1<<i)];
                else
                    sup[mask]+=sup[mask^(1<<i)];
            }
        }
        while(q--)
        {
            string str;
            cin>>str;
            reverse(all(str));
            int mask1=0,mask2=0,mask3=0;
            f(i,0,n)
            {
                if(str[i]=='?')
                    mask1|=(1<<i);
                else if(str[i]=='0')
                    mask2|=(1<<i);
                else
                    mask3|=(1<<i);
            }
            int ans=0;
            if(cnt[mask1]<=cnt[mask2] && cnt[mask1]<=cnt[mask3])
            {
                for(int submask=mask1;submask>0;submask=((submask-1)&mask1))
                    ans+=(s[mask3|submask]-'0');
                ans+=(s[mask3]-'0');
            }
            else if(cnt[mask2]<=cnt[mask3] && cnt[mask2]<=cnt[mask1])
            {
                for(int submask=mask2;submask>0;submask=(mask2&(submask-1)))
                    ans+=(((cnt[submask]&1)?-1:1)*sup[submask|mask3]);
                ans+=sup[mask3];
            }
            else
            {
                for(int submask=mask3;submask>0;submask=(mask3&(submask-1)))
                    ans+=(((cnt[submask]&1)?-1:1)*sub[submask|mask1]);
                ans+=sub[mask1];
            }
            cout<<ans<<"\n";
        }
    }       
}   

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