답안 #330276

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
330276	2020-11-24T11:49:06 Z	Kevin_Zhang_TW	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	1781 ms	20108 KB

snake_escaping

#include <bits/stdc++.h>
//#pragma GCC optimize("Ofast")
#pragma GCC target("popcnt")
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T>
bool chmax(T &a, T b) { return a < b ? (a = b, true) : false; }
template<class T> 
bool chmin(T &a, T b) { return b < a ? (a = b, true) : false; }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U>
void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T>
void debug(T L, T R) { while (L != R) cerr << *L << " \n"[next(L) == R], ++L; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
 
const int MAX_N = 20;
int n, q;
char w[(1<<MAX_N) + 10], com[MAX_N << 1];
int dp[1<<MAX_N];
void init() {
	for (int i = 0;i < 1<<n;++i)
		dp[i] = w[i] - '0';
	for (int i = 0;i < n;++i)
		for (int s = 0;s < 1<<n;++s)
			if (s>>i&1)
				dp[s] += dp[s^(1<<i)];
}
int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n >> q >> w;
	init();
	for (int i = 0;i < q;++i) {
		cin >> com;
		int l = 0, r = (1<<n) - 1, sub = 0;
		reverse(com, com + n);
		for (int i = 0;i < n;++i) {
			if (com[i] == '0') r ^= 1<<i;
			if (com[i] == '1') l ^= 1<<i;
			if (com[i] == '?') sub |= 1<<i;
		} 
		int res = 0;
		if (__builtin_popcount(sub) <= 10) {
			for (int s = sub ; s ;(--s) &= sub) {
				res += w[l | s] - '0';
			}
			res += w[l] - '0';
		}
		else {
			int ls = __builtin_popcount(l);
			for (int s = l ; s ; (--s) &= l) {
				int x = ((__builtin_popcount(s)^ls)&1?-1:1) * dp[s | sub];
				res += x;
			} 
			res += (ls&1?-1:1) * dp[sub];
			DE(res);
		} 
		cout << abs(res) << '\n';
	}
}

Compilation message

snake_escaping.cpp: In function 'int32_t main()':
snake_escaping.cpp:20:17: warning: statement has no effect [-Wunused-value]
   20 | #define DE(...) 0
      |                 ^
snake_escaping.cpp:63:4: note: in expansion of macro 'DE'
   63 |    DE(res);
      |    ^~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	2 ms	364 KB	Output is correct
9	Correct	1 ms	364 KB	Output is correct
10	Correct	1 ms	364 KB	Output is correct
11	Correct	279 ms	15084 KB	Output is correct
12	Correct	284 ms	14444 KB	Output is correct
13	Correct	235 ms	13676 KB	Output is correct
14	Correct	234 ms	13804 KB	Output is correct
15	Correct	303 ms	14828 KB	Output is correct
16	Correct	262 ms	14060 KB	Output is correct
17	Correct	265 ms	13932 KB	Output is correct
18	Correct	1376 ms	15852 KB	Output is correct
19	Correct	236 ms	12908 KB	Output is correct
20	Correct	322 ms	14572 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	2 ms	364 KB	Output is correct
9	Correct	1 ms	364 KB	Output is correct
10	Correct	1 ms	364 KB	Output is correct
11	Correct	279 ms	15084 KB	Output is correct
12	Correct	284 ms	14444 KB	Output is correct
13	Correct	235 ms	13676 KB	Output is correct
14	Correct	234 ms	13804 KB	Output is correct
15	Correct	303 ms	14828 KB	Output is correct
16	Correct	262 ms	14060 KB	Output is correct
17	Correct	265 ms	13932 KB	Output is correct
18	Correct	1376 ms	15852 KB	Output is correct
19	Correct	236 ms	12908 KB	Output is correct
20	Correct	322 ms	14572 KB	Output is correct
21	Correct	424 ms	11884 KB	Output is correct
22	Correct	419 ms	12012 KB	Output is correct
23	Correct	267 ms	10988 KB	Output is correct
24	Correct	261 ms	10860 KB	Output is correct
25	Correct	540 ms	12908 KB	Output is correct
26	Correct	309 ms	11500 KB	Output is correct
27	Correct	315 ms	11244 KB	Output is correct
28	Correct	216 ms	20108 KB	Output is correct
29	Correct	257 ms	15852 KB	Output is correct
30	Correct	480 ms	18016 KB	Output is correct
31	Correct	325 ms	17900 KB	Output is correct
32	Correct	287 ms	17908 KB	Output is correct
33	Correct	269 ms	16748 KB	Output is correct
34	Correct	276 ms	17004 KB	Output is correct
35	Correct	317 ms	17516 KB	Output is correct
36	Correct	199 ms	15980 KB	Output is correct
37	Correct	298 ms	18028 KB	Output is correct
38	Correct	263 ms	16108 KB	Output is correct
39	Correct	292 ms	17132 KB	Output is correct
40	Correct	272 ms	16992 KB	Output is correct

