# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
257481 | mhy908 | Snake Escaping (JOI18_snake_escaping) | C++14 | 1 ms | 384 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
typedef long long LL;
int len, n, q;
int arr[1050000], arrrv[1050000], dp[1050000], dprv[1050000];
char str[1050000], qu[30];
int q_query(){
int temp=0, x=0, ret=0;
for(int i=1; i<=len; i++){
temp*=2, x*=2;
if(qu[i]=='?')x++;
if(qu[i]=='1')temp++;
}
for(int i=x; ; i=x&(i-1)){
ret+=arr[temp^i];
if(!i)break;
}
return ret;
}
int o_query(){
int temp=0, x=0, ret=0;
for(int i=1; i<=len; i++){
temp*=2, x*=2;
if(qu[i]=='1')x++;
if(qu[i]=='?')temp++;
}
if(!x)return dp[temp];
ret=0;
for(int i=x; i; i=x&(i-1)){
int pc=__builtin_popcount(i);
if(pc%2)ret+=dp[temp^i]-dp[temp];
else ret-=dp[temp^i]-dp[temp];
}
return ret;
}
int z_query(){
int temp=0, x=0, ret=0;
for(int i=1; i<=len; i++){
temp*=2, x*=2;
if(qu[i]=='0')x++;
if(qu[i]=='?')temp++;
}
if(!x)return dprv[temp];
ret=0;
for(int i=x; i; i=x&(i-1)){
int pc=__builtin_popcount(i);
if(pc%2)ret+=dprv[temp^i]-dprv[temp];
else ret-=dprv[temp^i]-dprv[temp];
}
return ret;
}
int main(){
scanf("%d %d", &len, &q);
n=(1<<len);
scanf("%s", str);
for(int i=0; i<n; i++){
arr[i]=(int)(str[i]-'0');
arrrv[(~i)&(n-1)]=arr[i];
}
for(int i=0; i<n; i++)dp[i]=arr[i], dprv[i]=arrrv[i];
for(int i=0; i<len; i++){
for(int mask=0; mask<n; mask++){
if(mask&(1<<i))dp[mask]+=dp[mask^(1<<i)];
if(mask&(1<<i))dprv[mask]+=dprv[mask^(1<<i)];
}
}
for(int j=1; j<=q; j++){
memset(qu, 0, sizeof qu);
scanf("%s", qu+1);
int qn=0, zn=0, on=0;
for(int i=1; i<=len; i++){
if(qu[i]=='?')qn++;
if(qu[i]=='0')zn++;
if(qu[i]=='1')on++;
}
if(qn<=6)printf("%d\n", q_query());
else if(on<=6)printf("%d\n", o_query());
else printf("%d\n", z_query());
}
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |