답안 #68740

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
68740 2018-08-18T10:16:36 Z tmwilliamlin168 Snake Escaping (JOI18_snake_escaping) C++14
22 / 100
443 ms 66560 KB
#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)
        ~~~~^~
# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 424 KB Output is correct
2 Correct 3 ms 600 KB Output is correct
3 Correct 2 ms 600 KB Output is correct
4 Correct 3 ms 600 KB Output is correct
5 Correct 2 ms 600 KB Output is correct
6 Correct 2 ms 632 KB Output is correct
7 Correct 2 ms 644 KB Output is correct
8 Correct 3 ms 656 KB Output is correct
9 Correct 2 ms 712 KB Output is correct
10 Correct 4 ms 724 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 424 KB Output is correct
2 Correct 3 ms 600 KB Output is correct
3 Correct 2 ms 600 KB Output is correct
4 Correct 3 ms 600 KB Output is correct
5 Correct 2 ms 600 KB Output is correct
6 Correct 2 ms 632 KB Output is correct
7 Correct 2 ms 644 KB Output is correct
8 Correct 3 ms 656 KB Output is correct
9 Correct 2 ms 712 KB Output is correct
10 Correct 4 ms 724 KB Output is correct
11 Correct 242 ms 15328 KB Output is correct
12 Correct 241 ms 17896 KB Output is correct
13 Correct 314 ms 17896 KB Output is correct
14 Correct 296 ms 18480 KB Output is correct
15 Correct 279 ms 19552 KB Output is correct
16 Correct 292 ms 19552 KB Output is correct
17 Correct 409 ms 23280 KB Output is correct
18 Correct 298 ms 25040 KB Output is correct
19 Correct 215 ms 25040 KB Output is correct
20 Correct 247 ms 25040 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 424 KB Output is correct
2 Correct 3 ms 600 KB Output is correct
3 Correct 2 ms 600 KB Output is correct
4 Correct 3 ms 600 KB Output is correct
5 Correct 2 ms 600 KB Output is correct
6 Correct 2 ms 632 KB Output is correct
7 Correct 2 ms 644 KB Output is correct
8 Correct 3 ms 656 KB Output is correct
9 Correct 2 ms 712 KB Output is correct
10 Correct 4 ms 724 KB Output is correct
11 Correct 242 ms 15328 KB Output is correct
12 Correct 241 ms 17896 KB Output is correct
13 Correct 314 ms 17896 KB Output is correct
14 Correct 296 ms 18480 KB Output is correct
15 Correct 279 ms 19552 KB Output is correct
16 Correct 292 ms 19552 KB Output is correct
17 Correct 409 ms 23280 KB Output is correct
18 Correct 298 ms 25040 KB Output is correct
19 Correct 215 ms 25040 KB Output is correct
20 Correct 247 ms 25040 KB Output is correct
21 Correct 267 ms 25040 KB Output is correct
22 Correct 308 ms 25040 KB Output is correct
23 Correct 308 ms 25040 KB Output is correct
24 Correct 319 ms 25040 KB Output is correct
25 Correct 314 ms 25064 KB Output is correct
26 Correct 443 ms 25064 KB Output is correct
27 Correct 376 ms 25064 KB Output is correct
28 Correct 208 ms 27612 KB Output is correct
29 Correct 255 ms 27612 KB Output is correct
30 Correct 315 ms 27612 KB Output is correct
31 Correct 365 ms 27612 KB Output is correct
32 Correct 395 ms 27612 KB Output is correct
33 Correct 300 ms 27612 KB Output is correct
34 Correct 351 ms 27612 KB Output is correct
35 Correct 379 ms 27612 KB Output is correct
36 Correct 214 ms 27612 KB Output is correct
37 Correct 300 ms 27612 KB Output is correct
38 Correct 310 ms 27612 KB Output is correct
39 Correct 305 ms 27612 KB Output is correct
40 Correct 310 ms 39720 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 424 KB Output is correct
2 Correct 3 ms 600 KB Output is correct
3 Correct 2 ms 600 KB Output is correct
4 Correct 3 ms 600 KB Output is correct
5 Correct 2 ms 600 KB Output is correct
6 Correct 2 ms 632 KB Output is correct
7 Correct 2 ms 644 KB Output is correct
8 Correct 3 ms 656 KB Output is correct
9 Correct 2 ms 712 KB Output is correct
10 Correct 4 ms 724 KB Output is correct
11 Correct 122 ms 46260 KB Output is correct
12 Correct 116 ms 48368 KB Output is correct
13 Correct 134 ms 50360 KB Output is correct
14 Correct 181 ms 52444 KB Output is correct
15 Correct 119 ms 54584 KB Output is correct
16 Correct 175 ms 56516 KB Output is correct
17 Correct 129 ms 58608 KB Output is correct
18 Correct 105 ms 60876 KB Output is correct
19 Correct 118 ms 62680 KB Output is correct
20 Correct 124 ms 64872 KB Output is correct
21 Runtime error 140 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.
22 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 424 KB Output is correct
2 Correct 3 ms 600 KB Output is correct
3 Correct 2 ms 600 KB Output is correct
4 Correct 3 ms 600 KB Output is correct
5 Correct 2 ms 600 KB Output is correct
6 Correct 2 ms 632 KB Output is correct
7 Correct 2 ms 644 KB Output is correct
8 Correct 3 ms 656 KB Output is correct
9 Correct 2 ms 712 KB Output is correct
10 Correct 4 ms 724 KB Output is correct
11 Correct 242 ms 15328 KB Output is correct
12 Correct 241 ms 17896 KB Output is correct
13 Correct 314 ms 17896 KB Output is correct
14 Correct 296 ms 18480 KB Output is correct
15 Correct 279 ms 19552 KB Output is correct
16 Correct 292 ms 19552 KB Output is correct
17 Correct 409 ms 23280 KB Output is correct
18 Correct 298 ms 25040 KB Output is correct
19 Correct 215 ms 25040 KB Output is correct
20 Correct 247 ms 25040 KB Output is correct
21 Correct 267 ms 25040 KB Output is correct
22 Correct 308 ms 25040 KB Output is correct
23 Correct 308 ms 25040 KB Output is correct
24 Correct 319 ms 25040 KB Output is correct
25 Correct 314 ms 25064 KB Output is correct
26 Correct 443 ms 25064 KB Output is correct
27 Correct 376 ms 25064 KB Output is correct
28 Correct 208 ms 27612 KB Output is correct
29 Correct 255 ms 27612 KB Output is correct
30 Correct 315 ms 27612 KB Output is correct
31 Correct 365 ms 27612 KB Output is correct
32 Correct 395 ms 27612 KB Output is correct
33 Correct 300 ms 27612 KB Output is correct
34 Correct 351 ms 27612 KB Output is correct
35 Correct 379 ms 27612 KB Output is correct
36 Correct 214 ms 27612 KB Output is correct
37 Correct 300 ms 27612 KB Output is correct
38 Correct 310 ms 27612 KB Output is correct
39 Correct 305 ms 27612 KB Output is correct
40 Correct 310 ms 39720 KB Output is correct
41 Correct 122 ms 46260 KB Output is correct
42 Correct 116 ms 48368 KB Output is correct
43 Correct 134 ms 50360 KB Output is correct
44 Correct 181 ms 52444 KB Output is correct
45 Correct 119 ms 54584 KB Output is correct
46 Correct 175 ms 56516 KB Output is correct
47 Correct 129 ms 58608 KB Output is correct
48 Correct 105 ms 60876 KB Output is correct
49 Correct 118 ms 62680 KB Output is correct
50 Correct 124 ms 64872 KB Output is correct
51 Runtime error 140 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.
52 Halted 0 ms 0 KB -