Submission #210486

#TimeUsernameProblemLanguageResultExecution timeMemory
210486kshitij_sodaniSnake Escaping (JOI18_snake_escaping)C++17
0 / 100
714 ms45180 KiB
#include <iostream> #include <bits/stdc++.h> using namespace std; #define mp make_pair #define pb push_back typedef long long int llo; #define a first #define b second #define endl "\n" int aa=7; vector<int> aac[1000001]; vector<int> pre[130]; int sl3[21]; int sl[14]; int l; int dp[1600000]; int last[1600000]; int ans[1000000]; int it[1200000]; int num[1200000]; int ok; void find(int ind,int tot,int ind2){//pre_sub if(ind==aa){ pre[tot].pb(ind2); // cout<<tot<<" "<<ind2<<endl; } else{ if(aac[ind2][ind]%2==0){ find(ind+1,tot,ind2); } if(aac[ind2][ind]>0){ find(ind+1,tot+sl[aa-ind-1],ind2); } } } void find2(int ind,int ind2,int tot=0){// if(ind==l-aa){ last[tot]=ind2; // cout<<tot<<","<<ind2<<endl; return; } if(ind==ind2){ find2(ind+1,ind2,tot+2*sl3[(l-aa)-ind-1]); } else{ find2(ind+1,ind2,tot); find2(ind+1,ind2,tot+sl3[(l-aa)-ind-1]); } if(ind<ind2){ find2(ind+1,ind2,tot+2*sl3[(l-aa)-ind-1]); } } int find3(int ind){//dp if(dp[ind]>-1){ return dp[ind]; } if(last[ind]==-1){ dp[ind]=it[ind+ok*(sl[l-aa])]; return dp[ind]; } dp[ind]=find3(ind-sl3[l-aa-last[ind]-1])+find3(ind-2*sl3[l-aa-last[ind]-1]); return dp[ind]; } //void(int) int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); memset(last,-1,sizeof(last)); memset(num,0,sizeof(num)); sl[0]=1; for(int i=1;i<21;i++){ sl[i]=2*sl[i-1]; } sl3[0]=1; for(int i=1;i<14;i++){ sl3[i]=3*sl3[i-1]; } int q; cin>>l>>q; aa=min(7,l-1); int n=1<<l; char ss; for(int i=0;i<n;i++){ cin>>ss; it[i]=ss-'0'; } for(int ii=0;ii<q;ii++){ for(int i=0;i<l;i++){ cin>>ss; if(ss=='0'){ aac[ii].pb(0); if(l==1){ cout<<it[0]<<endl; } } else if(ss=='1'){ aac[ii].pb(1); if(l==1){ cout<<it[1]<<endl; } else{ if(i>=aa){ num[ii]+=sl3[l-i-1]; } } } else{ aac[ii].pb(2); if(l==1){ cout<<it[0]+it[1]<<endl; } else{ if(i>=aa){ num[ii]+=2*sl3[l-i-1]; } } } } } /*for(int i=0;i<q;i++){ cout<<num[i]<<" "; } cout<<endl;*/ if(l==1){ return 0; } for(int i=0;i<q;i++){ find(0,0,i); } memset(ans,0,sizeof(ans)); for(int i=0;i<l-aa;i++){ find2(0,i,0); } for(int i=0;i<130;i++){ if(pre[i].size()==0){ continue; } } for(int i=0;i<130;i++){ ok=i; if(pre[i].size()){ memset(dp,-1,sizeof(dp)); for(int j=0;j<1600000;j++){ find3(j); } for(auto j:pre[i]){ ans[j]+=dp[num[j]]; // cout<<i<<":"<<j<<":"<<dp[num[j]]<<endl; } } } for(int i=0;i<q;i++){ cout<<ans[i]<<endl; } return 0; }

Compilation message (stderr)

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:74:17: warning: iteration 14 invokes undefined behavior [-Waggressive-loop-optimizations]
   sl[i]=2*sl[i-1];
           ~~~~~~^
snake_escaping.cpp:73:15: note: within this loop
  for(int i=1;i<21;i++){
              ~^~~
#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...