oj.uz

Submission #534373

# Submission time Handle Problem Language Result Execution time Memory
534373 2022-03-08T06:11:18 Z rk42745417 Snake Escaping (JOI18_snake_escaping) C++17
100 / 100
 1694 ms 42304 KB 
/*
--------------              |   /
      |                     |  /
      |                     | /
      |             *       |/          |    |         ------            *
      |                     |           |    |        /      \
      |             |       |\          |    |       |       |\          |
   \  |             |       | \         |    |       |       | \         |
    \ |             |       |  \        |    |        \     /   \        |
     V              |       |   \        \__/|         -----     \       |
*/
#include <bits/stdc++.h>
using namespace std;
#define debug(x) cerr << "\e[1;31m" << #x << " = " << (x) << "\e[0m\n"
#define print(x) emilia_mata_tenshi(#x, begin(x), end(x))
template<typename T> void emilia_mata_tenshi(const char *s, T l, T r) {
	cerr << "\e[1;33m" << s << " = [";
	while(l != r) {
		cerr << *l;
		cerr << (++l == r ? ']' : ',');
	}
	cerr << "\e[0m\n";
}

#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);
using ll = int64_t;
using ull = uint64_t;
using ld = long double;
using uint = uint32_t;
const double EPS  = 1e-8;
const int INF     = 0x3F3F3F3F;
const ll LINF     = 4611686018427387903;
const int MOD     = 1e9+7;
static int Lamy_is_cute = []() {
	EmiliaMyWife
	return 48763;
}();
/*--------------------------------------------------------------------------------------*/

const int N = 2e6 + 25;
int arr[N], dp[N], dp2[N], l;
int dfs(const string &s, int n, int cur) {
	if(n == l)
		return arr[cur];
	if(s[n] == '?')
		return dfs(s, n + 1, cur) + dfs(s, n + 1, cur | (1 << n));
	if(s[n] == '1')
		return dfs(s, n + 1, cur | (1 << n));
	return dfs(s, n + 1, cur);
}
int dfs2(const string &s, int n, int cur, int cnt) {
	if(n == l)
		return dp[cur] * (cnt % 2 ? -1 : 1);
	if(s[n] == '?')
		return dfs2(s, n + 1, cur | (1 << n), cnt);
	if(s[n] == '0')
		return dfs2(s, n + 1, cur, cnt);
	return dfs2(s, n + 1, cur | (1 << n), cnt) + dfs2(s, n + 1, cur, cnt + 1);
}
int dfs3(const string &s, int n, int cur, int cnt) {
	if(n == l)
		return dp2[cur] * (cnt % 2 ? -1 : 1);
	if(s[n] == '?')
		return dfs3(s, n + 1, cur, cnt);
	if(s[n] == '1')
		return dfs3(s, n + 1, cur | (1 << n), cnt);
	return dfs3(s, n + 1, cur | (1 << n), cnt + 1) + dfs3(s, n + 1, cur, cnt);
}

signed main() {
	int q;
	cin >> l >> q;
	{
		string s;
		cin >> s;
		for(int i = 0; i < (1 << l); i++)
			arr[i] = dp[i] = dp2[i] = s[i] - '0';
	}
	for(int i = 0; i < l; i++)
		for(int j = 0; j < (1 << l); j++)
			if(j >> i & 1)
				dp[j] += dp[j ^ (1 << i)];
	for(int i = 0; i < l; i++)
		for(int j = 0; j < (1 << l); j++)
			if(j >> i & 1 ^ 1)
				dp2[j] += dp2[j ^ (1 << i)];

	while(q--) {
		string s;
		cin >> s;
		reverse(s.begin(), s.end());
		int cnt = 0, cnt2 = 0;
		for(char c : s) {
			cnt += c == '?';
			cnt2 += c == '1';
		}
		int cnt3 = l - (cnt + cnt2);
		if(cnt <= min(cnt3, cnt2))
			cout << dfs(s, 0, 0) << '\n';
		else if(cnt2 <= min(cnt, cnt3))
			cout << dfs2(s, 0, 0, 0) << '\n';
		else
			cout << dfs3(s, 0, 0, 0) << '\n';
	}
}

Compilation message

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:85:14: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   85 |    if(j >> i & 1 ^ 1)
      |       ~~~~~~~^~~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 208 ms 4512 KB Output is correct