Subtask #4
53.0 / 53.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	2 ms	364 KB	Output is correct
9	Correct	1 ms	364 KB	Output is correct
10	Correct	1 ms	364 KB	Output is correct
11	Correct	113 ms	7788 KB	Output is correct
12	Correct	61 ms	7916 KB	Output is correct
13	Correct	45 ms	7660 KB	Output is correct
14	Correct	52 ms	7660 KB	Output is correct
15	Correct	44 ms	7916 KB	Output is correct
16	Correct	60 ms	7788 KB	Output is correct
17	Correct	61 ms	7788 KB	Output is correct
18	Correct	40 ms	7916 KB	Output is correct
19	Correct	45 ms	7556 KB	Output is correct
20	Correct	90 ms	7788 KB	Output is correct
21	Correct	117 ms	7788 KB	Output is correct
22	Correct	53 ms	7660 KB	Output is correct
23	Correct	45 ms	7660 KB	Output is correct
24	Correct	49 ms	7660 KB	Output is correct
25	Correct	63 ms	7788 KB	Output is correct
26	Correct	37 ms	7660 KB	Output is correct
27	Correct	107 ms	7916 KB	Output is correct
28	Correct	44 ms	7788 KB	Output is correct
29	Correct	50 ms	7788 KB	Output is correct
30	Correct	48 ms	7660 KB	Output is correct
31	Correct	42 ms	7660 KB	Output is correct
32	Correct	61 ms	7788 KB	Output is correct
33	Correct	58 ms	7788 KB	Output is correct
34	Correct	37 ms	7660 KB	Output is correct
35	Correct	61 ms	7660 KB	Output is correct
36	Correct	60 ms	7788 KB	Output is correct
37	Correct	63 ms	7788 KB	Output is correct
38	Correct	62 ms	7788 KB	Output is correct
39	Correct	60 ms	7660 KB	Output is correct
40	Correct	61 ms	7788 KB	Output is correct

