oj.uz

Submission #544292

# Submission time Handle Problem Language Result Execution time Memory
544292 2022-04-01T15:15:17 Z valerikk Snake Escaping (JOI18_snake_escaping) C++17
100 / 100
 1044 ms 22360 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int L = 21;
const int M = (1 << L) + 7;
const int K = 6;

int l, q;
int m;
char s[M];
int a[M];
int f[M];
int g[M];

int main() {
	cin >> l >> q >> s;

	m = (1 << l);
	for (int i = 0; i < m; ++i) {
		a[i] = s[i] - '0';
	}

	for (int i = 0; i < m; ++i) {
		f[i] = a[i];
		g[i] = a[i];
	}	
	for (int j = 0; j < l; ++j) {
		for (int i = 0; i < m; ++i) {
			if ((i >> j) & 1) {
				f[i] += f[i ^ (1 << j)];
				g[i ^ (1 << j)] += g[i];
			}
		}
	}

	while (q--) {
		/* int x;
		scanf("%d", &x); */
		static int t[3];
		memset(t, 0, sizeof(t));
		static char tt[L];
		scanf("%s", tt);
		
		for (int i = l - 1; i >= 0; --i) {
			/* t[x % 3] |= (1 << i);
			x /= 3; */
			t[tt[i] == '?' ? 2 : tt[i] - '0'] |= (1 << (l - i - 1)); 
		}

		if (__builtin_popcount(t[1]) <= K) {
			int ans = 0;
			int ppc = __builtin_popcount(t[1]);
			for (int z = t[1]; ; z = (z - 1) & t[1]) {
				ans += (((ppc ^ __builtin_popcount(z)) & 1) ? -1 : 1) * f[t[2] | z];
				if (z == 0) break;
			}
			printf("%d\n", ans);
		} else if (__builtin_popcount(t[0]) <= K) {
			int ans = 0;
			int ppc = __builtin_popcount(t[0]);
			for (int z = t[0]; ; z = (z - 1) & t[0]) {
				ans += (((ppc ^ __builtin_popcount(z)) & 1) ? -1 : 1) * g[t[1] ^ t[0] ^ z];
				if (z == 0) break;
			}
			printf("%d\n", ans);
		} else {
			assert(__builtin_popcount(t[2]) <= K);
			int ans = 0;
			for (int z = t[2]; ; z = (z - 1) & t[2]) {
				ans += a[t[1] | z];
				if (z == 0) break;
			}
			printf("%d\n", ans);
		}
	}
	return 0;
}

