# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
64559 | 2018-08-04T23:02:55 Z | keko37 | Snake Escaping (JOI18_snake_escaping) | C++14 | 2000 ms | 33976 KB |
#include<iostream> using namespace std; const int MAXN = 21; int n, q; char l[MAXN]; int val[1<<MAXN], sum0[1<<MAXN], sum1[1<<MAXN]; void precompute () { for (int i=0; i<(1<<n); i++) { sum0[i] = val[i]; sum1[i] = val[i ^ ((1<<n) - 1)]; } for (int i=0; i<n; i++) { for (int j=0; j<(1<<n); j++) { if (j & (1<<i)) sum0[j] += sum0[j ^ (1<<i)]; if (j & (1<<i)) sum1[j] += sum1[j ^ (1<<i)]; } } } void ispis (int x) { for (int i=n-1; i>=0; i--) { cout << (bool) (x & (1<<i)); } cout << endl; } int main () { std::ios::sync_with_stdio(false); cin >> n >> q; for (int i=0; i<(1<<n); i++) { char c; cin >> c; val[i] = c - '0'; } precompute(); for (int tc=0; tc<q; tc++) { int a = 0, b = 0, c = 0; for (int i=0; i<n; i++) { cin >> l[i]; if (l[i] == '?') { a ^= (1<<(n-1-i)); } else if (l[i] == '0') { b ^= (1<<(n-1-i)); } else { c ^= (1<<(n-1-i)); } } int sol = 0, mask = 0; if (__builtin_popcount(a) <= n/3) { do { sol += val[mask | c]; } while (mask = (mask-a) & a); } else if (__builtin_popcount(b) <= n/3) { do { if (__builtin_popcount(mask | a) & 1) { sol -= sum1[mask | a]; } else { sol += sum1[mask | a]; } } while (mask = (mask-b) & b); if (sol < 0) sol = -sol; } else { do { if (__builtin_popcount(mask | a) & 1) { sol -= sum0[mask | a]; } else { sol += sum0[mask | a]; } } while (mask = (mask-c) & c); if (sol < 0) sol = -sol; } cout << sol << "\n"; } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 376 KB | Output is correct |
2 | Correct | 4 ms | 376 KB | Output is correct |
3 | Correct | 4 ms | 556 KB | Output is correct |
4 | Correct | 5 ms | 556 KB | Output is correct |
5 | Correct | 5 ms | 556 KB | Output is correct |
6 | Correct | 6 ms | 612 KB | Output is correct |
7 | Correct | 5 ms | 624 KB | Output is correct |
8 | Correct | 4 ms | 636 KB | Output is correct |
9 | Correct | 5 ms | 808 KB | Output is correct |
10 | Correct | 6 ms | 808 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 376 KB | Output is correct |
2 | Correct | 4 ms | 376 KB | Output is correct |
3 | Correct | 4 ms | 556 KB | Output is correct |
4 | Correct | 5 ms | 556 KB | Output is correct |
5 | Correct | 5 ms | 556 KB | Output is correct |
6 | Correct | 6 ms | 612 KB | Output is correct |
7 | Correct | 5 ms | 624 KB | Output is correct |
8 | Correct | 4 ms | 636 KB | Output is correct |
9 | Correct | 5 ms | 808 KB | Output is correct |
10 | Correct | 6 ms | 808 KB | Output is correct |
11 | Execution timed out | 2019 ms | 8952 KB | Time limit exceeded |
12 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 376 KB | Output is correct |
2 | Correct | 4 ms | 376 KB | Output is correct |
3 | Correct | 4 ms | 556 KB | Output is correct |
4 | Correct | 5 ms | 556 KB | Output is correct |
5 | Correct | 5 ms | 556 KB | Output is correct |
6 | Correct | 6 ms | 612 KB | Output is correct |
7 | Correct | 5 ms | 624 KB | Output is correct |
8 | Correct | 4 ms | 636 KB | Output is correct |
9 | Correct | 5 ms | 808 KB | Output is correct |
10 | Correct | 6 ms | 808 KB | Output is correct |
11 | Execution timed out | 2019 ms | 8952 KB | Time limit exceeded |
12 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 376 KB | Output is correct |
2 | Correct | 4 ms | 376 KB | Output is correct |
3 | Correct | 4 ms | 556 KB | Output is correct |
4 | Correct | 5 ms | 556 KB | Output is correct |
5 | Correct | 5 ms | 556 KB | Output is correct |
6 | Correct | 6 ms | 612 KB | Output is correct |
7 | Correct | 5 ms | 624 KB | Output is correct |
8 | Correct | 4 ms | 636 KB | Output is correct |
9 | Correct | 5 ms | 808 KB | Output is correct |
10 | Correct | 6 ms | 808 KB | Output is correct |
11 | Correct | 183 ms | 17460 KB | Output is correct |
12 | Correct | 209 ms | 17608 KB | Output is correct |
13 | Correct | 227 ms | 17608 KB | Output is correct |
14 | Correct | 280 ms | 17608 KB | Output is correct |
15 | Correct | 218 ms | 17652 KB | Output is correct |
16 | Correct | 284 ms | 17652 KB | Output is correct |
17 | Correct | 250 ms | 17652 KB | Output is correct |
18 | Correct | 224 ms | 17652 KB | Output is correct |
19 | Correct | 259 ms | 17652 KB | Output is correct |
20 | Correct | 238 ms | 17652 KB | Output is correct |
21 | Correct | 299 ms | 17652 KB | Output is correct |
22 | Correct | 282 ms | 17652 KB | Output is correct |
23 | Correct | 200 ms | 17652 KB | Output is correct |
24 | Correct | 253 ms | 17652 KB | Output is correct |
25 | Correct | 261 ms | 17652 KB | Output is correct |
26 | Correct | 176 ms | 17652 KB | Output is correct |
27 | Correct | 222 ms | 17652 KB | Output is correct |
28 | Correct | 213 ms | 17652 KB | Output is correct |
29 | Correct | 242 ms | 17652 KB | Output is correct |
30 | Correct | 247 ms | 17652 KB | Output is correct |
31 | Correct | 205 ms | 17652 KB | Output is correct |
32 | Correct | 276 ms | 17652 KB | Output is correct |
33 | Correct | 267 ms | 19632 KB | Output is correct |
34 | Correct | 215 ms | 21484 KB | Output is correct |
35 | Correct | 248 ms | 23640 KB | Output is correct |
36 | Correct | 244 ms | 25768 KB | Output is correct |
37 | Correct | 212 ms | 27804 KB | Output is correct |
38 | Correct | 223 ms | 29860 KB | Output is correct |
39 | Correct | 233 ms | 31880 KB | Output is correct |
40 | Correct | 202 ms | 33976 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 376 KB | Output is correct |
2 | Correct | 4 ms | 376 KB | Output is correct |
3 | Correct | 4 ms | 556 KB | Output is correct |
4 | Correct | 5 ms | 556 KB | Output is correct |
5 | Correct | 5 ms | 556 KB | Output is correct |
6 | Correct | 6 ms | 612 KB | Output is correct |
7 | Correct | 5 ms | 624 KB | Output is correct |
8 | Correct | 4 ms | 636 KB | Output is correct |
9 | Correct | 5 ms | 808 KB | Output is correct |
10 | Correct | 6 ms | 808 KB | Output is correct |
11 | Execution timed out | 2019 ms | 8952 KB | Time limit exceeded |
12 | Halted | 0 ms | 0 KB | - |