답안 #68743 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
68743	2018-08-18T10:18:22 Z	tmwilliamlin168	Snake Escaping (JOI18_snake_escaping)	C++14	75 / 100	752 ms	66560 KB

snake_escaping

#include <bits/stdc++.h>
using namespace std;

const int mxL=20, mxQ=1e6;
int l, q, dp[2][1<<mxL];
string s;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> l >> q >> s;
	for(int j=0; j<2; ++j) {
		for(int i=0; i<1<<l; ++i)
			dp[j][i]=s[i]-'0';
		for(int k=0; k<l; ++k)
			for(int i=0; i<1<<l; ++i)
				if(i>>k&1^j)
					dp[j][i]+=dp[j][i^1<<k];
	}
	while(q--) {
		string t;
		cin >> t;
		int na=0, nb=0, nc=0, ma=0, mb=0, mc=0, ans=0;
		for(int i=0; i<l; ++i) {
			if(t[i]=='0') {
				++na;
				ma|=1<<(l-1-i);
			} else if(t[i]=='1') {
				++nb;
				mb|=1<<(l-1-i);
			} else {
				++nc;
				mc|=1<<(l-1-i);
			}
		}
		if(na<nc||nb<nc) {
			bool sw=0;
			if(nb>na) {
				swap(nb, na);
				swap(mb, ma);
				sw=1;
			}
			for(int i=mb; ; i=(i-1)&mb) {
				ans+=dp[sw][(sw?(1<<l)-1:0)^i^mb^mc]*(__builtin_popcount(i)&1?-1:1);
				if(!i)
					break;
			}
		} else {
			for(int i=mc; ; i=(i-1)&mc) {
				ans+=s[i|mb]-'0';
				if(!i)
					break;
			}
		}
		cout << ans << "\n";
	}
}

Compilation message

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:18:12: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
     if(i>>k&1^j)
        ~~~~^~

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	3 ms	496 KB	Output is correct
3	Correct	3 ms	608 KB	Output is correct
4	Correct	3 ms	608 KB	Output is correct
5	Correct	3 ms	608 KB	Output is correct
6	Correct	3 ms	680 KB	Output is correct
7	Correct	2 ms	680 KB	Output is correct
8	Correct	2 ms	680 KB	Output is correct
9	Correct	2 ms	688 KB	Output is correct
10	Correct	3 ms	700 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	3 ms	496 KB	Output is correct
3	Correct	3 ms	608 KB	Output is correct
4	Correct	3 ms	608 KB	Output is correct
5	Correct	3 ms	608 KB	Output is correct
6	Correct	3 ms	680 KB	Output is correct
7	Correct	2 ms	680 KB	Output is correct
8	Correct	2 ms	680 KB	Output is correct
9	Correct	2 ms	688 KB	Output is correct
10	Correct	3 ms	700 KB	Output is correct
11	Correct	344 ms	4936 KB	Output is correct
12	Correct	262 ms	4936 KB	Output is correct
13	Correct	276 ms	4936 KB	Output is correct
14	Correct	301 ms	4936 KB	Output is correct
15	Correct	303 ms	5412 KB	Output is correct
16	Correct	377 ms	5412 KB	Output is correct
17	Correct	365 ms	7388 KB	Output is correct
18	Correct	260 ms	9216 KB	Output is correct
19	Correct	318 ms	9216 KB	Output is correct
20	Correct	304 ms	9216 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	3 ms	496 KB	Output is correct
3	Correct	3 ms	608 KB	Output is correct
4	Correct	3 ms	608 KB	Output is correct
5	Correct	3 ms	608 KB	Output is correct
6	Correct	3 ms	680 KB	Output is correct
7	Correct	2 ms	680 KB	Output is correct
8	Correct	2 ms	680 KB	Output is correct
9	Correct	2 ms	688 KB	Output is correct
10	Correct	3 ms	700 KB	Output is correct
11	Correct	344 ms	4936 KB	Output is correct
12	Correct	262 ms	4936 KB	Output is correct
13	Correct	276 ms	4936 KB	Output is correct
14	Correct	301 ms	4936 KB	Output is correct
15	Correct	303 ms	5412 KB	Output is correct
16	Correct	377 ms	5412 KB	Output is correct
17	Correct	365 ms	7388 KB	Output is correct
18	Correct	260 ms	9216 KB	Output is correct
19	Correct	318 ms	9216 KB	Output is correct
20	Correct	304 ms	9216 KB	Output is correct
21	Correct	298 ms	9216 KB	Output is correct
22	Correct	305 ms	9216 KB	Output is correct
23	Correct	377 ms	9216 KB	Output is correct
24	Correct	356 ms	9216 KB	Output is correct
25	Correct	335 ms	9352 KB	Output is correct
26	Correct	370 ms	9352 KB	Output is correct
27	Correct	429 ms	9352 KB	Output is correct
28	Correct	253 ms	13916 KB	Output is correct
29	Correct	297 ms	13916 KB	Output is correct
30	Correct	337 ms	13916 KB	Output is correct
31	Correct	361 ms	13916 KB	Output is correct
32	Correct	493 ms	13916 KB	Output is correct
33	Correct	299 ms	13916 KB	Output is correct
34	Correct	329 ms	13916 KB	Output is correct
35	Correct	363 ms	13916 KB	Output is correct
36	Correct	207 ms	13952 KB	Output is correct
37	Correct	274 ms	16060 KB	Output is correct
38	Correct	304 ms	16060 KB	Output is correct
39	Correct	352 ms	16060 KB	Output is correct
40	Correct	348 ms	16060 KB	Output is correct

