답안 #41159 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
41159	2018-02-13T07:08:09 Z	aome	Snake Escaping (JOI18_snake_escaping)	C++14	75 / 100	2000 ms	34860 KB

snake_escaping

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 1 << 20;
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];
char a[N];
 
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]]];
		}
	}
} 

int main() {
	scanf("%d %d %s", &n, &q, &a);
	for (int i = 0; i < q; ++i) {
		char s[20]; scanf("%s", &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 << max(0, n - 7)); ++j) {
			f[to3[j]] += a[j << 7 | i] - '0';
		}
		calc();
		for (int j = 0; j < q; ++j) {
			if ((i & mask2[0][j]) == mask2[0][j] && (i | mask2[1][j]) == mask2[1][j]) res[j] += f[mask3[j]];
		}
	}
	for (int i = 0; i < q; ++i) printf("%d\n", res[i]);
}

Compilation message

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:45:30: warning: format '%s' expects argument of type 'char*', but argument 4 has type 'char (*)[1048576]' [-Wformat=]
  scanf("%d %d %s", &n, &q, &a);
                              ^
snake_escaping.cpp:47:29: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[20]' [-Wformat=]
   char s[20]; scanf("%s", &s);
                             ^
snake_escaping.cpp:45:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %s", &n, &q, &a);
                               ^
snake_escaping.cpp:47:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   char s[20]; scanf("%s", &s);
                              ^
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

#	결과	실행 시간	메모리	Grader output
1	Correct	675 ms	12920 KB	Output is correct
2	Correct	638 ms	12928 KB	Output is correct
3	Correct	640 ms	13096 KB	Output is correct
4	Correct	641 ms	13112 KB	Output is correct
5	Correct	632 ms	13112 KB	Output is correct
6	Correct	640 ms	13204 KB	Output is correct
7	Correct	632 ms	13220 KB	Output is correct
8	Correct	634 ms	13220 KB	Output is correct
9	Correct	631 ms	13220 KB	Output is correct
10	Correct	655 ms	13276 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	675 ms	12920 KB	Output is correct
2	Correct	638 ms	12928 KB	Output is correct
3	Correct	640 ms	13096 KB	Output is correct
4	Correct	641 ms	13112 KB	Output is correct
5	Correct	632 ms	13112 KB	Output is correct
6	Correct	640 ms	13204 KB	Output is correct
7	Correct	632 ms	13220 KB	Output is correct
8	Correct	634 ms	13220 KB	Output is correct
9	Correct	631 ms	13220 KB	Output is correct
10	Correct	655 ms	13276 KB	Output is correct
11	Correct	1290 ms	32632 KB	Output is correct
12	Correct	1403 ms	32632 KB	Output is correct
13	Correct	1755 ms	32632 KB	Output is correct
14	Correct	1661 ms	32632 KB	Output is correct
15	Correct	1949 ms	32796 KB	Output is correct
16	Correct	1668 ms	32796 KB	Output is correct
17	Correct	1718 ms	32796 KB	Output is correct
18	Correct	1216 ms	33836 KB	Output is correct
19	Correct	1298 ms	33836 KB	Output is correct
20	Correct	1389 ms	33836 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	675 ms	12920 KB	Output is correct
2	Correct	638 ms	12928 KB	Output is correct
3	Correct	640 ms	13096 KB	Output is correct
4	Correct	641 ms	13112 KB	Output is correct
5	Correct	632 ms	13112 KB	Output is correct
6	Correct	640 ms	13204 KB	Output is correct
7	Correct	632 ms	13220 KB	Output is correct
8	Correct	634 ms	13220 KB	Output is correct
9	Correct	631 ms	13220 KB	Output is correct
10	Correct	655 ms	13276 KB	Output is correct
11	Correct	1290 ms	32632 KB	Output is correct
12	Correct	1403 ms	32632 KB	Output is correct
13	Correct	1755 ms	32632 KB	Output is correct
14	Correct	1661 ms	32632 KB	Output is correct
15	Correct	1949 ms	32796 KB	Output is correct
16	Correct	1668 ms	32796 KB	Output is correct
17	Correct	1718 ms	32796 KB	Output is correct
18	Correct	1216 ms	33836 KB	Output is correct
19	Correct	1298 ms	33836 KB	Output is correct
20	Correct	1389 ms	33836 KB	Output is correct
21	Correct	1389 ms	33836 KB	Output is correct
22	Correct	1334 ms	33836 KB	Output is correct
23	Correct	1743 ms	33836 KB	Output is correct
24	Correct	1671 ms	33836 KB	Output is correct
25	Correct	1956 ms	33888 KB	Output is correct
26	Correct	1604 ms	33888 KB	Output is correct
27	Correct	1609 ms	33888 KB	Output is correct
28	Correct	1134 ms	34740 KB	Output is correct
29	Correct	1295 ms	34740 KB	Output is correct
30	Correct	1352 ms	34740 KB	Output is correct
31	Correct	1738 ms	34740 KB	Output is correct
32	Correct	1600 ms	34740 KB	Output is correct
33	Correct	1223 ms	34740 KB	Output is correct
34	Correct	1618 ms	34740 KB	Output is correct
35	Correct	1673 ms	34740 KB	Output is correct
36	Correct	963 ms	34740 KB	Output is correct
37	Correct	1363 ms	34740 KB	Output is correct
38	Correct	1402 ms	34740 KB	Output is correct
39	Correct	1434 ms	34740 KB	Output is correct
40	Correct	1511 ms	34740 KB	Output is correct

