oj.uz

Submission #590285

# Submission time Handle Problem Language Result Execution time Memory
590285 2022-07-05T18:11:00 Z blue Snake Escaping (JOI18_snake_escaping) C++17
100 / 100
 1587 ms 46212 KB 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

using vi = vector<int>;
#define sz(x) int(x.size())

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int L, Q;
	cin >> L >> Q;

	vi A((1<<L));
	for(int i = 0; i < (1<<L); i++)
	{
		char c;
		cin >> c;
		A[i] = c - '0';
	}

	vi lowersum = A;

	vi uppersum = A; 
	reverse(uppersum.begin(), uppersum.end());

	for(int b = 0; b < L; b++)
	{
		for(int i = 0; i < (1<<L); i++)
		{
			if(i & (1<<b))
			{
				lowersum[i] += lowersum[i ^ (1<<b)];
				uppersum[i] += uppersum[i ^ (1<<b)];
			}
		}
	}

	vi getbit((1<<L));
	for(int i = 0; i < L; i++)
		getbit[(1<<i)] = i;

	for(int j = 0; j < Q; j++)
	{
		vi p0, p1, pq;

		int onemask = 0;
		int qmask = 0;
		int zeromask = 0;

		for(int b = L-1; b >= 0; b--)
		{
			char c;
			cin >> c;

			if(c == '0')
			{
				p0.push_back(b);
				zeromask += (1<<b);
			}
			else if(c == '1')
			{
				p1.push_back(b);
				onemask += (1<<b);
			}
			else
			{
				pq.push_back(b);
				qmask += (1<<b);
			}
		}

		int res = 0;


		if(sz(p1) <= 6)
		{
			// cerr << "p1 size = " << sz(p1) << '\n';
			vi ssum((1 << sz(p1)), 0);
			vi sign((1 << sz(p1)), +1);

			if(sz(p1) % 2 == 0)
				sign[0] = +1;
			else
				sign[0] = -1;

			for(int m = 1; m < (1<<sz(p1)); m++)
			{
				ssum[m] = ssum[m - (m&-m)] + (1 << p1[getbit[m&-m]]);
				sign[m] = -1 * sign[m - (m&-m)];
			}

			for(int m = 0; m < (1<<sz(p1)); m++)
			{
				// cerr << "m = " << m << '\n';
				// cerr << "sign = " << sign[m] << '\n';
				res += lowersum[qmask | ssum[m]] * sign[m];
			}
		}
		else if(sz(p0) <= 6)
		{
			// cerr << "p0 size = " << sz(p0) << '\n';
			vi ssum((1 << sz(p0)), 0);
			vi sign((1 << sz(p0)), +1);

			if(sz(p0) % 2 == 0)
				sign[0] = +1;
			else
				sign[0] = -1;

			for(int m = 1; m < (1<<sz(p0)); m++)
			{
				ssum[m] = ssum[m - (m&-m)] + (1 << p0[getbit[m&-m]]);
				sign[m] = -1 * sign[m - (m&-m)];
			}

			// cerr << "qmask = " << qmask << '\n';

			for(int m = 0; m < (1<<sz(p0)); m++)
			{
				// cerr << m << " -> " << ssum[m] << '\n';
				res += uppersum[qmask | ssum[m]] * sign[m];
			}
		}
		else// if(sz(pq) <= 6)
		{
			vi ssum((1 << sz(pq)), 0);
			for(int m = 1; m < (1<<sz(pq)); m++)
				ssum[m] = ssum[m - (m&-m)] + (1 << pq[getbit[m&-m]]);

			for(int m = 0; m < (1<<sz(pq)); m++)
				res += A[onemask | ssum[m]];
		}

		// cerr << test << ' ' << mask << '\n';

		cout << res << '\n';
	}
}

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 212 KB Output is correct
6 Correct 1 ms 212 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 212 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 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 212 KB Output is correct
6 Correct 1 ms 212 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 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 739 ms 4856 KB Output is correct
12 Correct 620 ms 14756 KB Output is correct
13 Correct 698 ms 13888 KB Output is correct
14 Correct 713 ms 14032 KB Output is correct
15 Correct 623 ms 15052 KB Output is correct
16 Correct 752 ms 14172 KB Output is correct
17 Correct 723 ms 14232 KB Output is correct
18 Correct 494 ms 16044 KB Output is correct
19 Correct 722 ms 13060 KB Output is correct
20 Correct 708 ms 14644 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 212 KB Output is correct
6 Correct 1 ms 212 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 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 739 ms 4856 KB Output is correct
12 Correct 620 ms 14756 KB Output is correct
13 Correct 698 ms 13888 KB Output is correct
14 Correct 713 ms 14032 KB Output is correct
15 Correct 623 ms 15052 KB Output is correct
16 Correct 752 ms 14172 KB Output is correct
17 Correct 723 ms 14232 KB Output is correct
18 Correct 494 ms 16044 KB Output is correct
19 Correct 722 ms 13060 KB Output is correct
20 Correct 708 ms 14644 KB Output is correct
21 Correct 961 ms 18180 KB Output is correct
22 Correct 700 ms 18332 KB Output is correct
23 Correct 873 ms 17312 KB Output is correct
24 Correct 834 ms 17088 KB Output is correct
25 Correct 722 ms 19124 KB Output is correct
26 Correct 883 ms 17564 KB Output is correct
27 Correct 961 ms 17668 KB Output is correct
28 Correct 487 ms 20224 KB Output is correct
29 Correct 896 ms 16084 KB Output is correct
30 Correct 805 ms 18232 KB Output is correct
31 Correct 838 ms 18108 KB Output is correct
32 Correct 841 ms 18008 KB Output is correct
33 Correct 717 ms 16900 KB Output is correct
34 Correct 904 ms 17064 KB Output is correct
35 Correct 880 ms 17468 KB Output is correct
36 Correct 528 ms 16028 KB Output is correct
37 Correct 703 ms 18092 KB Output is correct
38 Correct 825 ms 16052 KB Output is correct
39 Correct 1018 ms 17252 KB Output is correct
40 Correct 913 ms 17184 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 212 KB Output is correct
6 Correct 1 ms 212 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 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 102 ms 16972 KB Output is correct
12 Correct 93 ms 17000 KB Output is correct
13 Correct 105 ms 16872 KB Output is correct
14 Correct 114 ms 16908 KB Output is correct
15 Correct 96 ms 16992 KB Output is correct
16 Correct 125 ms 16988 KB Output is correct
17 Correct 119 ms 16860 KB Output is correct
18 Correct 72 ms 17132 KB Output is correct
19 Correct 86 ms 16840 KB Output is correct
20 Correct 93 ms 17000 KB Output is correct
21 Correct 99 ms 16996 KB Output is correct
22 Correct 108 ms 16936 KB Output is correct
23 Correct 90 ms 16844 KB Output is correct
24 Correct 113 ms 16872 KB Output is correct
25 Correct 117 ms 16872 KB Output is correct
26 Correct 77 ms 16792 KB Output is correct
27 Correct 99 ms 16988 KB Output is correct
28 Correct 88 ms 16728 KB Output is correct
29 Correct 111 ms 17000 KB Output is correct
30 Correct 111 ms 16992 KB Output is correct
31 Correct 98 ms 16900 KB Output is correct
32 Correct 114 ms 16908 KB Output is correct
33 Correct 124 ms 16864 KB Output is correct
34 Correct 73 ms 16740 KB Output is correct
35 Correct 130 ms 16860 KB Output is correct
36 Correct 106 ms 16876 KB Output is correct
37 Correct 102 ms 16860 KB Output is correct
38 Correct 101 ms 16840 KB Output is correct
39 Correct 100 ms 16872 KB Output is correct
40 Correct 109 ms 16984 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 212 KB Output is correct
6 Correct 1 ms 212 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 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 739 ms 4856 KB Output is correct
12 Correct 620 ms 14756 KB Output is correct
13 Correct 698 ms 13888 KB Output is correct
14 Correct 713 ms 14032 KB Output is correct
15 Correct 623 ms 15052 KB Output is correct
16 Correct 752 ms 14172 KB Output is correct
17 Correct 723 ms 14232 KB Output is correct
18 Correct 494 ms 16044 KB Output is correct
19 Correct 722 ms 13060 KB Output is correct
20 Correct 708 ms 14644 KB Output is correct
21 Correct 961 ms 18180 KB Output is correct
22 Correct 700 ms 18332 KB Output is correct
23 Correct 873 ms 17312 KB Output is correct
24 Correct 834 ms 17088 KB Output is correct
25 Correct 722 ms 19124 KB Output is correct
26 Correct 883 ms 17564 KB Output is correct
27 Correct 961 ms 17668 KB Output is correct
28 Correct 487 ms 20224 KB Output is correct
29 Correct 896 ms 16084 KB Output is correct
30 Correct 805 ms 18232 KB Output is correct
31 Correct 838 ms 18108 KB Output is correct
32 Correct 841 ms 18008 KB Output is correct
33 Correct 717 ms 16900 KB Output is correct
34 Correct 904 ms 17064 KB Output is correct
35 Correct 880 ms 17468 KB Output is correct
36 Correct 528 ms 16028 KB Output is correct
37 Correct 703 ms 18092 KB Output is correct
38 Correct 825 ms 16052 KB Output is correct
39 Correct 1018 ms 17252 KB Output is correct
40 Correct 913 ms 17184 KB Output is correct
41 Correct 102 ms 16972 KB Output is correct
42 Correct 93 ms 17000 KB Output is correct
43 Correct 105 ms 16872 KB Output is correct
44 Correct 114 ms 16908 KB Output is correct
45 Correct 96 ms 16992 KB Output is correct
46 Correct 125 ms 16988 KB Output is correct
47 Correct 119 ms 16860 KB Output is correct
48 Correct 72 ms 17132 KB Output is correct
49 Correct 86 ms 16840 KB Output is correct
50 Correct 93 ms 17000 KB Output is correct
51 Correct 99 ms 16996 KB Output is correct
52 Correct 108 ms 16936 KB Output is correct
53 Correct 90 ms 16844 KB Output is correct
54 Correct 113 ms 16872 KB Output is correct
55 Correct 117 ms 16872 KB Output is correct
56 Correct 77 ms 16792 KB Output is correct
57 Correct 99 ms 16988 KB Output is correct
58 Correct 88 ms 16728 KB Output is correct
59 Correct 111 ms 17000 KB Output is correct
60 Correct 111 ms 16992 KB Output is correct
61 Correct 98 ms 16900 KB Output is correct
62 Correct 114 ms 16908 KB Output is correct
63 Correct 124 ms 16864 KB Output is correct
64 Correct 73 ms 16740 KB Output is correct
65 Correct 130 ms 16860 KB Output is correct
66 Correct 106 ms 16876 KB Output is correct
67 Correct 102 ms 16860 KB Output is correct
68 Correct 101 ms 16840 KB Output is correct
69 Correct 100 ms 16872 KB Output is correct
70 Correct 109 ms 16984 KB Output is correct
71 Correct 1065 ms 43280 KB Output is correct
72 Correct 1034 ms 43388 KB Output is correct
73 Correct 1395 ms 41980 KB Output is correct
74 Correct 1539 ms 42392 KB Output is correct
75 Correct 1072 ms 44300 KB Output is correct
76 Correct 1587 ms 42532 KB Output is correct
77 Correct 1499 ms 42436 KB Output is correct
78 Correct 679 ms 46212 KB Output is correct
79 Correct 973 ms 40280 KB Output is correct
80 Correct 1043 ms 43528 KB Output is correct
81 Correct 1337 ms 43236 KB Output is correct
82 Correct 1562 ms 42268 KB Output is correct
83 Correct 1123 ms 41372 KB Output is correct
84 Correct 1551 ms 42292 KB Output is correct
85 Correct 1499 ms 42492 KB Output is correct
86 Correct 652 ms 40268 KB Output is correct
87 Correct 1063 ms 43376 KB Output is correct
88 Correct 1014 ms 40236 KB Output is correct
89 Correct 1288 ms 41900 KB Output is correct
90 Correct 1381 ms 42188 KB Output is correct
91 Correct 1106 ms 41404 KB Output is correct
92 Correct 1472 ms 42564 KB Output is correct
93 Correct 1525 ms 42460 KB Output is correct
94 Correct 667 ms 40268 KB Output is correct
95 Correct 1316 ms 42328 KB Output is correct
96 Correct 1296 ms 42348 KB Output is correct
97 Correct 1311 ms 42556 KB Output is correct
98 Correct 1279 ms 42296 KB Output is correct
99 Correct 1305 ms 42332 KB Output is correct
100 Correct 1330 ms 42376 KB Output is correct