oj.uz

Submission #534365

# Submission time Handle Problem Language Result Execution time Memory
534365 2022-03-08T06:05:34 Z rk42745417 Snake Escaping (JOI18_snake_escaping) C++17
75 / 100
 2000 ms 21716 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;
}();
/*--------------------------------------------------------------------------------------*/

signed main() {
	int l, q;
	cin >> l >> q;
	vector<int> arr(1 << l), dp(1 << l), dp2(1 << l);
	{
		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)];
	function<int(const string&, int, 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);
	};
	function<int(const string &s, int, int, 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);
	};
	function<int(const string &s, int, int, 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);
	};

	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:56:14: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   56 |    if(j >> i & 1 ^ 1)
      |       ~~~~~~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 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 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 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 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 304 ms 4292 KB Output is correct
12 Correct 329 ms 3908 KB Output is correct
13 Correct 379 ms 3140 KB Output is correct
14 Correct 537 ms 3256 KB Output is correct
15 Correct 393 ms 4328 KB Output is correct
16 Correct 512 ms 3460 KB Output is correct
17 Correct 483 ms 3456 KB Output is correct
18 Correct 264 ms 5244 KB Output is correct
19 Correct 263 ms 2296 KB Output is correct
20 Correct 296 ms 3940 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 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 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 304 ms 4292 KB Output is correct
12 Correct 329 ms 3908 KB Output is correct
13 Correct 379 ms 3140 KB Output is correct
14 Correct 537 ms 3256 KB Output is correct
15 Correct 393 ms 4328 KB Output is correct
16 Correct 512 ms 3460 KB Output is correct
17 Correct 483 ms 3456 KB Output is correct
18 Correct 264 ms 5244 KB Output is correct
19 Correct 263 ms 2296 KB Output is correct
20 Correct 296 ms 3940 KB Output is correct
21 Correct 339 ms 4344 KB Output is correct
22 Correct 345 ms 4536 KB Output is correct
23 Correct 737 ms 3532 KB Output is correct
24 Correct 944 ms 3540 KB Output is correct
25 Correct 520 ms 5408 KB Output is correct
26 Correct 843 ms 3936 KB Output is correct
27 Correct 701 ms 3884 KB Output is correct
28 Correct 271 ms 6340 KB Output is correct
29 Correct 300 ms 2328 KB Output is correct
30 Correct 323 ms 4520 KB Output is correct
31 Correct 599 ms 4332 KB Output is correct
32 Correct 972 ms 4564 KB Output is correct
33 Correct 449 ms 3224 KB Output is correct
34 Correct 773 ms 3392 KB Output is correct
35 Correct 670 ms 3872 KB Output is correct
36 Correct 296 ms 2408 KB Output is correct
37 Correct 307 ms 4384 KB Output is correct
38 Correct 301 ms 2336 KB Output is correct
39 Correct 641 ms 3564 KB Output is correct
40 Correct 916 ms 3372 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 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 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 71 ms 14772 KB Output is correct
12 Correct 74 ms 14696 KB Output is correct
13 Correct 121 ms 14696 KB Output is correct
14 Correct 236 ms 14696 KB Output is correct
15 Correct 90 ms 14740 KB Output is correct
16 Correct 220 ms 14696 KB Output is correct
17 Correct 195 ms 14696 KB Output is correct
18 Correct 86 ms 14696 KB Output is correct
19 Correct 73 ms 14788 KB Output is correct
20 Correct 79 ms 14696 KB Output is correct
21 Correct 128 ms 14696 KB Output is correct
22 Correct 316 ms 14696 KB Output is correct
23 Correct 86 ms 14824 KB Output is correct
24 Correct 202 ms 14764 KB Output is correct
25 Correct 179 ms 14696 KB Output is correct
26 Correct 64 ms 14696 KB Output is correct
27 Correct 70 ms 14696 KB Output is correct
28 Correct 102 ms 14696 KB Output is correct
29 Correct 137 ms 14696 KB Output is correct
30 Correct 198 ms 14696 KB Output is correct
31 Correct 93 ms 14696 KB Output is correct
32 Correct 228 ms 14732 KB Output is correct
33 Correct 170 ms 14696 KB Output is correct
34 Correct 61 ms 14696 KB Output is correct
35 Correct 146 ms 14696 KB Output is correct
36 Correct 145 ms 14696 KB Output is correct
37 Correct 143 ms 14724 KB Output is correct
38 Correct 160 ms 14696 KB Output is correct
39 Correct 143 ms 14696 KB Output is correct
40 Correct 144 ms 14760 KB Output is correct

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 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 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 304 ms 4292 KB Output is correct
12 Correct 329 ms 3908 KB Output is correct
13 Correct 379 ms 3140 KB Output is correct
14 Correct 537 ms 3256 KB Output is correct
15 Correct 393 ms 4328 KB Output is correct
16 Correct 512 ms 3460 KB Output is correct
17 Correct 483 ms 3456 KB Output is correct
18 Correct 264 ms 5244 KB Output is correct
19 Correct 263 ms 2296 KB Output is correct
20 Correct 296 ms 3940 KB Output is correct
21 Correct 339 ms 4344 KB Output is correct
22 Correct 345 ms 4536 KB Output is correct
23 Correct 737 ms 3532 KB Output is correct
24 Correct 944 ms 3540 KB Output is correct
25 Correct 520 ms 5408 KB Output is correct
26 Correct 843 ms 3936 KB Output is correct
27 Correct 701 ms 3884 KB Output is correct
28 Correct 271 ms 6340 KB Output is correct
29 Correct 300 ms 2328 KB Output is correct
30 Correct 323 ms 4520 KB Output is correct
31 Correct 599 ms 4332 KB Output is correct
32 Correct 972 ms 4564 KB Output is correct
33 Correct 449 ms 3224 KB Output is correct
34 Correct 773 ms 3392 KB Output is correct
35 Correct 670 ms 3872 KB Output is correct
36 Correct 296 ms 2408 KB Output is correct
37 Correct 307 ms 4384 KB Output is correct
38 Correct 301 ms 2336 KB Output is correct
39 Correct 641 ms 3564 KB Output is correct
40 Correct 916 ms 3372 KB Output is correct
41 Correct 71 ms 14772 KB Output is correct
42 Correct 74 ms 14696 KB Output is correct
43 Correct 121 ms 14696 KB Output is correct
44 Correct 236 ms 14696 KB Output is correct
45 Correct 90 ms 14740 KB Output is correct
46 Correct 220 ms 14696 KB Output is correct
47 Correct 195 ms 14696 KB Output is correct
48 Correct 86 ms 14696 KB Output is correct
49 Correct 73 ms 14788 KB Output is correct
50 Correct 79 ms 14696 KB Output is correct
51 Correct 128 ms 14696 KB Output is correct
52 Correct 316 ms 14696 KB Output is correct
53 Correct 86 ms 14824 KB Output is correct
54 Correct 202 ms 14764 KB Output is correct
55 Correct 179 ms 14696 KB Output is correct
56 Correct 64 ms 14696 KB Output is correct
57 Correct 70 ms 14696 KB Output is correct
58 Correct 102 ms 14696 KB Output is correct
59 Correct 137 ms 14696 KB Output is correct
60 Correct 198 ms 14696 KB Output is correct
61 Correct 93 ms 14696 KB Output is correct
62 Correct 228 ms 14732 KB Output is correct
63 Correct 170 ms 14696 KB Output is correct
64 Correct 61 ms 14696 KB Output is correct
65 Correct 146 ms 14696 KB Output is correct
66 Correct 145 ms 14696 KB Output is correct
67 Correct 143 ms 14724 KB Output is correct
68 Correct 160 ms 14696 KB Output is correct
69 Correct 143 ms 14696 KB Output is correct
70 Correct 144 ms 14760 KB Output is correct
71 Correct 568 ms 20336 KB Output is correct
72 Correct 611 ms 21716 KB Output is correct
73 Correct 1584 ms 20232 KB Output is correct
74 Execution timed out 2048 ms 17076 KB Time limit exceeded
75 Halted 0 ms 0 KB -