Submission #437224

#TimeUsernameProblemLanguageResultExecution timeMemory
437224cpp219Snake Escaping (JOI18_snake_escaping)C++14
100 / 100
1608 ms61496 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; #define fi first #define se second #define mp make_pair #define pb push_back #define fbo find_by_order #define ook order_of_key typedef long long ll; typedef pair<int,int> ii; typedef vector<int> vi; typedef long double ld; typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds; typedef set<int>::iterator sit; typedef map<int,int>::iterator mit; typedef vector<int>::iterator vit; ii queries[1000011]; char a[(1<<20)+12]; int ans[1000011]; const int N = 1594323; const int LG = 13; const int N2 = 2187; const int LG2 = 7; int dp[N+3]; int nxt[N+3][2]; bitset<(1<<LG2)+1> subbit[N2+3]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); for(int i=0;i<N;i++) { int cur=i; bool pos=0; int t=1; for(int j=LG-1;j>=0;j--) { if(cur%3==2) { nxt[i][1] = i - t; nxt[i][0] = i - t - t; pos=1; break; } cur/=3; t*=3; } if(!pos) { nxt[i][0]=nxt[i][1]=-1; } } for(int i=0;i<N2;i++) { int tmp[LG2+1]={}; int cur=i; for(int j=LG2-1;j>=0;j--) { tmp[j] = cur%3; cur/=3; } for(int j=0;j<(1<<LG2);j++) { bool pos=1; int cur2=j; for(int k=LG2-1;k>=0;k--) { int t=cur2&1; cur2>>=1; if(tmp[k]==2) continue; if(tmp[k]==t) continue; pos=0; break; } if(pos) subbit[i].set(j,1); } } int l,q; cin>>l>>q; cin>>a; for(int i=0;i<q;i++) { char x[21]; cin>>x; for(int j=0;j<min(l,LG2);j++) { queries[i].fi*=3; queries[i].fi+=(x[j]=='0'?0:(x[j]=='1'?1:2)); } for(int j=LG2;j<l;j++) { queries[i].se*=3; queries[i].se+=(x[j]=='0'?0:(x[j]=='1'?1:2)); } } int rhs = max(0, l - LG2); for(int i=0;i<(1<<min(l,LG2));i++) { for(int j=0;j<N;j++) { if(nxt[j][0]==-1) { int cur=j; int bit = 0; for(int k=0;k<rhs;k++) { if(cur%3) bit^=(1<<k); cur/=3; } dp[j] = a[(i<<rhs)^bit]-'0'; } else { dp[j] = dp[nxt[j][0]]+dp[nxt[j][1]]; } } for(int j=0;j<q;j++) { if(subbit[queries[j].fi][i]) { ans[j] += dp[queries[j].se]; } } } for(int i=0;i<q;i++) { cout<<ans[i]<<'\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...