# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
257481 | 2020-08-04T10:42:38 Z | mhy908 | Snake Escaping (JOI18_snake_escaping) | C++14 | 1 ms | 384 KB |
#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
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 384 KB | Output is correct |
2 | Correct | 1 ms | 384 KB | Output is correct |
3 | Correct | 1 ms | 384 KB | Output is correct |
4 | Correct | 1 ms | 384 KB | Output is correct |
5 | Correct | 1 ms | 384 KB | Output is correct |
6 | Correct | 1 ms | 384 KB | Output is correct |
7 | Incorrect | 1 ms | 384 KB | Output isn't correct |
8 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 384 KB | Output is correct |
2 | Correct | 1 ms | 384 KB | Output is correct |
3 | Correct | 1 ms | 384 KB | Output is correct |
4 | Correct | 1 ms | 384 KB | Output is correct |
5 | Correct | 1 ms | 384 KB | Output is correct |
6 | Correct | 1 ms | 384 KB | Output is correct |
7 | Incorrect | 1 ms | 384 KB | Output isn't correct |
8 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 384 KB | Output is correct |
2 | Correct | 1 ms | 384 KB | Output is correct |
3 | Correct | 1 ms | 384 KB | Output is correct |
4 | Correct | 1 ms | 384 KB | Output is correct |
5 | Correct | 1 ms | 384 KB | Output is correct |
6 | Correct | 1 ms | 384 KB | Output is correct |
7 | Incorrect | 1 ms | 384 KB | Output isn't correct |
8 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 384 KB | Output is correct |
2 | Correct | 1 ms | 384 KB | Output is correct |
3 | Correct | 1 ms | 384 KB | Output is correct |
4 | Correct | 1 ms | 384 KB | Output is correct |
5 | Correct | 1 ms | 384 KB | Output is correct |
6 | Correct | 1 ms | 384 KB | Output is correct |
7 | Incorrect | 1 ms | 384 KB | Output isn't correct |
8 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 384 KB | Output is correct |
2 | Correct | 1 ms | 384 KB | Output is correct |
3 | Correct | 1 ms | 384 KB | Output is correct |
4 | Correct | 1 ms | 384 KB | Output is correct |
5 | Correct | 1 ms | 384 KB | Output is correct |
6 | Correct | 1 ms | 384 KB | Output is correct |
7 | Incorrect | 1 ms | 384 KB | Output isn't correct |
8 | Halted | 0 ms | 0 KB | - |