oj.uz

Submission #678625

# Submission time Handle Problem Language Result Execution time Memory
678625 2023-01-06T08:56:39 Z hollwo_pelw Snake Escaping (JOI18_snake_escaping) C++17
100 / 100
 1244 ms 26056 KB 
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/trie_policy.hpp>
// #include <ext/rope>

using namespace std;
// using namespace __gnu_cxx;
// using namespace __gnu_pbds;

void Hollwo_Pelw();

signed main(){
#ifndef hollwo_pelw_local
	if (fopen(".inp", "r"))
		assert(freopen(".inp", "r", stdin)), assert(freopen(".out", "w", stdout));
#else
	using namespace chrono;
	auto start = steady_clock::now();
#endif
	cin.tie(0), cout.tie(0) -> sync_with_stdio(0);
	int testcases = 1;
	// cin >> testcases;
	for (int test = 1; test <= testcases; test++){
		// cout << "Case #" << test << ": ";
		Hollwo_Pelw();
	}
#ifdef hollwo_pelw_local
	auto end = steady_clock::now();
	cout << "\nExecution time : " << duration_cast<milliseconds> (end - start).count() << "[ms]" << endl;
#endif
}

int n, q, f0[1 << 20], f1[1 << 20], pc[1 << 20];
string s;

void Hollwo_Pelw(){
	cin >> n >> q >> s;
	for (int i = 0; i < 1 << n; i++) {
		f0[i] = f1[i] = s[i] - '0';
	}

	for (int i = 0; i < 1 << n; i++)
		pc[i] = __builtin_popcount(i);

	for (int i = 0; i < n; i++) {
		for (int mask = 0; mask < 1 << n; mask++) {
			if (mask >> i & 1) {
				f0[mask ^ 1 << i] += f0[mask];
				f1[mask] += f1[mask ^ 1 << i];
			}
		}
	}

	for (string base; q --; ) {
		cin >> base;
		reverse(base.begin(), base.end());
		int c0 = 0, c1 = 0, cq = 0;
		for (int i = 0; i < n; i++) {
			if (base[i] == '0') c0 |= 1 << i;
			if (base[i] == '1') c1 |= 1 << i;
			if (base[i] == '?') cq |= 1 << i;
		}

		if (pc[c0] <= 7) {
			int res = 0;
			for (int sub = c0; ; sub = (sub - 1) & c0) {
				res += (pc[c0] % 2 == pc[sub] % 2 ? 1 : -1) * f0[c0 ^ c1 ^ sub];
				if (!sub) break;
			}
			cout << res << '\n';
			continue;
		}
		
		if (pc[c1] <= 7) {
			int res = 0;
			for (int sub = c1; ; sub = (sub - 1) & c1) {
				res += (pc[c1] % 2 == pc[sub] % 2 ? 1 : -1) * f1[cq ^ sub];
				if (!sub) break;
			}
			cout << res << '\n';
			continue;
		}

		if (pc[cq] <= 7) {
			int res = 0;
			for (int sub = cq; ; sub = (sub - 1) & cq) {
				res += s[sub | c1] - '0';
				if (!sub) break;
			}
			cout << res << '\n';
			continue;
		}

	}
}

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 340 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 332 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 340 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 198 ms 15032 KB Output is correct
12 Correct 286 ms 14748 KB Output is correct
13 Correct 295 ms 13924 KB Output is correct
14 Correct 251 ms 14060 KB Output is correct
15 Correct 202 ms 15012 KB Output is correct
16 Correct 236 ms 14204 KB Output is correct
17 Correct 266 ms 14184 KB Output is correct
18 Correct 159 ms 15980 KB Output is correct
19 Correct 243 ms 13000 KB Output is correct
20 Correct 202 ms 14844 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 340 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 198 ms 15032 KB Output is correct
12 Correct 286 ms 14748 KB Output is correct
13 Correct 295 ms 13924 KB Output is correct
14 Correct 251 ms 14060 KB Output is correct
15 Correct 202 ms 15012 KB Output is correct
16 Correct 236 ms 14204 KB Output is correct
17 Correct 266 ms 14184 KB Output is correct
18 Correct 159 ms 15980 KB Output is correct
19 Correct 243 ms 13000 KB Output is correct
20 Correct 202 ms 14844 KB Output is correct
21 Correct 215 ms 18024 KB Output is correct
22 Correct 331 ms 18252 KB Output is correct
23 Correct 378 ms 17288 KB Output is correct
24 Correct 311 ms 17076 KB Output is correct
25 Correct 239 ms 19164 KB Output is correct
26 Correct 280 ms 17568 KB Output is correct
27 Correct 309 ms 17504 KB Output is correct
28 Correct 186 ms 20204 KB Output is correct
29 Correct 356 ms 16028 KB Output is correct
30 Correct 225 ms 18288 KB Output is correct
31 Correct 277 ms 18096 KB Output is correct
32 Correct 275 ms 18104 KB Output is correct
33 Correct 248 ms 16944 KB Output is correct
34 Correct 352 ms 17100 KB Output is correct
35 Correct 340 ms 17536 KB Output is correct
36 Correct 166 ms 16108 KB Output is correct
37 Correct 510 ms 18096 KB Output is correct
38 Correct 343 ms 16080 KB Output is correct
39 Correct 274 ms 17224 KB Output is correct
40 Correct 262 ms 17024 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 340 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 48 ms 15996 KB Output is correct
12 Correct 53 ms 15972 KB Output is correct
13 Correct 63 ms 15936 KB Output is correct
14 Correct 71 ms 15992 KB Output is correct
15 Correct 46 ms 16036 KB Output is correct
16 Correct 61 ms 16048 KB Output is correct
17 Correct 72 ms 15988 KB Output is correct
18 Correct 51 ms 16188 KB Output is correct
19 Correct 50 ms 15832 KB Output is correct
20 Correct 45 ms 16012 KB Output is correct
21 Correct 53 ms 15980 KB Output is correct
22 Correct 79 ms 15948 KB Output is correct
23 Correct 47 ms 15972 KB Output is correct
24 Correct 79 ms 16052 KB Output is correct
25 Correct 114 ms 15952 KB Output is correct
26 Correct 41 ms 15852 KB Output is correct
27 Correct 50 ms 16064 KB Output is correct
28 Correct 54 ms 15852 KB Output is correct
29 Correct 60 ms 15936 KB Output is correct
30 Correct 71 ms 16012 KB Output is correct
31 Correct 58 ms 15980 KB Output is correct
32 Correct 74 ms 15988 KB Output is correct
33 Correct 100 ms 16024 KB Output is correct
34 Correct 40 ms 15860 KB Output is correct
35 Correct 76 ms 15976 KB Output is correct
36 Correct 60 ms 15944 KB Output is correct
37 Correct 89 ms 15932 KB Output is correct
38 Correct 88 ms 15960 KB Output is correct
39 Correct 76 ms 16020 KB Output is correct
40 Correct 62 ms 15940 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 340 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 198 ms 15032 KB Output is correct
12 Correct 286 ms 14748 KB Output is correct
13 Correct 295 ms 13924 KB Output is correct
14 Correct 251 ms 14060 KB Output is correct
15 Correct 202 ms 15012 KB Output is correct
16 Correct 236 ms 14204 KB Output is correct
17 Correct 266 ms 14184 KB Output is correct
18 Correct 159 ms 15980 KB Output is correct
19 Correct 243 ms 13000 KB Output is correct
20 Correct 202 ms 14844 KB Output is correct
21 Correct 215 ms 18024 KB Output is correct
22 Correct 331 ms 18252 KB Output is correct
23 Correct 378 ms 17288 KB Output is correct
24 Correct 311 ms 17076 KB Output is correct
25 Correct 239 ms 19164 KB Output is correct
26 Correct 280 ms 17568 KB Output is correct
27 Correct 309 ms 17504 KB Output is correct
28 Correct 186 ms 20204 KB Output is correct
29 Correct 356 ms 16028 KB Output is correct
30 Correct 225 ms 18288 KB Output is correct
31 Correct 277 ms 18096 KB Output is correct
32 Correct 275 ms 18104 KB Output is correct
33 Correct 248 ms 16944 KB Output is correct
34 Correct 352 ms 17100 KB Output is correct
35 Correct 340 ms 17536 KB Output is correct
36 Correct 166 ms 16108 KB Output is correct
37 Correct 510 ms 18096 KB Output is correct
38 Correct 343 ms 16080 KB Output is correct
39 Correct 274 ms 17224 KB Output is correct
40 Correct 262 ms 17024 KB Output is correct
41 Correct 48 ms 15996 KB Output is correct
42 Correct 53 ms 15972 KB Output is correct
43 Correct 63 ms 15936 KB Output is correct
44 Correct 71 ms 15992 KB Output is correct
45 Correct 46 ms 16036 KB Output is correct
46 Correct 61 ms 16048 KB Output is correct
47 Correct 72 ms 15988 KB Output is correct
48 Correct 51 ms 16188 KB Output is correct
49 Correct 50 ms 15832 KB Output is correct
50 Correct 45 ms 16012 KB Output is correct
51 Correct 53 ms 15980 KB Output is correct
52 Correct 79 ms 15948 KB Output is correct
53 Correct 47 ms 15972 KB Output is correct
54 Correct 79 ms 16052 KB Output is correct
55 Correct 114 ms 15952 KB Output is correct
56 Correct 41 ms 15852 KB Output is correct
57 Correct 50 ms 16064 KB Output is correct
58 Correct 54 ms 15852 KB Output is correct
59 Correct 60 ms 15936 KB Output is correct
60 Correct 71 ms 16012 KB Output is correct
61 Correct 58 ms 15980 KB Output is correct
62 Correct 74 ms 15988 KB Output is correct
63 Correct 100 ms 16024 KB Output is correct
64 Correct 40 ms 15860 KB Output is correct
65 Correct 76 ms 15976 KB Output is correct
66 Correct 60 ms 15944 KB Output is correct
67 Correct 89 ms 15932 KB Output is correct
68 Correct 88 ms 15960 KB Output is correct
69 Correct 76 ms 16020 KB Output is correct
70 Correct 62 ms 15940 KB Output is correct
71 Correct 297 ms 21596 KB Output is correct
72 Correct 410 ms 21720 KB Output is correct
73 Correct 656 ms 20312 KB Output is correct
74 Correct 1244 ms 20640 KB Output is correct
75 Correct 403 ms 24056 KB Output is correct
76 Correct 724 ms 22340 KB Output is correct
77 Correct 1010 ms 22264 KB Output is correct
78 Correct 236 ms 26056 KB Output is correct
79 Correct 320 ms 19952 KB Output is correct
80 Correct 333 ms 23228 KB Output is correct
81 Correct 574 ms 23020 KB Output is correct
82 Correct 725 ms 21992 KB Output is correct
83 Correct 407 ms 21192 KB Output is correct
84 Correct 851 ms 21996 KB Output is correct
85 Correct 890 ms 22072 KB Output is correct
86 Correct 199 ms 19956 KB Output is correct
87 Correct 334 ms 22912 KB Output is correct
88 Correct 450 ms 20112 KB Output is correct
89 Correct 470 ms 21556 KB Output is correct
90 Correct 909 ms 21880 KB Output is correct
91 Correct 381 ms 21132 KB Output is correct
92 Correct 862 ms 22156 KB Output is correct
93 Correct 876 ms 22008 KB Output is correct
94 Correct 207 ms 19784 KB Output is correct
95 Correct 632 ms 21776 KB Output is correct
96 Correct 656 ms 21784 KB Output is correct
97 Correct 665 ms 21392 KB Output is correct
98 Correct 656 ms 21112 KB Output is correct
99 Correct 651 ms 20860 KB Output is correct
100 Correct 610 ms 20592 KB Output is correct