Submission #1052109

#TimeUsernameProblemLanguageResultExecution timeMemory
1052109vjudge1Snake Escaping (JOI18_snake_escaping)C++17
0 / 100
1 ms4440 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pi; typedef pair<long long,long long> pl; #define all(s) s.begin(),s.end() #define F first #define S second #define sz(a) a.size() const ll mod = 1e9+7; const ll INF = 1e18; const int inf = 1e9+200; const int N=1e5 + 10; int n,q; int a[11*N]; int sub[11*N],sup[11*N]; void solve() { cin>>n>>q; for(int i=0;i<(1<<n);++i) { char cc; cin>>cc; a[i]=(cc-'0'); } for(int i=0;i<(1<<n);++i) { sub[i]=a[i]; sup[i]=a[i]; } for(int i=0;i<n;++i) { for(int mask=0;mask<(1<<n);++mask) { if(mask & (1<<i)) { sub[mask] += sub[mask^(1<<i)]; } } } for(int i=0;i<n;++i) { for(int mask=(1<<n)-1;mask>=0;--mask) { if(mask & (1<<i)) { sup[mask] += sup[mask^(1<<i)]; } } } while(q--) { string s; cin>>s; int cnt[3]; fill(cnt,cnt+3,0); ll sum=0; vector<int> b; reverse(all(s)); vector<int> b1; vector<int> b2; for(int i=0;i<n;++i) { if(s[i]=='?') { cnt[2]++; b.push_back(i); } else if(s[i]=='1') { cnt[1]++; sum+=(1<<i); b1.push_back(i); } else { cnt[0]++; b2.push_back(i); } } if(cnt[2]<=6) { int ans = 0; for(int mask=0;mask<(1<<cnt[2]);++mask) { int t=0; for(int i=0;i<cnt[2];++i) { if((mask>>i)&1) { t+=(1<<(b[i])); } } ans+=a[sum + t]; } cout<<ans<<'\n'; } else if(cnt[1]<=6) { int ans = 0; for(int i=0;i<n;++i) { if(s[i]=='?'){ s[i]='1'; sum+=(1<<i); } } for(int mask=0;mask<(1<<cnt[1]);++mask) { int t=0; for(int i=0;i<cnt[1];++i) { if((mask>>i) & 1) { t+=(1<<(b1[i])); } } if((cnt[1]-__builtin_popcount(mask))&1==0) { ans+=sub[sum-t]; } else { ans-=sub[sum-t]; } } cout<<ans<<'\n'; } else if(cnt[0]<=6) { int ans = 0; for(int mask=0;mask<(1<<cnt[0]);++mask) { int t=0; for(int i=0;i<cnt[0];++i) { if((mask>>i) & 1) { t+=(1<<(b2[i])); } } if((__builtin_popcount(mask))&1==0) { ans+=sup[sum+t]; } else { ans-=sup[sum+t]; } } cout<<ans<<'\n'; } } } int main() { ios_base::sync_with_stdio(0) , cin.tie(0) , cout.tie(0); int T=1; //cin>>T; while(T--) { solve(); } return 0; }

Compilation message (stderr)

snake_escaping.cpp: In function 'void solve()':
snake_escaping.cpp:101:55: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
  101 |                 if((cnt[1]-__builtin_popcount(mask))&1==0) {
      |                                                      ~^~~
snake_escaping.cpp:119:48: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
  119 |                 if((__builtin_popcount(mask))&1==0) {
      |                                               ~^~~
#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...