Subtask #4
53.0 / 53.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	3 ms	496 KB	Output is correct
3	Correct	3 ms	608 KB	Output is correct
4	Correct	3 ms	608 KB	Output is correct
5	Correct	3 ms	608 KB	Output is correct
6	Correct	3 ms	680 KB	Output is correct
7	Correct	2 ms	680 KB	Output is correct
8	Correct	2 ms	680 KB	Output is correct
9	Correct	2 ms	688 KB	Output is correct
10	Correct	3 ms	700 KB	Output is correct
11	Correct	124 ms	21732 KB	Output is correct
12	Correct	121 ms	21860 KB	Output is correct
13	Correct	124 ms	21860 KB	Output is correct
14	Correct	155 ms	21860 KB	Output is correct
15	Correct	108 ms	21860 KB	Output is correct
16	Correct	137 ms	21860 KB	Output is correct
17	Correct	134 ms	21860 KB	Output is correct
18	Correct	112 ms	21988 KB	Output is correct
19	Correct	109 ms	21988 KB	Output is correct
20	Correct	105 ms	21988 KB	Output is correct
21	Correct	120 ms	21988 KB	Output is correct
22	Correct	214 ms	23776 KB	Output is correct
23	Correct	110 ms	25860 KB	Output is correct
24	Correct	127 ms	27908 KB	Output is correct
25	Correct	158 ms	29940 KB	Output is correct
26	Correct	115 ms	30704 KB	Output is correct
27	Correct	121 ms	30852 KB	Output is correct
28	Correct	131 ms	30852 KB	Output is correct
29	Correct	129 ms	30852 KB	Output is correct
30	Correct	130 ms	30852 KB	Output is correct
31	Correct	124 ms	30852 KB	Output is correct
32	Correct	164 ms	30852 KB	Output is correct
33	Correct	146 ms	30852 KB	Output is correct
34	Correct	108 ms	30852 KB	Output is correct
35	Correct	128 ms	30852 KB	Output is correct
36	Correct	116 ms	30852 KB	Output is correct
37	Correct	120 ms	30852 KB	Output is correct
38	Correct	125 ms	30908 KB	Output is correct
39	Correct	141 ms	30908 KB	Output is correct
40	Correct	128 ms	30908 KB	Output is correct

