제출 #1202739

#제출 시각아이디문제언어결과실행 시간메모리
1202739tin_leSnake Escaping (JOI18_snake_escaping)C++20
0 / 100
1 ms328 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int bits, queries; cin >> bits >> queries; int size = 1 << bits; vector<int> base(size), sumSub(size), sumSup(size); string tox; cin >> tox; for (int mask = 0; mask < size; mask++) { base[mask] = tox[mask] - '0'; sumSub[mask] = base[mask]; sumSup[mask] = base[mask]; } for (int b = 0; b < bits; b++) { for (int mask = 0; mask < size; mask++) { if (mask & (1 << b)) { sumSub[mask] += sumSub[mask ^ (1 << b)]; } else { sumSup[mask] += sumSup[mask ^ (1 << b)]; } } } while (queries--) { string pattern; cin >> pattern; reverse(pattern.begin(), pattern.end()); int maskZero = 0; int maskOne = 0; int maskAny = 0; for (int i = 0; i < bits; i++) { char c = pattern[i]; if (c == '0') maskZero |= 1 << i; if (c == '1') maskOne |= 1 << i; if (c == '?') maskAny |= 1 << i; } int result = 0; int countAny = __builtin_popcount(maskAny); int countOne = __builtin_popcount(maskOne); int countZero= __builtin_popcount(maskZero); if (countAny <= 6) { result = base[maskOne]; for (int sub = maskAny; sub; sub = (sub - 1) & maskAny) { result += base[sub | maskOne]; } } else if (countOne <= 6) { result = 0; for (int sub = maskOne; ; sub = (sub - 1) & maskOne) { int parity = __builtin_parity(sub); result += (parity ? -1 : 1) * sumSub[sub | maskAny]; if (sub == 0) break; } } else { result = 0; for (int sub = maskZero; ; sub = (sub - 1) & maskZero) { int parity = __builtin_parity(sub); result += (parity ? -1 : 1) * sumSup[sub | maskOne]; if (sub == 0) break; } } cout << result << "\n"; } return 0; }
#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...