Submission #964797

#TimeUsernameProblemLanguageResultExecution timeMemory
964797BaytoroSnake Escaping (JOI18_snake_escaping)C++17
65 / 100
2005 ms18664 KiB
#include <bits/stdc++.h> using namespace std; #define ios ios::sync_with_stdio(false); cin.tie(NULL); #define pb push_back #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define fr first #define sc second //#define mp make_pair #define ll long long //#define int ll //#define double long double const ll INF=1e18,N=(1<<20)+5; int dp[N][2],a[N]; void solve(){ int n,q;cin>>n>>q; string s;cin>>s; for(int i=0;i<(1<<n);i++) a[i]=(s[i]-'0'); for(int i=0;i<(1<<n);i++) dp[i][0]=dp[i][1]=a[i]; for(int i=0;i<n;i++){ for(int mask=0;mask<(1<<n);mask++){ if(mask&(1<<i)) dp[mask][0]+=dp[mask^(1<<i)][0]; else dp[mask][1]+=dp[mask^(1<<i)][1]; } } while(q--){ string st;cin>>st;reverse(all(st)); int z=0,o=0,u=0; for(int i=0;i<st.size();i++){ if(st[i]=='?') u++; else if(st[i]=='0') z++; else o++; } int sum=0,ans=0; vector<int> tmp; if(u<=6){ for(int i=0;i<n;i++){ if(st[i]=='1') sum+=(1<<i); if(st[i]=='?') tmp.pb(1<<i); } for(int i=0;i<(1<<tmp.size());i++){ int tmpsum=sum; for(int j=0;j<tmp.size();j++){ if(i&(1<<j)) tmpsum+=tmp[j]; } ans+=a[tmpsum]; } } else if(o<=6){ for(int i=0;i<n;i++){ if(st[i]=='1' || st[i]=='?') sum+=(1<<i); if(st[i]=='1') tmp.pb(1<<i); } for(int i=0;i<(1<<tmp.size());i++){ int tmpsum=sum,c=0; for(int j=0;j<tmp.size();j++){ if(i&(1<<j)){ tmpsum^=(tmp[j]); c++; } } if(c%2) ans-=dp[tmpsum][0]; else ans+=dp[tmpsum][0]; } } else{ for(int i=0;i<n;i++){ if(st[i]=='1') sum+=(1<<i); if(st[i]=='0') tmp.pb(1<<i); } for(int i=0;i<(1<<tmp.size());i++){ int tmpsum=sum,c=0; for(int j=0;j<tmp.size();j++){ if(!(i&(1<<j))){ tmpsum^=(tmp[j]); c++; } } if(c%2) ans-=dp[tmpsum][1]; else ans+=dp[tmpsum][1]; } } cout<<ans<<endl; } } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t=1;//cin>>t; while(t--) solve(); }

Compilation message (stderr)

snake_escaping.cpp: In function 'void solve()':
snake_escaping.cpp:29:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |   for(int i=0;i<st.size();i++){
      |               ~^~~~~~~~~~
snake_escaping.cpp:43:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for(int j=0;j<tmp.size();j++){
      |                 ~^~~~~~~~~~~
snake_escaping.cpp:56:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     for(int j=0;j<tmp.size();j++){
      |                 ~^~~~~~~~~~~
snake_escaping.cpp:73:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |     for(int j=0;j<tmp.size();j++){
      |                 ~^~~~~~~~~~~
#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...