Submission #699110

#TimeUsernameProblemLanguageResultExecution timeMemory
699110Jarif_RahmanSnake Escaping (JOI18_snake_escaping)C++17
100 / 100
911 ms42184 KiB
#include <bits/stdc++.h> #define pb push_back #define f first #define sc second using namespace std; typedef long long int ll; typedef string str; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); int L, Q; cin >> L >> Q; int* v = new int[1<<L]; for(int i = 0; i < (1<<L); i++){ char c; cin >> c; v[i] = c-'0'; } int *dp1 = new int[1<<L], *dp2 = new int[1<<L]; fill(dp1, dp1+(1<<L), 0); fill(dp2, dp2+(1<<L), 0); for(int i = 0; i < (1<<L); i++){ dp1[i]+=v[i]; dp2[((1<<L)-1)^i]+=v[i]; } for(int j = 0; j < L; j++) for(int i = 0; i < (1<<L); i++) if(i&(1<<j)){ dp1[i]+=dp1[i^(1<<j)]; dp2[i]+=dp2[i^(1<<j)]; } int L_3 = L/3; while(Q--){ str s; cin >> s; int z = 0, o = 0, u = 0; reverse(s.begin(), s.end()); for(int i = 0; i < L; i++){ if(s[i] == '0') z+=(1<<i); if(s[i] == '1') o+=(1<<i); if(s[i] == '?') u+=(1<<i); } int ans = 0; if(__builtin_popcount(u) <= L_3){ ans+=v[o]; for(int i = u; i > 0; i = (i-1)&u) ans+=v[i|o]; } else if(__builtin_popcount(o) <= L_3){ ans+=dp1[u]*(__builtin_popcount(o)&1?-1:1); for(int i = o; i > 0; i = (i-1)&o) ans+=dp1[i|u]*((__builtin_popcount(o)-__builtin_popcount(i))&1?-1:1); } else{ ans+=dp2[u]*(__builtin_popcount(z)&1?-1:1); for(int i = z; i > 0; i = (i-1)&z) ans+=dp2[i|u]*((__builtin_popcount(z)-__builtin_popcount(i))&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...