Submission #853365

#TimeUsernameProblemLanguageResultExecution timeMemory
853365anhduc2701Snake Escaping (JOI18_snake_escaping)C++17
100 / 100
674 ms34256 KiB
#include<bits/stdc++.h> #define pb push_back #define fi first #define se second #define BIT(x,i) (((x)>>(i))&1) using namespace std; typedef long long ll; int dp[1<<20]; int dp1[1<<20]; int l,q; int sum=0; string a; signed main(){ // freopen("input.inp","r",stdin); // freopen("output.out","w",stdout); cin.tie(0),cout.tie(0)->sync_with_stdio(0); cin >> l >> q; cin >> a; for(int i=0;i<(1<<l);i++){ int num=a[i]-'0'; dp[i]=num; dp1[i]=num; } for(int i=0;i<l;i++){ for(int j=0;j<(1<<l);j++){ if((1<<i)&j)dp[j]+=dp[j^(1<<i)]; else dp1[j]+=dp1[j^(1<<i)]; } } for(int i=1;i<=q;i++){ string s; cin >> s; int mask0=0; int num0=0,num1=0,num2=0,mask1=0,mask2=0; int sum=0; for(int j=0;j<l;j++){ if(s[l-1-j]=='?'){ mask2^=(1<<j); num2++; } if(s[l-1-j]=='0'){ mask0^=(1<<j); num0++; } if(s[l-1-j]=='1'){ mask1^=(1<<j); num1++; } } if(num0<=min(num1,num2)){ for(int j=mask0;j>=0;j=(j-1)&mask0){ if(__builtin_popcount(j)%2==0){ sum+=dp1[mask1^j]; } else{ sum-=dp1[mask1^j]; } if(j==0)break; } } else if(num1<=min(num0,num2)){ for(int j=mask1;j>=0;j=(j-1)&mask1){ if((__builtin_popcount(j)&1)==(__builtin_popcount(mask1)&1)){ sum+=dp[j^mask2]; } else{ sum-=dp[j^mask2]; } if(j==0)break; } } else{ for(int j=mask2;j>=0;j=(j-1)&mask2){ sum+=a[j^mask1]-'0'; if(j==0)break; } } cout << sum << '\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...