oj.uz

Submission #651528

# Submission time Handle Problem Language Result Execution time Memory
651528 2022-10-19T08:19:56 Z ymm Snake Escaping (JOI18_snake_escaping) C++17
100 / 100
 1688 ms 46268 KB 
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int L = 20;
int sub[1<<L];
int sup[1<<L];
int poi[1<<L];
int sign[1<<L];
int q, l;

void sos()
{
	Loop (i,0,1<<l) {
		sign[i] = __builtin_popcount(i)&1? -1: 1;
		sub[i] = poi[i];
		sup[i] = poi[i];
	}
	for (int i = 1; i < (1<<l); i <<= 1) {
		Loop (j,0,1<<l) {
			if (j&i) {
				sub[j] += sub[j^i];
				sup[j^i] += sup[j];
			}
		}
	}
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> l >> q;
	Loop (i,0,1<<l) {
		char c;
		cin >> c;
		poi[i] = c-'0';
	}
	sos();
	while (q--) {
		int cnt[3]={}, msk[3]={};
		LoopR (i,0,l) {
			char c;
			cin >> c;
			c = c =='?'? 2: c-'0';
			cnt[c]++;
			msk[c] ^= (1<<i);
		}
		int ans = 0;
		if (cnt[2] <= cnt[0] && cnt[2] <= cnt[0]) {
			int x = msk[2];
			Loop (i,0,1<<cnt[2]) {
				ans += poi[msk[1] ^ x];
				x = (x-1) & msk[2];
			}
		} else if (cnt[1] <= cnt[0] && cnt[1] <= cnt[2]) {
			int x = msk[1];
			Loop (i,0,1<<cnt[1]) {
				ans += sub[msk[2] ^ x] * sign[msk[1] ^ x];
				x = (x-1) & msk[1];
			}
		} else {
			int x = msk[0];
			Loop (i,0,1<<cnt[0]) {
				ans += sup[msk[1] ^ x] * sign[x];
				x = (x-1) & msk[0];
			}
		}
		cout << ans << '\n';
	}
}

Compilation message

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:49:8: warning: array subscript has type 'char' [-Wchar-subscripts]
   49 |    cnt[c]++;
      |        ^
snake_escaping.cpp:50:8: warning: array subscript has type 'char' [-Wchar-subscripts]
   50 |    msk[c] ^= (1<<i);
      |        ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 284 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 284 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 269 ms 15028 KB Output is correct