12 Correct 212 ms 4112 KB Output is correct
13 Correct 244 ms 3396 KB Output is correct
14 Correct 252 ms 3448 KB Output is correct
15 Correct 256 ms 4656 KB Output is correct
16 Correct 312 ms 3796 KB Output is correct
17 Correct 273 ms 3608 KB Output is correct
18 Correct 165 ms 5500 KB Output is correct
19 Correct 154 ms 2496 KB Output is correct
20 Correct 210 ms 4208 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 208 ms 4512 KB Output is correct
12 Correct 212 ms 4112 KB Output is correct
13 Correct 244 ms 3396 KB Output is correct
14 Correct 252 ms 3448 KB Output is correct
15 Correct 256 ms 4656 KB Output is correct
16 Correct 312 ms 3796 KB Output is correct
17 Correct 273 ms 3608 KB Output is correct
18 Correct 165 ms 5500 KB Output is correct
19 Correct 154 ms 2496 KB Output is correct
20 Correct 210 ms 4208 KB Output is correct
21 Correct 228 ms 4640 KB Output is correct
22 Correct 233 ms 4804 KB Output is correct
23 Correct 335 ms 3800 KB Output is correct
24 Correct 411 ms 3640 KB Output is correct
25 Correct 316 ms 5572 KB Output is correct
26 Correct 446 ms 4144 KB Output is correct
27 Correct 403 ms 4184 KB Output is correct
28 Correct 191 ms 6596 KB Output is correct
29 Correct 177 ms 2612 KB Output is correct
30 Correct 236 ms 4804 KB Output is correct
31 Correct 444 ms 4632 KB Output is correct
32 Correct 631 ms 4676 KB Output is correct
33 Correct 272 ms 3524 KB Output is correct
34 Correct 421 ms 3584 KB Output is correct
35 Correct 398 ms 4236 KB Output is correct
36 Correct 181 ms 2608 KB Output is correct
37 Correct 233 ms 4684 KB Output is correct
38 Correct 179 ms 2648 KB Output is correct
39 Correct 353 ms 3892 KB Output is correct
40 Correct 413 ms 3608 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 61 ms 14096 KB Output is correct
12 Correct 72 ms 13936 KB Output is correct
13 Correct 77 ms 13936 KB Output is correct
14 Correct 123 ms 13936 KB Output is correct
15 Correct 71 ms 13908 KB Output is correct
16 Correct 118 ms 13920 KB Output is correct
17 Correct 101 ms 13936 KB Output is correct
18 Correct 53 ms 13936 KB Output is correct
19 Correct 54 ms 13920 KB Output is correct
20 Correct 60 ms 13940 KB Output is correct
21 Correct 84 ms 13924 KB Output is correct
22 Correct 118 ms 13916 KB Output is correct
23 Correct 62 ms 13936 KB Output is correct
24 Correct 112 ms 13956 KB Output is correct
25 Correct 101 ms 13984 KB Output is correct
26 Correct 52 ms 13936 KB Output is correct
27 Correct 58 ms 13932 KB Output is correct
28 Correct 56 ms 13936 KB Output is correct
29 Correct 89 ms 13936 KB Output is correct
30 Correct 100 ms 13972 KB Output is correct
31 Correct 67 ms 13936 KB Output is correct
32 Correct 114 ms 13936 KB Output is correct
33 Correct 108 ms 13932 KB Output is correct
34 Correct 54 ms 13936 KB Output is correct
35 Correct 85 ms 13936 KB Output is correct
36 Correct 85 ms 13944 KB Output is correct
37 Correct 86 ms 13936 KB Output is correct
38 Correct 88 ms 13936 KB Output is correct
39 Correct 93 ms 13936 KB Output is correct
40 Correct 86 ms 13940 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 208 ms 4512 KB Output is correct
12 Correct 212 ms 4112 KB Output is correct
13 Correct 244 ms 3396 KB Output is correct
14 Correct 252 ms 3448 KB Output is correct
15 Correct 256 ms 4656 KB Output is correct
16 Correct 312 ms 3796 KB Output is correct
17 Correct 273 ms 3608 KB Output is correct
18 Correct 165 ms 5500 KB Output is correct
19 Correct 154 ms 2496 KB Output is correct
20 Correct 210 ms 4208 KB Output is correct
21 Correct 228 ms 4640 KB Output is correct
22 Correct 233 ms 4804 KB Output is correct
23 Correct 335 ms 3800 KB Output is correct
24 Correct 411 ms 3640 KB Output is correct
25 Correct 316 ms 5572 KB Output is correct
26 Correct 446 ms 4144 KB Output is correct
27 Correct 403 ms 4184 KB Output is correct
28 Correct 191 ms 6596 KB Output is correct
29 Correct 177 ms 2612 KB Output is correct
30 Correct 236 ms 4804 KB Output is correct
31 Correct 444 ms 4632 KB Output is correct
32 Correct 631 ms 4676 KB Output is correct
33 Correct 272 ms 3524 KB Output is correct
34 Correct 421 ms 3584 KB Output is correct
35 Correct 398 ms 4236 KB Output is correct
36 Correct 181 ms 2608 KB Output is correct
37 Correct 233 ms 4684 KB Output is correct
38 Correct 179 ms 2648 KB Output is correct
39 Correct 353 ms 3892 KB Output is correct
40 Correct 413 ms 3608 KB Output is correct
41 Correct 61 ms 14096 KB Output is correct
42 Correct 72 ms 13936 KB Output is correct
43 Correct 77 ms 13936 KB Output is correct
44 Correct 123 ms 13936 KB Output is correct
45 Correct 71 ms 13908 KB Output is correct
46 Correct 118 ms 13920 KB Output is correct
47 Correct 101 ms 13936 KB Output is correct
48 Correct 53 ms 13936 KB Output is correct
49 Correct 54 ms 13920 KB Output is correct
50 Correct 60 ms 13940 KB Output is correct
51 Correct 84 ms 13924 KB Output is correct
52 Correct 118 ms 13916 KB Output is correct
53 Correct 62 ms 13936 KB Output is correct
54 Correct 112 ms 13956 KB Output is correct
55 Correct 101 ms 13984 KB Output is correct
56 Correct 52 ms 13936 KB Output is correct
57 Correct 58 ms 13932 KB Output is correct
58 Correct 56 ms 13936 KB Output is correct
59 Correct 89 ms 13936 KB Output is correct
60 Correct 100 ms 13972 KB Output is correct
61 Correct 67 ms 13936 KB Output is correct
62 Correct 114 ms 13936 KB Output is correct
63 Correct 108 ms 13932 KB Output is correct
64 Correct 54 ms 13936 KB Output is correct
65 Correct 85 ms 13936 KB Output is correct
66 Correct 85 ms 13944 KB Output is correct
67 Correct 86 ms 13936 KB Output is correct
68 Correct 88 ms 13936 KB Output is correct
69 Correct 93 ms 13936 KB Output is correct
70 Correct 86 ms 13940 KB Output is correct
71 Correct 369 ms 18048 KB Output is correct
72 Correct 371 ms 17876 KB Output is correct
73 Correct 754 ms 16440 KB Output is correct
74 Correct 1694 ms 18316 KB Output is correct
75 Correct 585 ms 40380 KB Output is correct
76 Correct 1549 ms 38556 KB Output is correct
77 Correct 1283 ms 38588 KB Output is correct
78 Correct 314 ms 42304 KB Output is correct
79 Correct 357 ms 36200 KB Output is correct
80 Correct 474 ms 39400 KB Output is correct
81 Correct 1053 ms 39304 KB Output is correct
82 Correct 1651 ms 38488 KB Output is correct
83 Correct 497 ms 37548 KB Output is correct
84 Correct 1331 ms 38312 KB Output is correct
85 Correct 1248 ms 38604 KB Output is correct
86 Correct 281 ms 36308 KB Output is correct
87 Correct 396 ms 39248 KB Output is correct
88 Correct 327 ms 36360 KB Output is correct
89 Correct 797 ms 37960 KB Output is correct
90 Correct 1327 ms 38288 KB Output is correct
91 Correct 500 ms 37480 KB Output is correct
92 Correct 1579 ms 38580 KB Output is correct
93 Correct 1303 ms 38644 KB Output is correct
94 Correct 284 ms 36304 KB Output is correct
95 Correct 969 ms 38576 KB Output is correct
96 Correct 956 ms 38564 KB Output is correct
97 Correct 971 ms 38412 KB Output is correct
98 Correct 974 ms 38612 KB Output is correct
99 Correct 949 ms 38516 KB Output is correct
100 Correct 967 ms 38328 KB Output is correct