Submission #331796

#TimeUsernameProblemLanguageResultExecution timeMemory
331796daniel920712Snake Escaping (JOI18_snake_escaping)C++14
0 / 100
1 ms364 KiB
#include <iostream> #include <stdio.h> #include <stdlib.h> #include <vector> #include <string.h> #include <map> #include <utility> #include <algorithm> #include <stack> #include <queue> using namespace std; char all[1148576]; char tt[25]; int con1[2][1100005]; int con2[2][1100005]; int ans=0; int N; queue < pair < pair < int , int > , int > > BFS; void F(int x,int y,int z) { if(x==N) { if(z%2==0) ans+=con1[N%2][y]; else ans-=con1[N%2][y]; return; } if(tt[x]=='1') { F(x+1,y+(1<<(N-x-1)),z); F(x+1,y,z+1); } else if(tt[x]=='0') F(x+1,y,z); else F(x+1,y+(1<<(N-x-1)),z); } void F2(int x,int y) { if(x==N) { ans+=(all[y]-'0'); return; } if(tt[x]=='?') { F2(x+1,y); F2(x+1,y+(1<<(N-x-1))); } else F2(x+1,y+(1<<(N-x-1))*(tt[x]-'0')); } void F3(int x,int y,int z) { if(x==N) { if(z%2==0) ans+=con2[N%2][y]; else ans-=con2[N%2][y]; return; } if(tt[x]=='0') { F3(x+1,y+(1<<(N-x-1)),z+1); F3(x+1,y,z); } else if(tt[x]=='1') F3(x+1,y+(1<<(N-x-1)),z); else F3(x+1,y,z); } int main() { //freopen("05-05.txt","rt",stdin); //freopen("tt.txt","w+t",stdout); int M,i,j,ok,a,b,c,x,y,z; scanf("%d %d",&N,&M); scanf("%s",all); for(i=0;i<(1<<N);i++) con2[0][i]=con1[0][i]=all[i]-'0'; for(i=0;i<N;i++) { for(j=0;j<(1<<N);j++) { con1[1-i%2][j]=con1[i%2][j]; con2[1-i%2][j]=con2[i%2][j]; if(j&(1<<i)) con1[1-i%2][j]+=con1[i%2][j-(1<<i)]; else con2[1-i%2][j]+=con2[i%2][j+(1<<i)]; } } while(M--) { scanf("%s",tt); ans=0; a=0; b=0; c=0; for(i=0;i<N;i++) { if(tt[i]=='?') a++; else if(tt[i]=='1') b++; else c++; } if(b<=a&&b<=c) { BFS.push(make_pair(make_pair(0,0),0)); while(!BFS.empty()) { x=BFS.front().first.first; y=BFS.front().first.second; z=BFS.front().second; BFS.pop(); if(x==N) { if(z==0) ans+=con1[N%2][y]; else ans-=con1[N%2][y]; continue; } if(tt[x]=='1') { BFS.push(make_pair(make_pair(x+1,y+(1<<(N-x-1))),z)); BFS.push(make_pair(make_pair(x+1,y),z^1)); } else if(tt[x]=='0') BFS.push(make_pair(make_pair(x+1,y),z^1)); else BFS.push(make_pair(make_pair(x+1,y+(1<<(N-x-1))),z)); } } else if(a<=b&&a<=c) F2(0,0); else if(c<=b&&c<=a) F3(0,0,0); printf("%d\n",ans); } return 0; }

Compilation message (stderr)

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:71:15: warning: unused variable 'ok' [-Wunused-variable]
   71 |     int M,i,j,ok,a,b,c,x,y,z;
      |               ^~
snake_escaping.cpp:72:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   72 |     scanf("%d %d",&N,&M);
      |     ~~~~~^~~~~~~~~~~~~~~
snake_escaping.cpp:73:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   73 |     scanf("%s",all);
      |     ~~~~~^~~~~~~~~~
snake_escaping.cpp:90:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   90 |         scanf("%s",tt);
      |         ~~~~~^~~~~~~~~
#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...