12 Correct 286 ms 14760 KB Output is correct
13 Correct 302 ms 13996 KB Output is correct
14 Correct 269 ms 14100 KB Output is correct
15 Correct 295 ms 14988 KB Output is correct
16 Correct 298 ms 14260 KB Output is correct
17 Correct 295 ms 14156 KB Output is correct
18 Correct 277 ms 16172 KB Output is correct
19 Correct 252 ms 13132 KB Output is correct
20 Correct 263 ms 14948 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 284 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 269 ms 15028 KB Output is correct
12 Correct 286 ms 14760 KB Output is correct
13 Correct 302 ms 13996 KB Output is correct
14 Correct 269 ms 14100 KB Output is correct
15 Correct 295 ms 14988 KB Output is correct
16 Correct 298 ms 14260 KB Output is correct
17 Correct 295 ms 14156 KB Output is correct
18 Correct 277 ms 16172 KB Output is correct
19 Correct 252 ms 13132 KB Output is correct
20 Correct 263 ms 14948 KB Output is correct
21 Correct 327 ms 18160 KB Output is correct
22 Correct 366 ms 18224 KB Output is correct
23 Correct 350 ms 17340 KB Output is correct
24 Correct 334 ms 17100 KB Output is correct
25 Correct 354 ms 19080 KB Output is correct
26 Correct 344 ms 17648 KB Output is correct
27 Correct 350 ms 17524 KB Output is correct
28 Correct 334 ms 20068 KB Output is correct
29 Correct 315 ms 16076 KB Output is correct
30 Correct 313 ms 18308 KB Output is correct
31 Correct 367 ms 18124 KB Output is correct
32 Correct 361 ms 18128 KB Output is correct
33 Correct 335 ms 16944 KB Output is correct
34 Correct 327 ms 17128 KB Output is correct
35 Correct 352 ms 17564 KB Output is correct
36 Correct 333 ms 16120 KB Output is correct
37 Correct 414 ms 18140 KB Output is correct
38 Correct 320 ms 16028 KB Output is correct
39 Correct 331 ms 17336 KB Output is correct
40 Correct 318 ms 17052 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 284 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 96 ms 19008 KB Output is correct
12 Correct 89 ms 19008 KB Output is correct
13 Correct 72 ms 18872 KB Output is correct
14 Correct 78 ms 18936 KB Output is correct
15 Correct 73 ms 19056 KB Output is correct
16 Correct 88 ms 19080 KB Output is correct
17 Correct 95 ms 18960 KB Output is correct
18 Correct 68 ms 19060 KB Output is correct
19 Correct 67 ms 18752 KB Output is correct
20 Correct 68 ms 18940 KB Output is correct
21 Correct 78 ms 19000 KB Output is correct
22 Correct 80 ms 18892 KB Output is correct
23 Correct 65 ms 18912 KB Output is correct
24 Correct 72 ms 18892 KB Output is correct
25 Correct 89 ms 18968 KB Output is correct
26 Correct 70 ms 18872 KB Output is correct
27 Correct 131 ms 19020 KB Output is correct
28 Correct 76 ms 18752 KB Output is correct
29 Correct 72 ms 18876 KB Output is correct
30 Correct 69 ms 18896 KB Output is correct
31 Correct 74 ms 18868 KB Output is correct
32 Correct 80 ms 18908 KB Output is correct
33 Correct 89 ms 18924 KB Output is correct
34 Correct 67 ms 18880 KB Output is correct
35 Correct 86 ms 18860 KB Output is correct
36 Correct 78 ms 18908 KB Output is correct
37 Correct 80 ms 18980 KB Output is correct
38 Correct 86 ms 18876 KB Output is correct
39 Correct 94 ms 18880 KB Output is correct
40 Correct 82 ms 18876 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 284 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 269 ms 15028 KB Output is correct
12 Correct 286 ms 14760 KB Output is correct
13 Correct 302 ms 13996 KB Output is correct
14 Correct 269 ms 14100 KB Output is correct
15 Correct 295 ms 14988 KB Output is correct
16 Correct 298 ms 14260 KB Output is correct
17 Correct 295 ms 14156 KB Output is correct
18 Correct 277 ms 16172 KB Output is correct
19 Correct 252 ms 13132 KB Output is correct
20 Correct 263 ms 14948 KB Output is correct
21 Correct 327 ms 18160 KB Output is correct
22 Correct 366 ms 18224 KB Output is correct
23 Correct 350 ms 17340 KB Output is correct
24 Correct 334 ms 17100 KB Output is correct
25 Correct 354 ms 19080 KB Output is correct
26 Correct 344 ms 17648 KB Output is correct
27 Correct 350 ms 17524 KB Output is correct
28 Correct 334 ms 20068 KB Output is correct
29 Correct 315 ms 16076 KB Output is correct
30 Correct 313 ms 18308 KB Output is correct
31 Correct 367 ms 18124 KB Output is correct
32 Correct 361 ms 18128 KB Output is correct
33 Correct 335 ms 16944 KB Output is correct
34 Correct 327 ms 17128 KB Output is correct
35 Correct 352 ms 17564 KB Output is correct
36 Correct 333 ms 16120 KB Output is correct
37 Correct 414 ms 18140 KB Output is correct
38 Correct 320 ms 16028 KB Output is correct
39 Correct 331 ms 17336 KB Output is correct
40 Correct 318 ms 17052 KB Output is correct
41 Correct 96 ms 19008 KB Output is correct
42 Correct 89 ms 19008 KB Output is correct
43 Correct 72 ms 18872 KB Output is correct
44 Correct 78 ms 18936 KB Output is correct
45 Correct 73 ms 19056 KB Output is correct
46 Correct 88 ms 19080 KB Output is correct
47 Correct 95 ms 18960 KB Output is correct
48 Correct 68 ms 19060 KB Output is correct
49 Correct 67 ms 18752 KB Output is correct
50 Correct 68 ms 18940 KB Output is correct
51 Correct 78 ms 19000 KB Output is correct
52 Correct 80 ms 18892 KB Output is correct
53 Correct 65 ms 18912 KB Output is correct
54 Correct 72 ms 18892 KB Output is correct
55 Correct 89 ms 18968 KB Output is correct
56 Correct 70 ms 18872 KB Output is correct
57 Correct 131 ms 19020 KB Output is correct
58 Correct 76 ms 18752 KB Output is correct
59 Correct 72 ms 18876 KB Output is correct
60 Correct 69 ms 18896 KB Output is correct
61 Correct 74 ms 18868 KB Output is correct
62 Correct 80 ms 18908 KB Output is correct
63 Correct 89 ms 18924 KB Output is correct
64 Correct 67 ms 18880 KB Output is correct
65 Correct 86 ms 18860 KB Output is correct
66 Correct 78 ms 18908 KB Output is correct
67 Correct 80 ms 18980 KB Output is correct
68 Correct 86 ms 18876 KB Output is correct
69 Correct 94 ms 18880 KB Output is correct
70 Correct 82 ms 18876 KB Output is correct
71 Correct 519 ms 43296 KB Output is correct
72 Correct 990 ms 43396 KB Output is correct
73 Correct 609 ms 41904 KB Output is correct
74 Correct 746 ms 42236 KB Output is correct
75 Correct 590 ms 44204 KB Output is correct
76 Correct 931 ms 42532 KB Output is correct
77 Correct 850 ms 42568 KB Output is correct
78 Correct 483 ms 46268 KB Output is correct
79 Correct 498 ms 40460 KB Output is correct
80 Correct 539 ms 43356 KB Output is correct
81 Correct 639 ms 43224 KB Output is correct
82 Correct 721 ms 42288 KB Output is correct
83 Correct 555 ms 41496 KB Output is correct
84 Correct 757 ms 42184 KB Output is correct
85 Correct 858 ms 42468 KB Output is correct
86 Correct 459 ms 40268 KB Output is correct
87 Correct 1688 ms 43240 KB Output is correct
88 Correct 525 ms 40192 KB Output is correct
89 Correct 622 ms 41820 KB Output is correct
90 Correct 708 ms 42272 KB Output is correct
91 Correct 532 ms 41392 KB Output is correct
92 Correct 837 ms 42536 KB Output is correct
93 Correct 779 ms 42456 KB Output is correct
94 Correct 478 ms 40192 KB Output is correct
95 Correct 761 ms 42292 KB Output is correct
96 Correct 765 ms 42308 KB Output is correct
97 Correct 752 ms 42264 KB Output is correct
98 Correct 744 ms 42248 KB Output is correct
99 Correct 719 ms 42260 KB Output is correct
100 Correct 759 ms 42256 KB Output is correct