Submission #1113367

#TimeUsernameProblemLanguageResultExecution timeMemory
1113367emad234Snake Escaping (JOI18_snake_escaping)C++17
0 / 100
1 ms504 KiB
#include "bits/stdc++.h" #define F first #define S second #define ll long long #define pii pair<ll,int> const int mxN = (1 << 20) + 5; const int mod = 1e9 + 7; using namespace std; int sos[mxN][2][2]; signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n,q; cin >>n>>q; string s; cin>>s; for(int i = 0;i < n;i++){ for(int mask = 0;mask < (1 << n);mask++){ if(!i){ sos[mask][0][0] = s[mask] - '0'; if((mask &1)) sos[mask][0][0] += s[mask - 1] - '0'; sos[mask][0][1] = s[mask] - '0'; if((mask &1) == 0) sos[mask][0][1] += s[mask + 1] - '0'; continue; } sos[mask][i &1][0] = sos[mask][(i - 1)&1][0]; sos[mask][i &1][1] = sos[mask][(i - 1)&1][1]; if(mask >> i & 1) sos[mask][(i)&1][0] += sos[mask - (1 << i)][(i - 1)&1][0]; else sos[mask][i &1][1] += sos[mask + (1 << i)][(i - 1)&1][1]; } } while(q--){ string a; cin >>a; reverse(a.begin(),a.end()); int Qcnt = 0, Ocnt = 0, Icnt = 0; for(auto x : a){ if(x == '?') Qcnt++; else if(x == '1') Icnt++; else Ocnt++; } int ans = 0; if(min({Qcnt,Ocnt,Icnt}) == Qcnt){ // printf("? small\n"); int m1 = 0,m2 = 0,m3 = 0; int i = 0; for(auto x : a){ if(x == '1') m1 += (1 << i); if(x == '?') m2 += (1 << i); i++; } m3 = m2; while(m3 > 0){ ans += s[m3 + m1] - '0'; m3 = (m3 - 1) & m2; } ans += s[m1] - '0'; }else if(min({Qcnt,Ocnt,Icnt}) == Icnt){ // printf("1 small\n"); int m1 = 0,m2 = 0,m3 = 0; int i = 0; for(auto x : a){ if(x == '?') m1 += (1 << i); if(x == '1') m2 += (1 << i); i++; } m3 = m2; while(m3 > 0){ if(((Icnt + Qcnt) &1) == (__builtin_popcount(m3 + m1) & 1)) ans += sos[m3 + m1][(n - 1) & 1][0]; else ans -= sos[m3 + m1][(n - 1) & 1][0]; m3 = (m3 - 1) & m2; } if(((Icnt + Qcnt) & 1) == (__builtin_popcount(m1) & 1)) ans += sos[m1][(n - 1) & 1][0]; else ans -= sos[m1][(n - 1) & 1][0]; }else{ // printf("0 small\n"); int m1 = 0,m2 = 0,m3 = 0; int i = 0; for(auto x : a){ if(x == '1') m1 += (1 << i); if(x == '0') m2 += (1 << i); i++; } m3 = m2; while(m3 > 0){ if((Qcnt & 1) == (__builtin_popcount(m3 + m1) &1)) ans += sos[m3 + m1][(n - 1) & 1][1]; else ans -= sos[m3 + m1][(n - 1) & 1][1]; m3 = (m3 - 1) & m2; } if((Qcnt & 1) == (__builtin_popcount(m1) &1)) ans += sos[m1][(n - 1) & 1][1]; else ans -= sos[m1][(n - 1) & 1][1]; } cout<<ans<<'\n'; } }
#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...