제출 #257481

#제출 시각아이디문제언어결과실행 시간메모리
257481mhy908Snake Escaping (JOI18_snake_escaping)C++14
0 / 100
1 ms384 KiB
#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()); } }

컴파일 시 표준 에러 (stderr) 메시지

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:60: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:62:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s", str);
     ~~~~~^~~~~~~~~~~
snake_escaping.cpp:76:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s", qu+1);
         ~~~~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...