이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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]=='?')temp++, 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')temp++, x++;
if(qu[i]=='?')temp++;
}
for(int i=x; ; i=x&(i-1)){
int pc=__builtin_popcount(i);
if(pc%2)ret-=dp[temp^i];
else ret+=dp[temp^i];
if(!i)break;
}
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')temp++, x++;
if(qu[i]=='?')temp++;
}
for(int i=x; ; i=x&(i-1)){
int pc=__builtin_popcount(i);
if(pc%2)ret-=dprv[temp^i];
else ret+=dprv[temp^i];
if(!i)break;
}
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<=len/3)printf("%d\n", q_query());
else if(on<=len/3)printf("%d\n", o_query());
else printf("%d\n", z_query());
}
}
컴파일 시 표준 에러 (stderr) 메시지
snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:58:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &len, &q);
~~~~~^~~~~~~~~~~~~~~~~~~
snake_escaping.cpp:60:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", str);
~~~~~^~~~~~~~~~~
snake_escaping.cpp:74:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", qu+1);
~~~~~^~~~~~~~~~~~
# | 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... |