oj.uz

Submission #535014

# Submission time Handle Problem Language Result Execution time Memory
535014 2022-03-09T09:53:57 Z pooyashams Snake Escaping (JOI18_snake_escaping) C++14
75 / 100
 2000 ms 17732 KB 
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cstring>
#include <iomanip>
#include <vector>
#include <bitset>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

const int lgmx = 20;
const int maxn = (1<<lgmx);

int val[maxn];
int sub[maxn];
int sup[maxn];

int32_t main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int L, q; cin >> L >> q;
	const int n = (1<<L);
	for(int i = 0; i < n; i++)
	{
		char c; cin >> c;
		val[i] = c-'0';
		sub[i] = val[i];
		sup[i] = val[i];
	}
	for(int j = 0; j < L; j++)
		for(int i = 0; i < n; i++)
			if((i>>j) & 1)
				sub[i] += sub[i^(1<<j)];
	for(int j = L-1; j >= 0; j--)
		for(int i = n-1; i >= 0; i--)
			if((i>>j) & 1)
				sup[i^(1<<j)] += sup[i];
	vector<int> vec[3];
	for(int i = 0; i < 3; i++) vec[i].reserve(20);
	const int l3 = L/3;
	while(q--)
	{
		for(int i = 0; i < 3; i++) vec[i].clear();
		string s; cin >> s;
		reverse(s.begin(), s.end());
		for(int i = 0; i < L; i++)
		{
			if(s[i] == '?')
				vec[2].push_back(i);
			else
				vec[s[i]-'0'].push_back(i);
		}
		if((int)(vec[0].size()) <= l3)
		{
			int a = vec[0].size();
			int k = 0;
			for(int j: vec[1]) k ^= (1<<j);
			int ans = 0;
			for(int i = 0; i < (1<<a); i++)
			{
				int x = k;
				for(int j = i; j > 0; j -= j&-j)
					x ^= (1<<vec[0][__builtin_ctz(j)]);
				if(__builtin_popcount(i) & 1)
					ans -= sup[x];
				else
					ans += sup[x];
			}
			cout << ans << endl;
		}
		else if((int)(vec[1].size()) <= l3)
		{
			int a = vec[1].size();
			int k = 0;
			for(int j: vec[2]) k ^= (1<<j);
			int ans = 0;
			for(int i = 0; i < (1<<a); i++)
			{
				int x = k;
				for(int j = i; j > 0; j -= j&-j)
					x ^= (1<<vec[1][__builtin_ctz(j)]);
				if( (a-__builtin_popcount(i)) & 1)
					ans -= sub[x];
				else
					ans += sub[x];
			}
			cout << ans << endl;
		}
		else
		{
			int a = vec[2].size();
			int k = 0;
			for(int j: vec[1]) k ^= (1<<j);
			int ans = 0;
			for(int i = 0; i < (1<<a); i++)
			{
				int x = k;
				for(int j = i; j > 0; j -= j&-j)
					x ^= (1<<vec[2][__builtin_ctz(j)]);
				ans += val[x];
			}
			cout << ans << endl;
		}
	}
	return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 2 ms 324 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 2 ms 328 KB Output is correct