Compilation message

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:45:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |   scanf("%s", tt);
      |   ~~~~~^~~~~~~~~~

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 316 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 1 ms 312 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 316 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 316 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 1 ms 312 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 316 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 355 ms 5324 KB Output is correct
12 Correct 214 ms 4780 KB Output is correct
13 Correct 250 ms 4024 KB Output is correct
14 Correct 245 ms 4144 KB Output is correct
15 Correct 245 ms 5160 KB Output is correct
16 Correct 315 ms 4300 KB Output is correct
17 Correct 290 ms 4248 KB Output is correct
18 Correct 219 ms 6100 KB Output is correct
19 Correct 335 ms 3072 KB Output is correct
20 Correct 346 ms 4836 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 316 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 1 ms 312 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 316 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 355 ms 5324 KB Output is correct
12 Correct 214 ms 4780 KB Output is correct
13 Correct 250 ms 4024 KB Output is correct
14 Correct 245 ms 4144 KB Output is correct
15 Correct 245 ms 5160 KB Output is correct
16 Correct 315 ms 4300 KB Output is correct
17 Correct 290 ms 4248 KB Output is correct
18 Correct 219 ms 6100 KB Output is correct
19 Correct 335 ms 3072 KB Output is correct
20 Correct 346 ms 4836 KB Output is correct
21 Correct 511 ms 5220 KB Output is correct
22 Correct 247 ms 5368 KB Output is correct
23 Correct 330 ms 4460 KB Output is correct
24 Correct 326 ms 4624 KB Output is correct
25 Correct 264 ms 6592 KB Output is correct
26 Correct 370 ms 5456 KB Output is correct
27 Correct 345 ms 5104 KB Output is correct
28 Correct 246 ms 7616 KB Output is correct
29 Correct 517 ms 3820 KB Output is correct
30 Correct 347 ms 6544 KB Output is correct
31 Correct 316 ms 6376 KB Output is correct
32 Correct 330 ms 6420 KB Output is correct
33 Correct 273 ms 5288 KB Output is correct
34 Correct 354 ms 5392 KB Output is correct
35 Correct 346 ms 5896 KB Output is correct
36 Correct 243 ms 4428 KB Output is correct
37 Correct 260 ms 6664 KB Output is correct
38 Correct 424 ms 4564 KB Output is correct
39 Correct 493 ms 6132 KB Output is correct
40 Correct 380 ms 5820 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 316 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 1 ms 312 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 316 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 75 ms 15932 KB Output is correct
12 Correct 73 ms 15836 KB Output is correct
13 Correct 92 ms 15804 KB Output is correct
14 Correct 94 ms 15808 KB Output is correct
15 Correct 74 ms 15880 KB Output is correct
16 Correct 113 ms 15988 KB Output is correct
17 Correct 97 ms 15836 KB Output is correct
18 Correct 87 ms 16056 KB Output is correct
19 Correct 72 ms 15692 KB Output is correct
20 Correct 70 ms 15912 KB Output is correct
21 Correct 86 ms 15936 KB Output is correct
22 Correct 93 ms 15788 KB Output is correct
23 Correct 69 ms 15808 KB Output is correct
24 Correct 94 ms 15848 KB Output is correct
25 Correct 90 ms 15796 KB Output is correct
26 Correct 62 ms 15692 KB Output is correct
27 Correct 68 ms 15932 KB Output is correct
28 Correct 75 ms 15748 KB Output is correct
29 Correct 77 ms 15868 KB Output is correct
30 Correct 76 ms 15840 KB Output is correct
31 Correct 73 ms 15616 KB Output is correct
32 Correct 83 ms 15692 KB Output is correct
33 Correct 98 ms 15684 KB Output is correct
34 Correct 66 ms 15624 KB Output is correct
35 Correct 94 ms 15680 KB Output is correct
36 Correct 87 ms 15736 KB Output is correct
37 Correct 92 ms 15744 KB Output is correct
38 Correct 82 ms 15692 KB Output is correct
39 Correct 119 ms 15740 KB Output is correct
40 Correct 92 ms 15856 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 316 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 1 ms 312 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 316 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 355 ms 5324 KB Output is correct
12 Correct 214 ms 4780 KB Output is correct
13 Correct 250 ms 4024 KB Output is correct
14 Correct 245 ms 4144 KB Output is correct
15 Correct 245 ms 5160 KB Output is correct
16 Correct 315 ms 4300 KB Output is correct
17 Correct 290 ms 4248 KB Output is correct
18 Correct 219 ms 6100 KB Output is correct
19 Correct 335 ms 3072 KB Output is correct
20 Correct 346 ms 4836 KB Output is correct
21 Correct 511 ms 5220 KB Output is correct
22 Correct 247 ms 5368 KB Output is correct
23 Correct 330 ms 4460 KB Output is correct
24 Correct 326 ms 4624 KB Output is correct
25 Correct 264 ms 6592 KB Output is correct
26 Correct 370 ms 5456 KB Output is correct
27 Correct 345 ms 5104 KB Output is correct
28 Correct 246 ms 7616 KB Output is correct
29 Correct 517 ms 3820 KB Output is correct
30 Correct 347 ms 6544 KB Output is correct
31 Correct 316 ms 6376 KB Output is correct
32 Correct 330 ms 6420 KB Output is correct
33 Correct 273 ms 5288 KB Output is correct
34 Correct 354 ms 5392 KB Output is correct
35 Correct 346 ms 5896 KB Output is correct
36 Correct 243 ms 4428 KB Output is correct
37 Correct 260 ms 6664 KB Output is correct
38 Correct 424 ms 4564 KB Output is correct
39 Correct 493 ms 6132 KB Output is correct
40 Correct 380 ms 5820 KB Output is correct
41 Correct 75 ms 15932 KB Output is correct
42 Correct 73 ms 15836 KB Output is correct
43 Correct 92 ms 15804 KB Output is correct
44 Correct 94 ms 15808 KB Output is correct
45 Correct 74 ms 15880 KB Output is correct
46 Correct 113 ms 15988 KB Output is correct
47 Correct 97 ms 15836 KB Output is correct
48 Correct 87 ms 16056 KB Output is correct
49 Correct 72 ms 15692 KB Output is correct
50 Correct 70 ms 15912 KB Output is correct
51 Correct 86 ms 15936 KB Output is correct
52 Correct 93 ms 15788 KB Output is correct
53 Correct 69 ms 15808 KB Output is correct
54 Correct 94 ms 15848 KB Output is correct
55 Correct 90 ms 15796 KB Output is correct
56 Correct 62 ms 15692 KB Output is correct
57 Correct 68 ms 15932 KB Output is correct
58 Correct 75 ms 15748 KB Output is correct
59 Correct 77 ms 15868 KB Output is correct
60 Correct 76 ms 15840 KB Output is correct
61 Correct 73 ms 15616 KB Output is correct
62 Correct 83 ms 15692 KB Output is correct
63 Correct 98 ms 15684 KB Output is correct
64 Correct 66 ms 15624 KB Output is correct
65 Correct 94 ms 15680 KB Output is correct
66 Correct 87 ms 15736 KB Output is correct
67 Correct 92 ms 15744 KB Output is correct
68 Correct 82 ms 15692 KB Output is correct
69 Correct 119 ms 15740 KB Output is correct
70 Correct 92 ms 15856 KB Output is correct
71 Correct 431 ms 19268 KB Output is correct
72 Correct 462 ms 19564 KB Output is correct
73 Correct 664 ms 18020 KB Output is correct
74 Correct 788 ms 18476 KB Output is correct
75 Correct 467 ms 20348 KB Output is correct
76 Correct 1044 ms 18700 KB Output is correct
77 Correct 778 ms 18492 KB Output is correct
78 Correct 358 ms 22360 KB Output is correct
79 Correct 360 ms 16244 KB Output is correct
80 Correct 391 ms 19424 KB Output is correct
81 Correct 526 ms 19256 KB Output is correct
82 Correct 685 ms 18284 KB Output is correct
83 Correct 423 ms 17524 KB Output is correct
84 Correct 880 ms 18268 KB Output is correct
85 Correct 776 ms 18456 KB Output is correct
86 Correct 335 ms 16208 KB Output is correct
87 Correct 358 ms 19168 KB Output is correct
88 Correct 434 ms 16116 KB Output is correct
89 Correct 521 ms 17844 KB Output is correct
90 Correct 460 ms 18068 KB Output is correct
91 Correct 420 ms 17296 KB Output is correct
92 Correct 656 ms 18404 KB Output is correct
93 Correct 772 ms 18120 KB Output is correct
94 Correct 329 ms 15956 KB Output is correct
95 Correct 660 ms 17912 KB Output is correct
96 Correct 681 ms 17964 KB Output is correct
97 Correct 674 ms 17760 KB Output is correct
98 Correct 665 ms 17780 KB Output is correct
99 Correct 657 ms 17740 KB Output is correct
100 Correct 659 ms 17740 KB Output is correct