Submission #1099068

#TimeUsernameProblemLanguageResultExecution timeMemory
1099068trieSnake Escaping (JOI18_snake_escaping)C++17
22 / 100
342 ms20052 KiB
#include<bits/stdc++.h> #define mp make_pair #define fi first #define se second #define ii pair<int, int> #define iii pair<ii, int> #define ll long long #define pb push_back #define pli pair<ll, int> #define all(v) (v).begin(), (v).end() #define uniquev(v) sort(all(v)), (v).resize(unique(all(v)) - (v).begin()) #define cntbit(mask) __builtin_popcount(mask) #define getbit(x, i) ((x >> i) & 1) #define MASK(i) (1 << i) #define pli pair<ll, int> using namespace std; template<class T1, class T2> bool maximize(T1 &a, T2 b){if(a < b){a = b; return 1;} return 0;} template<class T1, class T2> bool minimize(T1 &a, T2 b){if(a > b){a = b; return 1;} return 0;} const int N = 1e5 + 5; const int V = 1e6 + 5; const int MOD = 1e9 + 7; int n, q, cost[MASK(20) + 5], f[MASK(20) + 5]; string s; void solve() { cin >> n >> q; cin >> s; for(int i = 0 ; i < (1 << n) ; i++) f[i] = cost[i] = (s[i] - '0'); for(int i = 0 ; i < n ; i++) for(int mask = 0 ; mask < MASK(n) ; mask++) if (getbit(mask, i)) cost[mask] += cost[mask ^ MASK(i)]; for(int i = 0 ; i < n ; i++) for(int mask = 0 ; mask < MASK(n) ; mask++) if (!getbit(mask, i)) f[mask] += f[mask | MASK(i)]; for(int i = 0 ; i < q ; i++) { string t; cin >> t; int mask1, mask2, mask3, sz = (int) t.size() - 1; ll ans; mask1 = mask2 = mask3 = ans = 0; for(int i = sz ; i >= 0 ; i--) if (t[i] == '1') mask1 |= MASK(sz - i); else if (t[i] == '?') mask2 |= MASK(sz - i); else mask3 |= MASK(sz - i); if (cntbit(mask1) <= 6) { int c = cntbit(mask1) & 1; for(int submask = mask1 ; submask >= 0 ; submask = (submask - 1) & mask1) { if ((cntbit(submask) & 1) == c) ans += cost[submask + mask2]; else ans -= cost[submask + mask2]; if (submask == 0) break; } } else if (cntbit(mask2) <= 6) { for(int submask = mask2 ; submask >= 0 ; submask = (submask - 1) & mask2) { ans += (s[submask + mask1] - '0'); if (submask == 0) break; } } else { int c = cntbit(mask3) & 1; for(int submask = mask3 ; submask >= 0 ; submask = (submask - 1) & mask3) { if ((cntbit(submask) & 1) == c) ans -= f[submask + mask1]; else ans += f[submask + mask1]; if (submask == 0) break; } } cout << ans << '\n'; } } int main(void) { //freopen("task.inp", "r", stdin); //freopen("task.out", "w", stdout); ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t = 1; while(t--) solve(); return 0; }

Compilation message (stderr)

snake_escaping.cpp: In function 'void solve()':
snake_escaping.cpp:41:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   41 |     for(int i = 0 ; i < n ; i++)
      |     ^~~
snake_escaping.cpp:45:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   45 |  for(int i = 0 ; i < q ; i++) {
      |  ^~~
snake_escaping.cpp:52:38: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   52 |    if (t[i] == '1') mask1 |= MASK(sz - i);
      |                                   ~~~^~~
snake_escaping.cpp:14:23: note: in definition of macro 'MASK'
   14 | #define MASK(i) (1 << i)
      |                       ^
snake_escaping.cpp:53:43: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   53 |    else if (t[i] == '?') mask2 |= MASK(sz - i);
      |                                        ~~~^~~
snake_escaping.cpp:14:23: note: in definition of macro 'MASK'
   14 | #define MASK(i) (1 << i)
      |                       ^
snake_escaping.cpp:54:35: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   54 |             else mask3 |= MASK(sz - i);
      |                                ~~~^~~
snake_escaping.cpp:14:23: note: in definition of macro 'MASK'
   14 | #define MASK(i) (1 << i)
      |                       ^
#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...