Submission #820638

#TimeUsernameProblemLanguageResultExecution timeMemory
820638winter0101Snake Escaping (JOI18_snake_escaping)C++14
100 / 100
783 ms43360 KiB
#include<bits/stdc++.h> using namespace std; #define all(fl) fl.begin(),fl.end() #define pb push_back #define fi first #define se second #define for1(i,j,k) for(int i=j;i<=k;i++) #define for2(i,j,k) for(int i=j;i>=k;i--) #define for3(i,j,k,l) for(int i=j;i<=k;i+=l) #define lb lower_bound #define ub upper_bound #define sz(a) (int)a.size() #define pii pair<int,int> #define pli pair<long long,int> #define gcd __gcd #define lcm(x,y) x*y/__gcd(x,y) #define pil pair<int,long long> #define pll pair<long long,long long> #define eb emplace_back int a[1<<20]; int f[1<<20]; int g[1<<20]; signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); //freopen("temp.INP","r",stdin); //freopen("temp.OUT","w",stdout); int n,q; cin>>n>>q; string s; cin>>s; for1(i,0,(1<<n)-1){ a[i]=(s[i]-'0'); f[i]=g[i]=a[i]; } for1(j,0,n-1){ for1(i,0,(1<<n)-1){ if (i>>j&1)f[i]=(f[i]+f[i-(1<<j)]); } for2(i,(1<<n)-1,0){ if (!(i>>j&1))g[i]=(g[i]+g[i+(1<<j)]); } } for1(i,1,q){ string t; cin>>t; int bit0=0,bit1=0,bit=0,mask=0,mask1=0,mask0=0; reverse(all(t)); for1(j,0,n-1){ if (t[j]=='0'){ bit0++; mask0|=(1<<j); } if (t[j]=='1'){ bit1++; mask1|=(1<<j); } if (t[j]=='?'){ bit++; mask|=(1<<j); } } int ans=0; if (mask==0){ cout<<a[mask1]<<'\n'; continue; } //cout<<mask0<<" "<<mask1<<" "<<mask<<'\n'; //if (bit>20){ if (bit<=6){ for(int ss=mask;ss;ss=(ss-1)&mask){ ans+=(a[mask1|ss]); } ans+=a[mask1]; } else if (bit1==min({bit,bit0,bit1})){ //else if (bit1>20){ ans=(ans+f[mask1|mask]); int n1=__builtin_popcount(mask1); for(int ss=mask1;ss;ss=(ss-1)&mask1){ if (ss==mask1)continue; int num=__builtin_popcount(ss); int ck=((num-n1)%2+2)%2; if (ck==0)ans=(ans+f[ss|mask]); else ans=(ans-f[ss|mask]); //cout<<ss<<'\n'; } if (mask1!=0){ if (n1%2==1)ans=(ans-f[mask]); else ans=(ans+f[mask]); } } else if (bit0==min({bit,bit0,bit1})){ //else if (bit0<=6){ ans=(ans+g[mask1]); //cout<<g[0]<<'\n'; for(int ss=mask0;ss;ss=(ss-1)&mask0){ int num=__builtin_popcount(ss); if (num%2==0)ans=(ans+g[ss|mask1]); else ans=(ans-g[ss|mask1]); } } cout<<ans<<'\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...