11 Correct 1459 ms 5208 KB Output is correct
12 Correct 1452 ms 5004 KB Output is correct
13 Correct 1444 ms 4152 KB Output is correct
14 Correct 1434 ms 4300 KB Output is correct
15 Correct 1451 ms 5156 KB Output is correct
16 Correct 1465 ms 4308 KB Output is correct
17 Correct 1522 ms 4240 KB Output is correct
18 Correct 1362 ms 6212 KB Output is correct
19 Correct 1399 ms 3184 KB Output is correct
20 Correct 1464 ms 4876 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 2 ms 324 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 2 ms 328 KB Output is correct
11 Correct 1459 ms 5208 KB Output is correct
12 Correct 1452 ms 5004 KB Output is correct
13 Correct 1444 ms 4152 KB Output is correct
14 Correct 1434 ms 4300 KB Output is correct
15 Correct 1451 ms 5156 KB Output is correct
16 Correct 1465 ms 4308 KB Output is correct
17 Correct 1522 ms 4240 KB Output is correct
18 Correct 1362 ms 6212 KB Output is correct
19 Correct 1399 ms 3184 KB Output is correct
20 Correct 1464 ms 4876 KB Output is correct
21 Correct 1523 ms 5188 KB Output is correct
22 Correct 1483 ms 5404 KB Output is correct
23 Correct 1519 ms 4388 KB Output is correct
24 Correct 1544 ms 4300 KB Output is correct
25 Correct 1503 ms 6196 KB Output is correct
26 Correct 1568 ms 4828 KB Output is correct
27 Correct 1519 ms 4844 KB Output is correct
28 Correct 1363 ms 7240 KB Output is correct
29 Correct 1426 ms 3188 KB Output is correct
30 Correct 1556 ms 5328 KB Output is correct
31 Correct 1660 ms 5188 KB Output is correct
32 Correct 1526 ms 5232 KB Output is correct
33 Correct 1479 ms 4104 KB Output is correct
34 Correct 1517 ms 4156 KB Output is correct
35 Correct 1634 ms 4508 KB Output is correct
36 Correct 1458 ms 3128 KB Output is correct
37 Correct 1466 ms 5168 KB Output is correct
38 Correct 1412 ms 3016 KB Output is correct
39 Correct 1499 ms 4224 KB Output is correct
40 Correct 1669 ms 3984 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 2 ms 324 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 2 ms 328 KB Output is correct
11 Correct 196 ms 13496 KB Output is correct
12 Correct 170 ms 13432 KB Output is correct
13 Correct 172 ms 13436 KB Output is correct
14 Correct 219 ms 13368 KB Output is correct
15 Correct 137 ms 13380 KB Output is correct
16 Correct 158 ms 13304 KB Output is correct
17 Correct 182 ms 13312 KB Output is correct
18 Correct 132 ms 13504 KB Output is correct
19 Correct 140 ms 13236 KB Output is correct
20 Correct 153 ms 13404 KB Output is correct
21 Correct 175 ms 13476 KB Output is correct
22 Correct 156 ms 13304 KB Output is correct
23 Correct 151 ms 13260 KB Output is correct
24 Correct 191 ms 13232 KB Output is correct
25 Correct 170 ms 13336 KB Output is correct
26 Correct 142 ms 13200 KB Output is correct
27 Correct 151 ms 13252 KB Output is correct
28 Correct 136 ms 13240 KB Output is correct
29 Correct 149 ms 13236 KB Output is correct
30 Correct 160 ms 13300 KB Output is correct
31 Correct 144 ms 13272 KB Output is correct
32 Correct 174 ms 13224 KB Output is correct
33 Correct 200 ms 13220 KB Output is correct
34 Correct 170 ms 13132 KB Output is correct
35 Correct 158 ms 13252 KB Output is correct
36 Correct 165 ms 13280 KB Output is correct
37 Correct 222 ms 13248 KB Output is correct
38 Correct 159 ms 13364 KB Output is correct
39 Correct 155 ms 13232 KB Output is correct
40 Correct 176 ms 13160 KB Output is correct

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 2 ms 324 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 2 ms 328 KB Output is correct
11 Correct 1459 ms 5208 KB Output is correct
12 Correct 1452 ms 5004 KB Output is correct
13 Correct 1444 ms 4152 KB Output is correct
14 Correct 1434 ms 4300 KB Output is correct
15 Correct 1451 ms 5156 KB Output is correct
16 Correct 1465 ms 4308 KB Output is correct
17 Correct 1522 ms 4240 KB Output is correct
18 Correct 1362 ms 6212 KB Output is correct
19 Correct 1399 ms 3184 KB Output is correct
20 Correct 1464 ms 4876 KB Output is correct
21 Correct 1523 ms 5188 KB Output is correct
22 Correct 1483 ms 5404 KB Output is correct
23 Correct 1519 ms 4388 KB Output is correct
24 Correct 1544 ms 4300 KB Output is correct
25 Correct 1503 ms 6196 KB Output is correct
26 Correct 1568 ms 4828 KB Output is correct
27 Correct 1519 ms 4844 KB Output is correct
28 Correct 1363 ms 7240 KB Output is correct
29 Correct 1426 ms 3188 KB Output is correct
30 Correct 1556 ms 5328 KB Output is correct
31 Correct 1660 ms 5188 KB Output is correct
32 Correct 1526 ms 5232 KB Output is correct
33 Correct 1479 ms 4104 KB Output is correct
34 Correct 1517 ms 4156 KB Output is correct
35 Correct 1634 ms 4508 KB Output is correct
36 Correct 1458 ms 3128 KB Output is correct
37 Correct 1466 ms 5168 KB Output is correct
38 Correct 1412 ms 3016 KB Output is correct
39 Correct 1499 ms 4224 KB Output is correct
40 Correct 1669 ms 3984 KB Output is correct
41 Correct 196 ms 13496 KB Output is correct
42 Correct 170 ms 13432 KB Output is correct
43 Correct 172 ms 13436 KB Output is correct
44 Correct 219 ms 13368 KB Output is correct
45 Correct 137 ms 13380 KB Output is correct
46 Correct 158 ms 13304 KB Output is correct
47 Correct 182 ms 13312 KB Output is correct
48 Correct 132 ms 13504 KB Output is correct
49 Correct 140 ms 13236 KB Output is correct
50 Correct 153 ms 13404 KB Output is correct
51 Correct 175 ms 13476 KB Output is correct
52 Correct 156 ms 13304 KB Output is correct
53 Correct 151 ms 13260 KB Output is correct
54 Correct 191 ms 13232 KB Output is correct
55 Correct 170 ms 13336 KB Output is correct
56 Correct 142 ms 13200 KB Output is correct
57 Correct 151 ms 13252 KB Output is correct
58 Correct 136 ms 13240 KB Output is correct
59 Correct 149 ms 13236 KB Output is correct
60 Correct 160 ms 13300 KB Output is correct
61 Correct 144 ms 13272 KB Output is correct
62 Correct 174 ms 13224 KB Output is correct
63 Correct 200 ms 13220 KB Output is correct
64 Correct 170 ms 13132 KB Output is correct
65 Correct 158 ms 13252 KB Output is correct
66 Correct 165 ms 13280 KB Output is correct
67 Correct 222 ms 13248 KB Output is correct
68 Correct 159 ms 13364 KB Output is correct
69 Correct 155 ms 13232 KB Output is correct
70 Correct 176 ms 13160 KB Output is correct
71 Correct 1681 ms 17616 KB Output is correct
72 Correct 1813 ms 17732 KB Output is correct
73 Execution timed out 2013 ms 16344 KB Time limit exceeded
74 Halted 0 ms 0 KB -