Subtask #5
0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	3 ms	496 KB	Output is correct
3	Correct	3 ms	608 KB	Output is correct
4	Correct	3 ms	608 KB	Output is correct
5	Correct	3 ms	608 KB	Output is correct
6	Correct	3 ms	680 KB	Output is correct
7	Correct	2 ms	680 KB	Output is correct
8	Correct	2 ms	680 KB	Output is correct
9	Correct	2 ms	688 KB	Output is correct
10	Correct	3 ms	700 KB	Output is correct
11	Correct	344 ms	4936 KB	Output is correct
12	Correct	262 ms	4936 KB	Output is correct
13	Correct	276 ms	4936 KB	Output is correct
14	Correct	301 ms	4936 KB	Output is correct
15	Correct	303 ms	5412 KB	Output is correct
16	Correct	377 ms	5412 KB	Output is correct
17	Correct	365 ms	7388 KB	Output is correct
18	Correct	260 ms	9216 KB	Output is correct
19	Correct	318 ms	9216 KB	Output is correct
20	Correct	304 ms	9216 KB	Output is correct
21	Correct	298 ms	9216 KB	Output is correct
22	Correct	305 ms	9216 KB	Output is correct
23	Correct	377 ms	9216 KB	Output is correct
24	Correct	356 ms	9216 KB	Output is correct
25	Correct	335 ms	9352 KB	Output is correct
26	Correct	370 ms	9352 KB	Output is correct
27	Correct	429 ms	9352 KB	Output is correct
28	Correct	253 ms	13916 KB	Output is correct
29	Correct	297 ms	13916 KB	Output is correct
30	Correct	337 ms	13916 KB	Output is correct
31	Correct	361 ms	13916 KB	Output is correct
32	Correct	493 ms	13916 KB	Output is correct
33	Correct	299 ms	13916 KB	Output is correct
34	Correct	329 ms	13916 KB	Output is correct
35	Correct	363 ms	13916 KB	Output is correct
36	Correct	207 ms	13952 KB	Output is correct
37	Correct	274 ms	16060 KB	Output is correct
38	Correct	304 ms	16060 KB	Output is correct
39	Correct	352 ms	16060 KB	Output is correct
40	Correct	348 ms	16060 KB	Output is correct
41	Correct	124 ms	21732 KB	Output is correct
42	Correct	121 ms	21860 KB	Output is correct
43	Correct	124 ms	21860 KB	Output is correct
44	Correct	155 ms	21860 KB	Output is correct
45	Correct	108 ms	21860 KB	Output is correct
46	Correct	137 ms	21860 KB	Output is correct
47	Correct	134 ms	21860 KB	Output is correct
48	Correct	112 ms	21988 KB	Output is correct
49	Correct	109 ms	21988 KB	Output is correct
50	Correct	105 ms	21988 KB	Output is correct
51	Correct	120 ms	21988 KB	Output is correct
52	Correct	214 ms	23776 KB	Output is correct
53	Correct	110 ms	25860 KB	Output is correct
54	Correct	127 ms	27908 KB	Output is correct
55	Correct	158 ms	29940 KB	Output is correct
56	Correct	115 ms	30704 KB	Output is correct
57	Correct	121 ms	30852 KB	Output is correct
58	Correct	131 ms	30852 KB	Output is correct
59	Correct	129 ms	30852 KB	Output is correct
60	Correct	130 ms	30852 KB	Output is correct
61	Correct	124 ms	30852 KB	Output is correct
62	Correct	164 ms	30852 KB	Output is correct
63	Correct	146 ms	30852 KB	Output is correct
64	Correct	108 ms	30852 KB	Output is correct
65	Correct	128 ms	30852 KB	Output is correct
66	Correct	116 ms	30852 KB	Output is correct
67	Correct	120 ms	30852 KB	Output is correct
68	Correct	125 ms	30908 KB	Output is correct
69	Correct	141 ms	30908 KB	Output is correct
70	Correct	128 ms	30908 KB	Output is correct
71	Correct	669 ms	35516 KB	Output is correct
72	Correct	752 ms	57276 KB	Output is correct
73	Runtime error	750 ms	66560 KB	Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
74	Halted	0 ms	0 KB	-

답안 #68743

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