oj.uz

Submission #41154

# Submission time Handle Problem Language Result Execution time Memory
41154 2018-02-13T06:53:12 Z aome Snake Escaping (JOI18_snake_escaping) C++14
75 / 100
 2000 ms 35088 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 1000005;
const int M = 1594323;

int n, q;
int to3[1 << 13];
int mask2[2][N]; // 0 check and, 1 check or
int mask3[N];
int res[N];
int pw3[12], f[M], g[M];
string a;

void prepare() {
	for (int i = 0; i < (1 << 13); ++i) {
		for (int j = 12; j >= 0; --j) {
			to3[i] *= 3;
			if (i >> j & 1) to3[i]++;
		}
	}
	pw3[0] = 1; 
	for (int i = 1; i < 13; ++i) pw3[i] = 3 * pw3[i - 1];
	for (int i = 0; i < M; ++i) {
		int cur = i;
		g[i] = -1;
		for (int j = 0; j < 13; ++j) {
			if (cur % 3 == 2) g[i] = j;
			cur /= 3;
		}
	}
}

void calc() {
	for (int i = 0; i < M; ++i) {
		if (g[i] != -1) {
			f[i] += f[i - 2 * pw3[g[i]]];
			f[i] += f[i - 1 * pw3[g[i]]];
		}
	}
}

inline bool check(int mask, int i) {
	return (mask & mask2[0][i]) == mask2[0][i] && (mask | mask2[1][i]) == mask2[1][i];
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> q >> a; 
	for (int i = 0; i < q; ++i) {
		string s; cin >> s;
		for (int j = max(0, n - 7); j < n; ++j) { // first 7 bits
			mask2[0][i] <<= 1, mask2[1][i] <<= 1;
			if (s[j] == '1') mask2[0][i]++;
			if (s[j] == '?' || s[j] == '1') mask2[1][i]++;
		}
		for (int j = 0; j < max(0, n - 7); ++j) { // last 13 bits
			mask3[i] *= 3;
			if (s[j] == '1') mask3[i]++;
			if (s[j] == '?') mask3[i] += 2;
		}
	}
	prepare();
	for (int i = 0; i < 128; ++i) { // first 7 bits
		memset(f, 0, sizeof f);
		for (int j = 0; j < (1 << n); ++j) {
			if ((j & 127) != i) continue;
			f[to3[j >> 7]] += a[j] - '0';
		}
		calc();
		for (int j = 0; j < q; ++j) {
			if (!check(i, j)) continue;
			res[j] += f[mask3[j]];
		}
	}
	for (int i = 0; i < q; ++i) printf("%d\n", res[i]);
}

Compilation message

snake_escaping.cpp: In function 'void prepare()':
snake_escaping.cpp:24:54: warning: iteration 11u invokes undefined behavior [-Waggressive-loop-optimizations]
  for (int i = 1; i < 13; ++i) pw3[i] = 3 * pw3[i - 1];
                                                      ^
snake_escaping.cpp:24:20: note: containing loop
  for (int i = 1; i < 13; ++i) pw3[i] = 3 * pw3[i - 1];
                    ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 689 ms 12916 KB Output is correct
