Submission #1113339

#TimeUsernameProblemLanguageResultExecution timeMemory
1113339vjudge1Snake Escaping (JOI18_snake_escaping)C++17
0 / 100
2059 ms15436 KiB
// Problem: B - Snake Escaping // Contest: Virtual Judge - Variety // URL: https://vjudge.net/contest/671976#problem/B // Memory Limit: 64 MB // Time Limit: 2000 ms // // By Muaath Alqarni // Blog: https://muaath5.githib.io/blog // // Powered by CP Editor (https://cpeditor.org) #include <bits/stdc++.h> #define ll long long #define pii pair<int, int> using namespace std; const int N = 20, SPLIT = 20; int n, q, mask[1<<N]; string vals; int dp[2][1<<N][N]; int sos[2][1<<N]; int main() { ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin >> n >> q >> vals; for (int i = 0; i < (1<<n); i++) mask[i] = vals[i] - '0'; for (int msk = 0; msk < (1<<n); msk++) { dp[0][msk][0] = mask[msk]; dp[1][msk][0] = mask[msk]; for (int i = 1; i <= n; i++) { dp[0][msk][i] += dp[0][msk][i-1]; dp[1][msk][i] += dp[1][msk][i-1]; if (msk & (1 << (i-1))) dp[0][msk][i] += dp[0][msk ^ (1 << (i-1))][i-1]; else dp[1][msk][i] += dp[1][msk ^ (1 << (i-1))][i-1]; } sos[0][msk] = dp[0][msk][n]; sos[1][msk] = dp[1][msk][n]; } while (q--) { string b; cin >> b; int c_marks=0, c_0=0, c_1=0; for (char c : b) if (c == '?') c_marks++; else if (c == '1') c_1++; else c_0++; if (c_marks <= SPLIT) { int init = 0; for (int i = 0; i < n; i++) if (b[i] == '1') init |= (1 << (n-i-1)); // bruteforce int ans = 0; for (int msk = 0; msk < (1 << c_marks); msk++) { int final = init; int idx = 0; for (int i = 0; i < n; i++) if (b[i] == '?') { if (msk&(1<<idx)) final |= (1 << (n-i-1)); idx++; } ans += mask[final]; cerr << bitset<N>(msk) << endl; } cerr <<endl; cout << ans << '\n'; continue; } } }
#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...