# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
42156 | 2018-02-23T05:14:56 Z | fest | Snake Escaping (JOI18_snake_escaping) | C++14 | 2000 ms | 65536 KB |
// fest #include <bits/stdc++.h> #define pb push_back #define F first #define S second #define y1 dasdasfasfas #define x1 wqdadfasfasfas #define All(c) c.begin(), c.end() #define SZ(A) (int((A).size())) #define umap unordered_map #define FILENAME "" #define __ fflush(stdout) typedef long long ll; typedef long double ld; using namespace std; void FREOPEN() { #ifdef COMP freopen(".in", "r", stdin); freopen("1.out", "w", stdout); #else freopen(FILENAME".in", "r", stdin); freopen(FILENAME".out", "w", stdout); #endif } inline double Time() {return (clock() * 1.0) / CLOCKS_PER_SEC; } const int N = 20, inf = 1e9 * 2, MOD = (int)1e9 + 7; char CH[N]; const ll INF = 1e18; const int dx[] = {1, -1, 0, 0, -1, 1, -1, 1}; const int dy[] = {0, 0, 1, -1, -1, 1, 1, -1}; int built[1 << N], ones[21], dp[2][2][1 << N], cost[2][1 << N], qs[21]; int n; inline int rev(int x) { int ret = 0; for (int i = 0; i < n; i++) { if (x & (1 << i)) continue; ret |= (1 << i); } return ret; } void build(int ty) { for (int mask = 0; mask < (1 << n); mask++) { dp[ty][0][mask] += cost[ty][mask]; if (mask & 1) dp[ty][0][mask] += cost[ty][mask ^ 1]; } for (int bit = 1; bit < n; bit++) { int j = bit % 2; for (int mask = 0; mask < (1 << n); mask++) { dp[ty][j][mask] = dp[ty][j ^ 1][mask]; if (mask & (1 << bit)) dp[ty][j][mask] += dp[ty][j ^ 1][mask ^ (1 << bit)]; } } } inline int calc(int ty, int cnt) { int ret = 0; int alw = 0; int r = 0; for (int i = 0; i < n; i++) { if (qs[i] == 2) alw |= (1 << i); if (qs[i] == 1) ones[r++] = i; } for (int mask = 0; mask < (1 << cnt); mask++) { int now = alw; for (int i = 0; i < r; i++) { if (mask & (1 << i)) now |= (1 << ones[i]); } if (built[mask] % 2) ret -= dp[ty][(n - 1) % 2][now]; else ret += dp[ty][(n - 1) % 2][now]; } return abs(ret); } int main() { int q; cin >> n >> q; scanf("\n"); for (int i = 0; i < (1 << n); i++) { char x; scanf("%c", &x); cost[0][i] = (int)(x - '0'); cost[1][rev(i)] = (int)(x - '0'); } for (int mask = 0; mask < (1 << n); mask++) built[mask] = __builtin_popcount(mask); build(0); build(1); while (q--) { scanf("\n"); int zer = 0, one = 0, que = 0; for (int i = n - 1; i >= 0; i--) { char x; scanf("%c", &x); if (x == '?') qs[i] = 2, que++; if (x == '1') qs[i] = 1, one++; if (x == '0') qs[i] = 0, zer++; } if (!one) { int ret = 0; for (int i = 0; i < n; i++) { if (qs[i] == 2) ret |= (1 << i); } printf("%d\n", dp[0][(n - 1) % 2][ret]); continue; } if (!zer) { int ret = 0; for (int i = 0; i < n; i++) { if (qs[i] == 2) ret |= (1 << i); } printf("%d\n", dp[1][(n - 1) % 2][ret]); continue; } if (que < 8) { int ans = 0; int r = 0; int alw = 0; for (int i = 0; i < n; i++) { if (qs[i] == 2) ones[r++] = i; if (qs[i] == 1) alw |= (1 << i); } for (int mask = 0; mask < (1 << que); mask++) { int ret = alw; for (int i = 0; i < r; i++) { if (mask & (1 << i)) ret |= (1 << ones[i]); } ans += cost[0][ret]; } printf("%d\n", ans); continue; } if (one < 8) { printf("%d\n", calc(0, one)); continue; } for (int i = 0; i < n; i++) if (qs[i] < 2) qs[i] ^= 1; printf("%d\n", calc(1, zer)); } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 3 ms | 556 KB | Output is correct |
3 | Correct | 2 ms | 640 KB | Output is correct |
4 | Correct | 3 ms | 640 KB | Output is correct |
5 | Correct | 3 ms | 640 KB | Output is correct |
6 | Correct | 3 ms | 640 KB | Output is correct |
7 | Correct | 2 ms | 640 KB | Output is correct |
8 | Correct | 2 ms | 640 KB | Output is correct |
9 | Correct | 4 ms | 640 KB | Output is correct |
10 | Correct | 2 ms | 640 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 3 ms | 556 KB | Output is correct |
3 | Correct | 2 ms | 640 KB | Output is correct |
4 | Correct | 3 ms | 640 KB | Output is correct |
5 | Correct | 3 ms | 640 KB | Output is correct |
6 | Correct | 3 ms | 640 KB | Output is correct |
7 | Correct | 2 ms | 640 KB | Output is correct |
8 | Correct | 2 ms | 640 KB | Output is correct |
9 | Correct | 4 ms | 640 KB | Output is correct |
10 | Correct | 2 ms | 640 KB | Output is correct |
11 | Correct | 718 ms | 7524 KB | Output is correct |
12 | Correct | 750 ms | 18148 KB | Output is correct |
13 | Correct | 854 ms | 28000 KB | Output is correct |
14 | Correct | 847 ms | 37196 KB | Output is correct |
15 | Correct | 1280 ms | 38476 KB | Output is correct |
16 | Correct | 949 ms | 38476 KB | Output is correct |
17 | Correct | 1027 ms | 38476 KB | Output is correct |
18 | Correct | 621 ms | 39296 KB | Output is correct |
19 | Correct | 751 ms | 39296 KB | Output is correct |
20 | Correct | 761 ms | 39296 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 3 ms | 556 KB | Output is correct |
3 | Correct | 2 ms | 640 KB | Output is correct |
4 | Correct | 3 ms | 640 KB | Output is correct |
5 | Correct | 3 ms | 640 KB | Output is correct |
6 | Correct | 3 ms | 640 KB | Output is correct |
7 | Correct | 2 ms | 640 KB | Output is correct |
8 | Correct | 2 ms | 640 KB | Output is correct |
9 | Correct | 4 ms | 640 KB | Output is correct |
10 | Correct | 2 ms | 640 KB | Output is correct |
11 | Correct | 718 ms | 7524 KB | Output is correct |
12 | Correct | 750 ms | 18148 KB | Output is correct |
13 | Correct | 854 ms | 28000 KB | Output is correct |
14 | Correct | 847 ms | 37196 KB | Output is correct |
15 | Correct | 1280 ms | 38476 KB | Output is correct |
16 | Correct | 949 ms | 38476 KB | Output is correct |
17 | Correct | 1027 ms | 38476 KB | Output is correct |
18 | Correct | 621 ms | 39296 KB | Output is correct |
19 | Correct | 751 ms | 39296 KB | Output is correct |
20 | Correct | 761 ms | 39296 KB | Output is correct |
21 | Correct | 960 ms | 39384 KB | Output is correct |
22 | Correct | 932 ms | 53176 KB | Output is correct |
23 | Correct | 1138 ms | 65536 KB | Output is correct |
24 | Correct | 1109 ms | 65536 KB | Output is correct |
25 | Correct | 1094 ms | 65536 KB | Output is correct |
26 | Correct | 1296 ms | 65536 KB | Output is correct |
27 | Correct | 1328 ms | 65536 KB | Output is correct |
28 | Correct | 775 ms | 65536 KB | Output is correct |
29 | Correct | 930 ms | 65536 KB | Output is correct |
30 | Correct | 964 ms | 65536 KB | Output is correct |
31 | Correct | 1561 ms | 65536 KB | Output is correct |
32 | Correct | 1256 ms | 65536 KB | Output is correct |
33 | Correct | 985 ms | 65536 KB | Output is correct |
34 | Correct | 1084 ms | 65536 KB | Output is correct |
35 | Correct | 1294 ms | 65536 KB | Output is correct |
36 | Correct | 781 ms | 65536 KB | Output is correct |
37 | Correct | 938 ms | 65536 KB | Output is correct |
38 | Correct | 927 ms | 65536 KB | Output is correct |
39 | Correct | 1070 ms | 65536 KB | Output is correct |
40 | Correct | 1109 ms | 65536 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 3 ms | 556 KB | Output is correct |
3 | Correct | 2 ms | 640 KB | Output is correct |
4 | Correct | 3 ms | 640 KB | Output is correct |
5 | Correct | 3 ms | 640 KB | Output is correct |
6 | Correct | 3 ms | 640 KB | Output is correct |
7 | Correct | 2 ms | 640 KB | Output is correct |
8 | Correct | 2 ms | 640 KB | Output is correct |
9 | Correct | 4 ms | 640 KB | Output is correct |
10 | Correct | 2 ms | 640 KB | Output is correct |
11 | Correct | 299 ms | 65536 KB | Output is correct |
12 | Correct | 287 ms | 65536 KB | Output is correct |
13 | Correct | 314 ms | 65536 KB | Output is correct |
14 | Correct | 393 ms | 65536 KB | Output is correct |
15 | Correct | 305 ms | 65536 KB | Output is correct |
16 | Correct | 363 ms | 65536 KB | Output is correct |
17 | Correct | 378 ms | 65536 KB | Output is correct |
18 | Correct | 271 ms | 65536 KB | Output is correct |
19 | Correct | 292 ms | 65536 KB | Output is correct |
20 | Correct | 294 ms | 65536 KB | Output is correct |
21 | Correct | 319 ms | 65536 KB | Output is correct |
22 | Correct | 393 ms | 65536 KB | Output is correct |
23 | Correct | 302 ms | 65536 KB | Output is correct |
24 | Correct | 323 ms | 65536 KB | Output is correct |
25 | Correct | 353 ms | 65536 KB | Output is correct |
26 | Correct | 307 ms | 65536 KB | Output is correct |
27 | Correct | 286 ms | 65536 KB | Output is correct |
28 | Correct | 292 ms | 65536 KB | Output is correct |
29 | Correct | 318 ms | 65536 KB | Output is correct |
30 | Correct | 332 ms | 65536 KB | Output is correct |
31 | Correct | 291 ms | 65536 KB | Output is correct |
32 | Correct | 390 ms | 65536 KB | Output is correct |
33 | Correct | 371 ms | 65536 KB | Output is correct |
34 | Correct | 273 ms | 65536 KB | Output is correct |
35 | Correct | 332 ms | 65536 KB | Output is correct |
36 | Correct | 329 ms | 65536 KB | Output is correct |
37 | Correct | 330 ms | 65536 KB | Output is correct |
38 | Correct | 346 ms | 65536 KB | Output is correct |
39 | Correct | 334 ms | 65536 KB | Output is correct |
40 | Correct | 337 ms | 65536 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 3 ms | 556 KB | Output is correct |
3 | Correct | 2 ms | 640 KB | Output is correct |
4 | Correct | 3 ms | 640 KB | Output is correct |
5 | Correct | 3 ms | 640 KB | Output is correct |
6 | Correct | 3 ms | 640 KB | Output is correct |
7 | Correct | 2 ms | 640 KB | Output is correct |
8 | Correct | 2 ms | 640 KB | Output is correct |
9 | Correct | 4 ms | 640 KB | Output is correct |
10 | Correct | 2 ms | 640 KB | Output is correct |
11 | Correct | 718 ms | 7524 KB | Output is correct |
12 | Correct | 750 ms | 18148 KB | Output is correct |
13 | Correct | 854 ms | 28000 KB | Output is correct |
14 | Correct | 847 ms | 37196 KB | Output is correct |
15 | Correct | 1280 ms | 38476 KB | Output is correct |
16 | Correct | 949 ms | 38476 KB | Output is correct |
17 | Correct | 1027 ms | 38476 KB | Output is correct |
18 | Correct | 621 ms | 39296 KB | Output is correct |
19 | Correct | 751 ms | 39296 KB | Output is correct |
20 | Correct | 761 ms | 39296 KB | Output is correct |
21 | Correct | 960 ms | 39384 KB | Output is correct |
22 | Correct | 932 ms | 53176 KB | Output is correct |
23 | Correct | 1138 ms | 65536 KB | Output is correct |
24 | Correct | 1109 ms | 65536 KB | Output is correct |
25 | Correct | 1094 ms | 65536 KB | Output is correct |
26 | Correct | 1296 ms | 65536 KB | Output is correct |
27 | Correct | 1328 ms | 65536 KB | Output is correct |
28 | Correct | 775 ms | 65536 KB | Output is correct |
29 | Correct | 930 ms | 65536 KB | Output is correct |
30 | Correct | 964 ms | 65536 KB | Output is correct |
31 | Correct | 1561 ms | 65536 KB | Output is correct |
32 | Correct | 1256 ms | 65536 KB | Output is correct |
33 | Correct | 985 ms | 65536 KB | Output is correct |
34 | Correct | 1084 ms | 65536 KB | Output is correct |
35 | Correct | 1294 ms | 65536 KB | Output is correct |
36 | Correct | 781 ms | 65536 KB | Output is correct |
37 | Correct | 938 ms | 65536 KB | Output is correct |
38 | Correct | 927 ms | 65536 KB | Output is correct |
39 | Correct | 1070 ms | 65536 KB | Output is correct |
40 | Correct | 1109 ms | 65536 KB | Output is correct |
41 | Correct | 299 ms | 65536 KB | Output is correct |
42 | Correct | 287 ms | 65536 KB | Output is correct |
43 | Correct | 314 ms | 65536 KB | Output is correct |
44 | Correct | 393 ms | 65536 KB | Output is correct |
45 | Correct | 305 ms | 65536 KB | Output is correct |
46 | Correct | 363 ms | 65536 KB | Output is correct |
47 | Correct | 378 ms | 65536 KB | Output is correct |
48 | Correct | 271 ms | 65536 KB | Output is correct |
49 | Correct | 292 ms | 65536 KB | Output is correct |
50 | Correct | 294 ms | 65536 KB | Output is correct |
51 | Correct | 319 ms | 65536 KB | Output is correct |
52 | Correct | 393 ms | 65536 KB | Output is correct |
53 | Correct | 302 ms | 65536 KB | Output is correct |
54 | Correct | 323 ms | 65536 KB | Output is correct |
55 | Correct | 353 ms | 65536 KB | Output is correct |
56 | Correct | 307 ms | 65536 KB | Output is correct |
57 | Correct | 286 ms | 65536 KB | Output is correct |
58 | Correct | 292 ms | 65536 KB | Output is correct |
59 | Correct | 318 ms | 65536 KB | Output is correct |
60 | Correct | 332 ms | 65536 KB | Output is correct |
61 | Correct | 291 ms | 65536 KB | Output is correct |
62 | Correct | 390 ms | 65536 KB | Output is correct |
63 | Correct | 371 ms | 65536 KB | Output is correct |
64 | Correct | 273 ms | 65536 KB | Output is correct |
65 | Correct | 332 ms | 65536 KB | Output is correct |
66 | Correct | 329 ms | 65536 KB | Output is correct |
67 | Correct | 330 ms | 65536 KB | Output is correct |
68 | Correct | 346 ms | 65536 KB | Output is correct |
69 | Correct | 334 ms | 65536 KB | Output is correct |
70 | Correct | 337 ms | 65536 KB | Output is correct |
71 | Correct | 1669 ms | 65536 KB | Output is correct |
72 | Correct | 1682 ms | 65536 KB | Output is correct |
73 | Execution timed out | 2044 ms | 65536 KB | Time limit exceeded |
74 | Halted | 0 ms | 0 KB | - |