Submission #1190317

#TimeUsernameProblemLanguageResultExecution timeMemory
1190317AlgorithmWarriorSnake Escaping (JOI18_snake_escaping)C++20
22 / 100
1296 ms131072 KiB
#include <bits/stdc++.h> using namespace std; int const MAX=1050000; int const LOG=23; int n,q; int val[MAX]; char qry[MAX]; int dpsub[MAX][LOG],dpsupra[MAX][LOG]; void read(){ cin>>n>>q; int i; for(i=0;i<(1<<n);++i){ char ch; cin>>ch; val[i]=ch-'0'; dpsub[i][0]=ch-'0'; dpsupra[i][0]=ch-'0'; } } void precalc(){ int i,mask; for(i=1;i<=n;++i) for(mask=0;mask<(1<<n);++mask) if(mask&(1<<(i-1))) dpsub[mask][i]=dpsub[mask][i-1]+dpsub[mask^(1<<(i-1))][i-1]; else dpsub[mask][i]=dpsub[mask][i-1]; for(i=1;i<=n;++i) for(mask=0;mask<(1<<n);++mask) if(mask&(1<<(i-1))) dpsupra[mask][i]=dpsupra[mask][i-1]; else dpsupra[mask][i]=dpsupra[mask][i-1]+dpsupra[mask^(1<<(i-1))][i-1]; } int solve_brut(){ int nr=0,mask=0; int i; for(i=0;i<n;++i) if(qry[i]=='?') mask|=(1<<(n-i-1)); else nr|=(1<<(n-i-1))*(qry[i]-'0'); int submask=mask; int sum=0; do{ sum+=val[nr|submask]; submask=((submask-1)&mask); }while(submask!=mask); return sum; } int solve_pinex1(){ int nr=0,mask=0; int i; for(i=0;i<n;++i) if(qry[i]=='?') nr|=(1<<(n-i-1)); else mask|=(1<<(n-i-1))*(qry[i]-'0'); int sum=0; int submask=mask; int nrb=__builtin_popcount(mask); do{ int nrbs=__builtin_popcount(submask); int semn; if(nrb%2==nrbs%2) semn=1; else semn=-1; sum+=semn*dpsub[nr|submask][n]; submask=(submask-1)&mask; }while(submask!=mask); return sum; } int solve_pinex0(){ int nr=0,mask=0; int i; for(i=0;i<n;++i) if(qry[i]!='?'){ nr|=(1<<(n-i-1))*(qry[i]-'0'); mask|=(1<<(n-i-1))*('1'-qry[i]); } int sum=0; int submask=mask; do{ int nrbs=__builtin_popcount(submask); int semn; if(nrbs%2==0) semn=1; else semn=-1; sum+=semn*dpsupra[nr|submask][n]; submask=(submask-1)&mask; }while(submask!=mask); return sum; } void process_queries(){ int i,j; for(i=1;i<=q;++i){ int cnt=0,cnt0=0,cnt1=0; for(j=0;j<n;++j){ cin>>qry[j]; if(qry[j]=='?') ++cnt; if(qry[j]=='0') ++cnt0; if(qry[j]=='1') ++cnt1; } if(cnt<=6) cout<<solve_brut()<<'\n'; else if(cnt0<=6) cout<<solve_pinex0()<<'\n'; else cout<<solve_pinex1()<<'\n'; } } int main() { read(); precalc(); process_queries(); return 0; }
#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...