#include "bits/stdc++.h"
#define MAXN 100009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x) cerr<< #x <<" = "<< x<<endl;
#define BLOK 10
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
int n,q;
const int N=(1<<20)+5;
int dp[N*2],pw[22],ans[N];
char s[N],t[22];
vector<PII>adj[22],query[130];
void rec(int pos,int mask,int bit,int last){
if(pos==min(n,BLOK)){
adj[bit].pb(mp(mask,last));
return;
}
rec(pos+1,mask*3,bit,last);
rec(pos+1,mask*3+1,bit,last);
rec(pos+1,mask*3+2,bit+1,min(n,BLOK)-pos-1);
}
int two(int x){
int bit=0,res=0;
while(x>=1){
assert(x%3<2);
if(x%3)
res+=(1<<bit);
x/=3;bit++;
}
return res;
}
void f(int l,int r,int mask,int suf,int ind){
if(l==r){
query[mask].pb(mp(suf,ind));
return;
}
if(t[l]=='0')
f(l+1,r,mask*2,suf,ind);
if(t[l]=='1')
f(l+1,r,mask*2+1,suf,ind);
if(t[l]=='?'){
f(l+1,r,mask*2,suf,ind);
f(l+1,r,mask*2+1,suf,ind);
}
}
int main(){
//~ freopen("file.in", "r", stdin);
scanf("%d%d",&n,&q);
scanf("%s",s);
pw[0]=1;
for(int i=1;i<=BLOK;i++)
pw[i]=pw[i-1]*3;
if(n<=BLOK){
rec(0,0,0,-1);
tr(it,adj[0])
dp[it->ff]=s[two(it->ff)]-'0';
for(int j=1;j<=n;j++)
tr(it,adj[j])
dp[it->ff]=dp[it->ff-pw[it->ss]]+dp[it->ff-2*pw[it->ss]];
for(int i=1;i<=q;i++){
scanf("%s",t);
int base=0;
for(int j=0;j<n;j++){
base=base*3;
if(t[j]=='1')
base++;
if(t[j]=='?')
base+=2;
}
printf("%d\n",dp[base]);
}
}
else{
rec(0,0,0,-1);
for(int i=1;i<=q;i++){
scanf("%s",t);
int base=0;
for(int j=n-BLOK;j<n;j++){
base=base*3;
if(t[j]=='1')
base++;
if(t[j]=='?')
base+=2;
}
f(0,n-BLOK,0,base,i);
}
for(int mask=0;mask<(1<<(n-BLOK));mask++){
tr(it,adj[0])
dp[it->ff]=s[(1<<BLOK)*mask+two(it->ff)]-'0';
for(int i=1;i<=BLOK;i++)
tr(it,adj[i])
dp[it->ff]=dp[it->ff-pw[it->ss]]+dp[it->ff-2*pw[it->ss]];
tr(it,query[mask])
ans[it->ss]+=dp[it->ff];
}
for(int i=1;i<=q;i++)
printf("%d\n",ans[i]);
}
return 0;
}
Compilation message
snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:61:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&n,&q);
^
snake_escaping.cpp:62:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s",s);
^
snake_escaping.cpp:74:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s",t);
^
snake_escaping.cpp:89:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s",t);
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
1272 KB |
Output is correct |
2 |
Correct |
3 ms |
1272 KB |
Output is correct |
3 |
Correct |
3 ms |
1344 KB |
Output is correct |
4 |
Correct |
3 ms |
1388 KB |
Output is correct |
5 |
Correct |
3 ms |
1472 KB |
Output is correct |
6 |
Correct |
3 ms |
1628 KB |
Output is correct |
7 |
Correct |
3 ms |
1628 KB |
Output is correct |
8 |
Correct |
3 ms |
1628 KB |
Output is correct |
9 |
Correct |
3 ms |
1628 KB |
Output is correct |
10 |
Correct |
3 ms |
1628 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
1272 KB |
Output is correct |
2 |
Correct |
3 ms |
1272 KB |
Output is correct |
3 |
Correct |
3 ms |
1344 KB |
Output is correct |
4 |
Correct |
3 ms |
1388 KB |
Output is correct |
5 |
Correct |
3 ms |
1472 KB |
Output is correct |
6 |
Correct |
3 ms |
1628 KB |
Output is correct |
7 |
Correct |
3 ms |
1628 KB |
Output is correct |
8 |
Correct |
3 ms |
1628 KB |
Output is correct |
9 |
Correct |
3 ms |
1628 KB |
Output is correct |
10 |
Correct |
3 ms |
1628 KB |
Output is correct |
11 |
Correct |
255 ms |
16368 KB |
Output is correct |
12 |
Correct |
225 ms |
26656 KB |
Output is correct |
13 |
Correct |
267 ms |
36828 KB |
Output is correct |
14 |
Correct |
246 ms |
47796 KB |
Output is correct |
15 |
Correct |
250 ms |
59424 KB |
Output is correct |
16 |
Correct |
283 ms |
65536 KB |
Output is correct |
17 |
Correct |
264 ms |
65536 KB |
Output is correct |
18 |
Correct |
226 ms |
65536 KB |
Output is correct |
19 |
Correct |
257 ms |
65536 KB |
Output is correct |
20 |
Correct |
278 ms |
65536 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
1272 KB |
Output is correct |
2 |
Correct |
3 ms |
1272 KB |
Output is correct |
3 |
Correct |
3 ms |
1344 KB |
Output is correct |
4 |
Correct |
3 ms |
1388 KB |
Output is correct |
5 |
Correct |
3 ms |
1472 KB |
Output is correct |
6 |
Correct |
3 ms |
1628 KB |
Output is correct |
7 |
Correct |
3 ms |
1628 KB |
Output is correct |
8 |
Correct |
3 ms |
1628 KB |
Output is correct |
9 |
Correct |
3 ms |
1628 KB |
Output is correct |
10 |
Correct |
3 ms |
1628 KB |
Output is correct |
11 |
Correct |
255 ms |
16368 KB |
Output is correct |
12 |
Correct |
225 ms |
26656 KB |
Output is correct |
13 |
Correct |
267 ms |
36828 KB |
Output is correct |
14 |
Correct |
246 ms |
47796 KB |
Output is correct |
15 |
Correct |
250 ms |
59424 KB |
Output is correct |
16 |
Correct |
283 ms |
65536 KB |
Output is correct |
17 |
Correct |
264 ms |
65536 KB |
Output is correct |
18 |
Correct |
226 ms |
65536 KB |
Output is correct |
19 |
Correct |
257 ms |
65536 KB |
Output is correct |
20 |
Correct |
278 ms |
65536 KB |
Output is correct |
21 |
Runtime error |
438 ms |
65536 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
22 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
1272 KB |
Output is correct |
2 |
Correct |
3 ms |
1272 KB |
Output is correct |
3 |
Correct |
3 ms |
1344 KB |
Output is correct |
4 |
Correct |
3 ms |
1388 KB |
Output is correct |
5 |
Correct |
3 ms |
1472 KB |
Output is correct |
6 |
Correct |
3 ms |
1628 KB |
Output is correct |
7 |
Correct |
3 ms |
1628 KB |
Output is correct |
8 |
Correct |
3 ms |
1628 KB |
Output is correct |
9 |
Correct |
3 ms |
1628 KB |
Output is correct |
10 |
Correct |
3 ms |
1628 KB |
Output is correct |
11 |
Runtime error |
18 ms |
65536 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
12 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
1272 KB |
Output is correct |
2 |
Correct |
3 ms |
1272 KB |
Output is correct |
3 |
Correct |
3 ms |
1344 KB |
Output is correct |
4 |
Correct |
3 ms |
1388 KB |
Output is correct |
5 |
Correct |
3 ms |
1472 KB |
Output is correct |
6 |
Correct |
3 ms |
1628 KB |
Output is correct |
7 |
Correct |
3 ms |
1628 KB |
Output is correct |
8 |
Correct |
3 ms |
1628 KB |
Output is correct |
9 |
Correct |
3 ms |
1628 KB |
Output is correct |
10 |
Correct |
3 ms |
1628 KB |
Output is correct |
11 |
Correct |
255 ms |
16368 KB |
Output is correct |
12 |
Correct |
225 ms |
26656 KB |
Output is correct |
13 |
Correct |
267 ms |
36828 KB |
Output is correct |
14 |
Correct |
246 ms |
47796 KB |
Output is correct |
15 |
Correct |
250 ms |
59424 KB |
Output is correct |
16 |
Correct |
283 ms |
65536 KB |
Output is correct |
17 |
Correct |
264 ms |
65536 KB |
Output is correct |
18 |
Correct |
226 ms |
65536 KB |
Output is correct |
19 |
Correct |
257 ms |
65536 KB |
Output is correct |
20 |
Correct |
278 ms |
65536 KB |
Output is correct |
21 |
Runtime error |
438 ms |
65536 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
22 |
Halted |
0 ms |
0 KB |
- |