Submission #933926

#TimeUsernameProblemLanguageResultExecution timeMemory
933926ShaShiSnake Escaping (JOI18_snake_escaping)C++17
100 / 100
1739 ms63596 KiB
// #pragma GCC optimize("O3") #include <bits/stdc++.h> #define int long long #define F first #define S second #define pii pair<int, int> #define all(x) x.begin(), x.end() #define kill(x) cout << x << endl, exit(0); #define mp make_pair #define pb push_back #define endl "\n" using namespace std; typedef long long ll; typedef long double ld; const int MAXN = (int)(1<<21) + 7; const int MOD = 998244353; const int INF = (int)1e18 + 7; const int LG = 21; int n, m, t, flag, u, v, w, k, tmp, tmp2, tmp3, tmp4, tmp5, tmp6, ans, q, h; int arr[MAXN], sub[MAXN], sup[MAXN]; string s, s2; int Z, O, Q; int32_t main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> q; cin >> s; for (int i=0; i<(1<<n); i++) sub[i] = sup[i] = s[i]-'0'; for (int j=0; j<LG; j++) for (int i=0; i<MAXN; i++) if (i&(1<<j)) sub[i] += sub[i^(1<<j)]; for (int j=0; j<LG; j++) for (int i=MAXN-1; i>=0; i--) if (i&(1<<j)) sup[i^(1<<j)] += sup[i]; while (q--) { cin >> s2; reverse(all(s2)); Z = O = Q = 0; for (int i=0; i<n; i++) { if (s2[i] == '1') { O += (1<<i); } else if (s2[i] == '0') { Z += (1<<i); } else { Q += (1<<i); } } if (__builtin_popcount(Q) <= 10 ) { ans = s[O]-'0'; for (int mask=Q; mask!=0; mask=Q&(mask-1)) ans += s[mask+O]-'0'; } else if (__builtin_popcount(Z) <= 10) { ans = sup[O]; for (int mask=Z; mask!=0; mask=Z&(mask-1)) ans += sup[mask+O]*((__builtin_popcount(mask)%2) == 1? -1 : 1); } else { // ans = (s[Q]-'0')*(__builtin_popcount(O)%2 == 1? -1 : 1); // for (int mask=O; mask!=0; mask=O&(mask-1)) ans += sub[mask+Q]*(__builtin_popcount(O-mask)%2 == 1? -1 : 1); } cout << ans << endl; } 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...