Subtask #5
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	2 ms	364 KB	Output is correct
9	Correct	1 ms	364 KB	Output is correct
10	Correct	1 ms	364 KB	Output is correct
11	Correct	279 ms	15084 KB	Output is correct
12	Correct	284 ms	14444 KB	Output is correct
13	Correct	235 ms	13676 KB	Output is correct
14	Correct	234 ms	13804 KB	Output is correct
15	Correct	303 ms	14828 KB	Output is correct
16	Correct	262 ms	14060 KB	Output is correct
17	Correct	265 ms	13932 KB	Output is correct
18	Correct	1376 ms	15852 KB	Output is correct
19	Correct	236 ms	12908 KB	Output is correct
20	Correct	322 ms	14572 KB	Output is correct
21	Correct	424 ms	11884 KB	Output is correct
22	Correct	419 ms	12012 KB	Output is correct
23	Correct	267 ms	10988 KB	Output is correct
24	Correct	261 ms	10860 KB	Output is correct
25	Correct	540 ms	12908 KB	Output is correct
26	Correct	309 ms	11500 KB	Output is correct
27	Correct	315 ms	11244 KB	Output is correct
28	Correct	216 ms	20108 KB	Output is correct
29	Correct	257 ms	15852 KB	Output is correct
30	Correct	480 ms	18016 KB	Output is correct
31	Correct	325 ms	17900 KB	Output is correct
32	Correct	287 ms	17908 KB	Output is correct
33	Correct	269 ms	16748 KB	Output is correct
34	Correct	276 ms	17004 KB	Output is correct
35	Correct	317 ms	17516 KB	Output is correct
36	Correct	199 ms	15980 KB	Output is correct
37	Correct	298 ms	18028 KB	Output is correct
38	Correct	263 ms	16108 KB	Output is correct
39	Correct	292 ms	17132 KB	Output is correct
40	Correct	272 ms	16992 KB	Output is correct
41	Correct	113 ms	7788 KB	Output is correct
42	Correct	61 ms	7916 KB	Output is correct
43	Correct	45 ms	7660 KB	Output is correct
44	Correct	52 ms	7660 KB	Output is correct
45	Correct	44 ms	7916 KB	Output is correct
46	Correct	60 ms	7788 KB	Output is correct
47	Correct	61 ms	7788 KB	Output is correct
48	Correct	40 ms	7916 KB	Output is correct
49	Correct	45 ms	7556 KB	Output is correct
50	Correct	90 ms	7788 KB	Output is correct
51	Correct	117 ms	7788 KB	Output is correct
52	Correct	53 ms	7660 KB	Output is correct
53	Correct	45 ms	7660 KB	Output is correct
54	Correct	49 ms	7660 KB	Output is correct
55	Correct	63 ms	7788 KB	Output is correct
56	Correct	37 ms	7660 KB	Output is correct
57	Correct	107 ms	7916 KB	Output is correct
58	Correct	44 ms	7788 KB	Output is correct
59	Correct	50 ms	7788 KB	Output is correct
60	Correct	48 ms	7660 KB	Output is correct
61	Correct	42 ms	7660 KB	Output is correct
62	Correct	61 ms	7788 KB	Output is correct
63	Correct	58 ms	7788 KB	Output is correct
64	Correct	37 ms	7660 KB	Output is correct
65	Correct	61 ms	7660 KB	Output is correct
66	Correct	60 ms	7788 KB	Output is correct
67	Correct	63 ms	7788 KB	Output is correct
68	Correct	62 ms	7788 KB	Output is correct
69	Correct	60 ms	7660 KB	Output is correct
70	Correct	61 ms	7788 KB	Output is correct
71	Correct	1681 ms	12012 KB	Output is correct
72	Correct	722 ms	12140 KB	Output is correct
73	Correct	420 ms	10732 KB	Output is correct
74	Correct	538 ms	10988 KB	Output is correct
75	Correct	370 ms	13292 KB	Output is correct
76	Correct	705 ms	11600 KB	Output is correct
77	Correct	658 ms	11372 KB	Output is correct
78	Correct	271 ms	15616 KB	Output is correct
79	Correct	359 ms	9452 KB	Output is correct
80	Correct	1250 ms	12564 KB	Output is correct
81	Correct	1781 ms	12532 KB	Output is correct
82	Correct	553 ms	11244 KB	Output is correct
83	Correct	361 ms	10348 KB	Output is correct
84	Correct	463 ms	11372 KB	Output is correct
85	Correct	663 ms	11576 KB	Output is correct
86	Correct	242 ms	9424 KB	Output is correct
87	Correct	1622 ms	12344 KB	Output is correct
88	Correct	358 ms	9196 KB	Output is correct
89	Correct	451 ms	10988 KB	Output is correct
90	Correct	453 ms	11388 KB	Output is correct
91	Correct	328 ms	10476 KB	Output is correct
92	Correct	695 ms	11628 KB	Output is correct
93	Correct	657 ms	11500 KB	Output is correct
94	Correct	249 ms	9220 KB	Output is correct
95	Correct	698 ms	11372 KB	Output is correct
96	Correct	737 ms	11004 KB	Output is correct
97	Correct	741 ms	12036 KB	Output is correct
98	Correct	749 ms	11904 KB	Output is correct
99	Correct	733 ms	11308 KB	Output is correct
100	Correct	737 ms	11328 KB	Output is correct

답안 #330276

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 25.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
25.0 / 25.0