2 Correct 606 ms 13152 KB Output is correct
3 Correct 622 ms 13152 KB Output is correct
4 Correct 647 ms 13152 KB Output is correct
5 Correct 641 ms 13152 KB Output is correct
6 Correct 639 ms 13152 KB Output is correct
7 Correct 614 ms 13168 KB Output is correct
8 Correct 651 ms 13236 KB Output is correct
9 Correct 609 ms 13236 KB Output is correct
10 Correct 629 ms 13280 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 689 ms 12916 KB Output is correct
2 Correct 606 ms 13152 KB Output is correct
3 Correct 622 ms 13152 KB Output is correct
4 Correct 647 ms 13152 KB Output is correct
5 Correct 641 ms 13152 KB Output is correct
6 Correct 639 ms 13152 KB Output is correct
7 Correct 614 ms 13168 KB Output is correct
8 Correct 651 ms 13236 KB Output is correct
9 Correct 609 ms 13236 KB Output is correct
10 Correct 629 ms 13280 KB Output is correct
11 Correct 1259 ms 32860 KB Output is correct
12 Correct 1392 ms 32860 KB Output is correct
13 Correct 1665 ms 32860 KB Output is correct
14 Correct 1533 ms 32860 KB Output is correct
15 Correct 1977 ms 32860 KB Output is correct
16 Correct 1603 ms 32860 KB Output is correct
17 Correct 1646 ms 32860 KB Output is correct
18 Correct 1070 ms 33784 KB Output is correct
19 Correct 1335 ms 33784 KB Output is correct
20 Correct 1337 ms 33784 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 689 ms 12916 KB Output is correct
2 Correct 606 ms 13152 KB Output is correct
3 Correct 622 ms 13152 KB Output is correct
4 Correct 647 ms 13152 KB Output is correct
5 Correct 641 ms 13152 KB Output is correct
6 Correct 639 ms 13152 KB Output is correct
7 Correct 614 ms 13168 KB Output is correct
8 Correct 651 ms 13236 KB Output is correct
9 Correct 609 ms 13236 KB Output is correct
10 Correct 629 ms 13280 KB Output is correct
11 Correct 1259 ms 32860 KB Output is correct
12 Correct 1392 ms 32860 KB Output is correct
13 Correct 1665 ms 32860 KB Output is correct
14 Correct 1533 ms 32860 KB Output is correct
15 Correct 1977 ms 32860 KB Output is correct
16 Correct 1603 ms 32860 KB Output is correct
17 Correct 1646 ms 32860 KB Output is correct
18 Correct 1070 ms 33784 KB Output is correct
19 Correct 1335 ms 33784 KB Output is correct
20 Correct 1337 ms 33784 KB Output is correct
21 Correct 1329 ms 33784 KB Output is correct
22 Correct 1411 ms 33784 KB Output is correct
23 Correct 1727 ms 33784 KB Output is correct
24 Correct 1571 ms 33784 KB Output is correct
25 Correct 1879 ms 33784 KB Output is correct
26 Correct 1609 ms 33784 KB Output is correct
27 Correct 1681 ms 33784 KB Output is correct
28 Correct 1098 ms 34636 KB Output is correct
29 Correct 1261 ms 34636 KB Output is correct
30 Correct 1301 ms 34636 KB Output is correct
31 Correct 1775 ms 34636 KB Output is correct
32 Correct 1618 ms 34636 KB Output is correct
33 Correct 1424 ms 34636 KB Output is correct
34 Correct 1602 ms 34636 KB Output is correct
35 Correct 1761 ms 34636 KB Output is correct
36 Correct 964 ms 34636 KB Output is correct
37 Correct 1359 ms 34636 KB Output is correct
38 Correct 1477 ms 34636 KB Output is correct
39 Correct 1521 ms 34636 KB Output is correct
40 Correct 1589 ms 34636 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 689 ms 12916 KB Output is correct
2 Correct 606 ms 13152 KB Output is correct
3 Correct 622 ms 13152 KB Output is correct
4 Correct 647 ms 13152 KB Output is correct
5 Correct 641 ms 13152 KB Output is correct
6 Correct 639 ms 13152 KB Output is correct
7 Correct 614 ms 13168 KB Output is correct
8 Correct 651 ms 13236 KB Output is correct
9 Correct 609 ms 13236 KB Output is correct
10 Correct 629 ms 13280 KB Output is correct
11 Correct 813 ms 34636 KB Output is correct
12 Correct 822 ms 34636 KB Output is correct
13 Correct 829 ms 34636 KB Output is correct
14 Correct 857 ms 34636 KB Output is correct
15 Correct 856 ms 34636 KB Output is correct
16 Correct 829 ms 34636 KB Output is correct
17 Correct 817 ms 34636 KB Output is correct
18 Correct 764 ms 34636 KB Output is correct
19 Correct 767 ms 34636 KB Output is correct
20 Correct 774 ms 34636 KB Output is correct
21 Correct 837 ms 34636 KB Output is correct
22 Correct 808 ms 34636 KB Output is correct
23 Correct 831 ms 34636 KB Output is correct
24 Correct 776 ms 34636 KB Output is correct
25 Correct 778 ms 34636 KB Output is correct
26 Correct 831 ms 34636 KB Output is correct
27 Correct 803 ms 34636 KB Output is correct
28 Correct 822 ms 34636 KB Output is correct
29 Correct 808 ms 34636 KB Output is correct
30 Correct 804 ms 34636 KB Output is correct
31 Correct 835 ms 34636 KB Output is correct
32 Correct 824 ms 34636 KB Output is correct
33 Correct 858 ms 34636 KB Output is correct
34 Correct 817 ms 34636 KB Output is correct
35 Correct 829 ms 34636 KB Output is correct
36 Correct 890 ms 34636 KB Output is correct
37 Correct 833 ms 34636 KB Output is correct
38 Correct 842 ms 34636 KB Output is correct
39 Correct 833 ms 34636 KB Output is correct
40 Correct 873 ms 34636 KB Output is correct

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 689 ms 12916 KB Output is correct
2 Correct 606 ms 13152 KB Output is correct
3 Correct 622 ms 13152 KB Output is correct
4 Correct 647 ms 13152 KB Output is correct
5 Correct 641 ms 13152 KB Output is correct
6 Correct 639 ms 13152 KB Output is correct
7 Correct 614 ms 13168 KB Output is correct
8 Correct 651 ms 13236 KB Output is correct
9 Correct 609 ms 13236 KB Output is correct
10 Correct 629 ms 13280 KB Output is correct
11 Correct 1259 ms 32860 KB Output is correct
12 Correct 1392 ms 32860 KB Output is correct
13 Correct 1665 ms 32860 KB Output is correct
14 Correct 1533 ms 32860 KB Output is correct
15 Correct 1977 ms 32860 KB Output is correct
16 Correct 1603 ms 32860 KB Output is correct
17 Correct 1646 ms 32860 KB Output is correct
18 Correct 1070 ms 33784 KB Output is correct
19 Correct 1335 ms 33784 KB Output is correct
20 Correct 1337 ms 33784 KB Output is correct
21 Correct 1329 ms 33784 KB Output is correct
22 Correct 1411 ms 33784 KB Output is correct
23 Correct 1727 ms 33784 KB Output is correct
24 Correct 1571 ms 33784 KB Output is correct
25 Correct 1879 ms 33784 KB Output is correct
26 Correct 1609 ms 33784 KB Output is correct
27 Correct 1681 ms 33784 KB Output is correct
28 Correct 1098 ms 34636 KB Output is correct
29 Correct 1261 ms 34636 KB Output is correct
30 Correct 1301 ms 34636 KB Output is correct
31 Correct 1775 ms 34636 KB Output is correct
32 Correct 1618 ms 34636 KB Output is correct
33 Correct 1424 ms 34636 KB Output is correct
34 Correct 1602 ms 34636 KB Output is correct
35 Correct 1761 ms 34636 KB Output is correct
36 Correct 964 ms 34636 KB Output is correct
37 Correct 1359 ms 34636 KB Output is correct
38 Correct 1477 ms 34636 KB Output is correct
39 Correct 1521 ms 34636 KB Output is correct
40 Correct 1589 ms 34636 KB Output is correct
41 Correct 813 ms 34636 KB Output is correct
42 Correct 822 ms 34636 KB Output is correct
43 Correct 829 ms 34636 KB Output is correct
44 Correct 857 ms 34636 KB Output is correct
45 Correct 856 ms 34636 KB Output is correct
46 Correct 829 ms 34636 KB Output is correct
47 Correct 817 ms 34636 KB Output is correct
48 Correct 764 ms 34636 KB Output is correct
49 Correct 767 ms 34636 KB Output is correct
50 Correct 774 ms 34636 KB Output is correct
51 Correct 837 ms 34636 KB Output is correct
52 Correct 808 ms 34636 KB Output is correct
53 Correct 831 ms 34636 KB Output is correct
54 Correct 776 ms 34636 KB Output is correct
55 Correct 778 ms 34636 KB Output is correct
56 Correct 831 ms 34636 KB Output is correct
57 Correct 803 ms 34636 KB Output is correct
58 Correct 822 ms 34636 KB Output is correct
59 Correct 808 ms 34636 KB Output is correct
60 Correct 804 ms 34636 KB Output is correct
61 Correct 835 ms 34636 KB Output is correct
62 Correct 824 ms 34636 KB Output is correct
63 Correct 858 ms 34636 KB Output is correct
64 Correct 817 ms 34636 KB Output is correct
65 Correct 829 ms 34636 KB Output is correct
66 Correct 890 ms 34636 KB Output is correct
67 Correct 833 ms 34636 KB Output is correct
68 Correct 842 ms 34636 KB Output is correct
69 Correct 833 ms 34636 KB Output is correct
70 Correct 873 ms 34636 KB Output is correct
71 Correct 1685 ms 35088 KB Output is correct
72 Correct 1901 ms 35088 KB Output is correct
73 Execution timed out 2041 ms 35088 KB Time limit exceeded
74 Halted 0 ms 0 KB -