Submission #964803

#TimeUsernameProblemLanguageResultExecution timeMemory
964803BaytoroSnake Escaping (JOI18_snake_escaping)C++17
58 / 100
2036 ms17408 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],dp2[N],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]=dp2[i]=a[i]; for(int i=0;i<n;i++){ for(int mask=0;mask<(1<<n);mask++){ if(mask&(1<<i)) dp[mask]+=dp[mask^(1<<i)]; else dp2[mask]+=dp2[mask^(1<<i)]; } } 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]; } cout<<ans<<endl; } 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(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^=(1<<tmp[j]); c++; } } if(c%2) ans-=dp[tmpsum]; else ans+=dp[tmpsum]; } cout<<ans<<endl; } else{ for(int i=0;i<n;i++){ if(st[i]=='1') sum+=(1<<i); if(st[i]=='0') tmp.pb(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^=(1<<tmp[j]); c++; } } if(c%2) ans-=dp2[tmpsum]; else ans+=dp2[tmpsum]; } cout<<ans<<endl; } } } signed main(){ ios; 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:57:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for(int j=0;j<tmp.size();j++){
      |                 ~^~~~~~~~~~~
snake_escaping.cpp:75:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |     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...