Subtask #4
53.0 / 53.0

#	결과	실행 시간	메모리	Grader output
1	Correct	675 ms	12920 KB	Output is correct
2	Correct	638 ms	12928 KB	Output is correct
3	Correct	640 ms	13096 KB	Output is correct
4	Correct	641 ms	13112 KB	Output is correct
5	Correct	632 ms	13112 KB	Output is correct
6	Correct	640 ms	13204 KB	Output is correct
7	Correct	632 ms	13220 KB	Output is correct
8	Correct	634 ms	13220 KB	Output is correct
9	Correct	631 ms	13220 KB	Output is correct
10	Correct	655 ms	13276 KB	Output is correct
11	Correct	669 ms	34740 KB	Output is correct
12	Correct	686 ms	34740 KB	Output is correct
13	Correct	679 ms	34740 KB	Output is correct
14	Correct	698 ms	34740 KB	Output is correct
15	Correct	689 ms	34740 KB	Output is correct
16	Correct	695 ms	34740 KB	Output is correct
17	Correct	730 ms	34740 KB	Output is correct
18	Correct	632 ms	34740 KB	Output is correct
19	Correct	659 ms	34740 KB	Output is correct
20	Correct	666 ms	34740 KB	Output is correct
21	Correct	694 ms	34740 KB	Output is correct
22	Correct	684 ms	34740 KB	Output is correct
23	Correct	648 ms	34740 KB	Output is correct
24	Correct	677 ms	34740 KB	Output is correct
25	Correct	677 ms	34740 KB	Output is correct
26	Correct	642 ms	34740 KB	Output is correct
27	Correct	670 ms	34740 KB	Output is correct
28	Correct	664 ms	34740 KB	Output is correct
29	Correct	673 ms	34740 KB	Output is correct
30	Correct	693 ms	34740 KB	Output is correct
31	Correct	704 ms	34740 KB	Output is correct
32	Correct	725 ms	34740 KB	Output is correct
33	Correct	739 ms	34740 KB	Output is correct
34	Correct	641 ms	34740 KB	Output is correct
35	Correct	703 ms	34740 KB	Output is correct
36	Correct	694 ms	34740 KB	Output is correct
37	Correct	798 ms	34740 KB	Output is correct
38	Correct	697 ms	34740 KB	Output is correct
39	Correct	702 ms	34740 KB	Output is correct
40	Correct	678 ms	34740 KB	Output is correct

