# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
331805 | 2020-11-30T08:10:55 Z | daniel920712 | Snake Escaping (JOI18_snake_escaping) | C++14 | 2 ms | 492 KB |
#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; vector < int > xxx; 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,con=0,xx; 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++; } xxx.clear(); con=0; if(b<=a&&b<=c) { for(i=0;i<N;i++) { if(tt[i]=='1') xxx.push_back(i); else if(tt[i]=='?') con+=(1<<(N-i-1)); } BFS.push(make_pair(make_pair(0,con),0)); while(!BFS.empty()) { x=BFS.front().first.first; y=BFS.front().first.second; z=BFS.front().second; BFS.pop(); if(x==b) { if(z==0) ans+=con1[N%2][y]; else ans-=con1[N%2][y]; continue; } xx=xxx[x]; BFS.push(make_pair(make_pair(x+1,y+(1<<(N-xx-1))),z)); BFS.push(make_pair(make_pair(x+1,y),z^1)); } } else if(a<=b&&a<=c) { for(i=0;i<N;i++) { if(tt[i]=='?') xxx.push_back(i); else if(tt[i]=='1') con+=(1<<(N-i-1)); } BFS.push(make_pair(make_pair(0,con),0)); while(!BFS.empty()) { x=BFS.front().first.first; y=BFS.front().first.second; z=BFS.front().second; BFS.pop(); if(x==a) { ans+=(all[y]-'0'); continue; } xx=xxx[x]; BFS.push(make_pair(make_pair(x+1,y+(1<<(N-xx-1))),z)); BFS.push(make_pair(make_pair(x+1,y),z)); } } else if(c<=b&&c<=a) { for(i=0;i<N;i++) { if(tt[i]=='0') xxx.push_back(i); else if(tt[i]=='1') con+=(1<<(N-i-1)); } BFS.push(make_pair(make_pair(0,con),0)); while(!BFS.empty()) { x=BFS.front().first.first; y=BFS.front().first.second; z=BFS.front().second; BFS.pop(); if(x==c) { if(z==0) ans+=con2[N%2][y]; else ans-=con2[N%2][y]; continue; } xx=tt[x]; BFS.push(make_pair(make_pair(x+1,y+(1<<(N-xx-1))),z^1)); BFS.push(make_pair(make_pair(x+1,y),z)); } } printf("%d\n",ans); } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | Output is correct |
2 | Correct | 1 ms | 364 KB | Output is correct |
3 | Correct | 1 ms | 384 KB | Output is correct |
4 | Correct | 1 ms | 364 KB | Output is correct |
5 | Runtime error | 2 ms | 492 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
6 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | Output is correct |
2 | Correct | 1 ms | 364 KB | Output is correct |
3 | Correct | 1 ms | 384 KB | Output is correct |
4 | Correct | 1 ms | 364 KB | Output is correct |
5 | Runtime error | 2 ms | 492 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
6 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | Output is correct |
2 | Correct | 1 ms | 364 KB | Output is correct |
3 | Correct | 1 ms | 384 KB | Output is correct |
4 | Correct | 1 ms | 364 KB | Output is correct |
5 | Runtime error | 2 ms | 492 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
6 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | Output is correct |
2 | Correct | 1 ms | 364 KB | Output is correct |
3 | Correct | 1 ms | 384 KB | Output is correct |
4 | Correct | 1 ms | 364 KB | Output is correct |
5 | Runtime error | 2 ms | 492 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
6 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | Output is correct |
2 | Correct | 1 ms | 364 KB | Output is correct |
3 | Correct | 1 ms | 384 KB | Output is correct |
4 | Correct | 1 ms | 364 KB | Output is correct |
5 | Runtime error | 2 ms | 492 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
6 | Halted | 0 ms | 0 KB | - |