Subtask #5
0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	675 ms	12920 KB	Output is correct
2	Correct	638 ms	12928 KB	Output is correct
3	Correct	640 ms	13096 KB	Output is correct
4	Correct	641 ms	13112 KB	Output is correct
5	Correct	632 ms	13112 KB	Output is correct
6	Correct	640 ms	13204 KB	Output is correct
7	Correct	632 ms	13220 KB	Output is correct
8	Correct	634 ms	13220 KB	Output is correct
9	Correct	631 ms	13220 KB	Output is correct
10	Correct	655 ms	13276 KB	Output is correct
11	Correct	1290 ms	32632 KB	Output is correct
12	Correct	1403 ms	32632 KB	Output is correct
13	Correct	1755 ms	32632 KB	Output is correct
14	Correct	1661 ms	32632 KB	Output is correct
15	Correct	1949 ms	32796 KB	Output is correct
16	Correct	1668 ms	32796 KB	Output is correct
17	Correct	1718 ms	32796 KB	Output is correct
18	Correct	1216 ms	33836 KB	Output is correct
19	Correct	1298 ms	33836 KB	Output is correct
20	Correct	1389 ms	33836 KB	Output is correct
21	Correct	1389 ms	33836 KB	Output is correct
22	Correct	1334 ms	33836 KB	Output is correct
23	Correct	1743 ms	33836 KB	Output is correct
24	Correct	1671 ms	33836 KB	Output is correct
25	Correct	1956 ms	33888 KB	Output is correct
26	Correct	1604 ms	33888 KB	Output is correct
27	Correct	1609 ms	33888 KB	Output is correct
28	Correct	1134 ms	34740 KB	Output is correct
29	Correct	1295 ms	34740 KB	Output is correct
30	Correct	1352 ms	34740 KB	Output is correct
31	Correct	1738 ms	34740 KB	Output is correct
32	Correct	1600 ms	34740 KB	Output is correct
33	Correct	1223 ms	34740 KB	Output is correct
34	Correct	1618 ms	34740 KB	Output is correct
35	Correct	1673 ms	34740 KB	Output is correct
36	Correct	963 ms	34740 KB	Output is correct
37	Correct	1363 ms	34740 KB	Output is correct
38	Correct	1402 ms	34740 KB	Output is correct
39	Correct	1434 ms	34740 KB	Output is correct
40	Correct	1511 ms	34740 KB	Output is correct
41	Correct	669 ms	34740 KB	Output is correct
42	Correct	686 ms	34740 KB	Output is correct
43	Correct	679 ms	34740 KB	Output is correct
44	Correct	698 ms	34740 KB	Output is correct
45	Correct	689 ms	34740 KB	Output is correct
46	Correct	695 ms	34740 KB	Output is correct
47	Correct	730 ms	34740 KB	Output is correct
48	Correct	632 ms	34740 KB	Output is correct
49	Correct	659 ms	34740 KB	Output is correct
50	Correct	666 ms	34740 KB	Output is correct
51	Correct	694 ms	34740 KB	Output is correct
52	Correct	684 ms	34740 KB	Output is correct
53	Correct	648 ms	34740 KB	Output is correct
54	Correct	677 ms	34740 KB	Output is correct
55	Correct	677 ms	34740 KB	Output is correct
56	Correct	642 ms	34740 KB	Output is correct
57	Correct	670 ms	34740 KB	Output is correct
58	Correct	664 ms	34740 KB	Output is correct
59	Correct	673 ms	34740 KB	Output is correct
60	Correct	693 ms	34740 KB	Output is correct
61	Correct	704 ms	34740 KB	Output is correct
62	Correct	725 ms	34740 KB	Output is correct
63	Correct	739 ms	34740 KB	Output is correct
64	Correct	641 ms	34740 KB	Output is correct
65	Correct	703 ms	34740 KB	Output is correct
66	Correct	694 ms	34740 KB	Output is correct
67	Correct	798 ms	34740 KB	Output is correct
68	Correct	697 ms	34740 KB	Output is correct
69	Correct	702 ms	34740 KB	Output is correct
70	Correct	678 ms	34740 KB	Output is correct
71	Correct	1529 ms	34768 KB	Output is correct
72	Correct	1535 ms	34860 KB	Output is correct
73	Correct	1860 ms	34860 KB	Output is correct
74	Correct	1842 ms	34860 KB	Output is correct
75	Execution timed out	2041 ms	34860 KB	Time limit exceeded
76	Halted	0 ms	0 KB	-

답안 #41159

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 7.0 / 7.0

Subtask #3 10.0 / 10.0

Subtask #4 53.0 / 53.0

Subtask #5 0 / 25.0

Subtask #1
5.0 / 5.0

Subtask #2
7.0 / 7.0

Subtask #3
10.0 / 10.0

Subtask #4
53.0 / 53.0

Subtask #5
0 / 25.0