답안 #330277

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
330277	2020-11-24T11:50:03 Z	Kevin_Zhang_TW	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	1934 ms	14188 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	492 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	492 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	333 ms	5100 KB	Output is correct
12	Correct	301 ms	5228 KB	Output is correct
13	Correct	270 ms	4460 KB	Output is correct
14	Correct	261 ms	4460 KB	Output is correct
15	Correct	342 ms	5356 KB	Output is correct
16	Correct	269 ms	4588 KB	Output is correct
17	Correct	286 ms	4588 KB	Output is correct
18	Correct	1547 ms	6412 KB	Output is correct
19	Correct	246 ms	3436 KB	Output is correct
20	Correct	340 ms	5228 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	492 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	333 ms	5100 KB	Output is correct
12	Correct	301 ms	5228 KB	Output is correct
13	Correct	270 ms	4460 KB	Output is correct
14	Correct	261 ms	4460 KB	Output is correct
15	Correct	342 ms	5356 KB	Output is correct
16	Correct	269 ms	4588 KB	Output is correct
17	Correct	286 ms	4588 KB	Output is correct
18	Correct	1547 ms	6412 KB	Output is correct
19	Correct	246 ms	3436 KB	Output is correct
20	Correct	340 ms	5228 KB	Output is correct
21	Correct	445 ms	5996 KB	Output is correct
22	Correct	453 ms	6252 KB	Output is correct
23	Correct	280 ms	5356 KB	Output is correct
24	Correct	269 ms	5100 KB	Output is correct
25	Correct	588 ms	7020 KB	Output is correct
26	Correct	325 ms	5612 KB	Output is correct
27	Correct	333 ms	5484 KB	Output is correct
28	Correct	230 ms	7148 KB	Output is correct
29	Correct	258 ms	3436 KB	Output is correct
30	Correct	508 ms	5740 KB	Output is correct
31	Correct	353 ms	5356 KB	Output is correct
32	Correct	297 ms	5356 KB	Output is correct
33	Correct	276 ms	4332 KB	Output is correct
34	Correct	287 ms	4204 KB	Output is correct
35	Correct	339 ms	4588 KB	Output is correct
36	Correct	200 ms	3052 KB	Output is correct
37	Correct	311 ms	5100 KB	Output is correct
38	Correct	264 ms	3052 KB	Output is correct
39	Correct	297 ms	4332 KB	Output is correct
40	Correct	276 ms	4076 KB	Output is correct

Subtask #4
53.0 / 53.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	492 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	117 ms	6380 KB	Output is correct
12	Correct	64 ms	6380 KB	Output is correct
13	Correct	46 ms	6252 KB	Output is correct
14	Correct	54 ms	6252 KB	Output is correct
15	Correct	47 ms	6380 KB	Output is correct
16	Correct	61 ms	6380 KB	Output is correct
17	Correct	62 ms	6252 KB	Output is correct
18	Correct	39 ms	6508 KB	Output is correct
19	Correct	48 ms	6252 KB	Output is correct
20	Correct	110 ms	6380 KB	Output is correct
21	Correct	122 ms	6380 KB	Output is correct
22	Correct	57 ms	6252 KB	Output is correct
23	Correct	44 ms	6252 KB	Output is correct
24	Correct	49 ms	6252 KB	Output is correct
25	Correct	60 ms	6380 KB	Output is correct
26	Correct	37 ms	6252 KB	Output is correct
27	Correct	114 ms	6508 KB	Output is correct
28	Correct	43 ms	6232 KB	Output is correct
29	Correct	49 ms	6252 KB	Output is correct
30	Correct	49 ms	6252 KB	Output is correct
31	Correct	42 ms	6252 KB	Output is correct
32	Correct	65 ms	6252 KB	Output is correct
33	Correct	60 ms	6252 KB	Output is correct
34	Correct	37 ms	6124 KB	Output is correct
35	Correct	65 ms	6124 KB	Output is correct
36	Correct	67 ms	6124 KB	Output is correct
37	Correct	63 ms	6124 KB	Output is correct
38	Correct	65 ms	6252 KB	Output is correct
39	Correct	63 ms	6124 KB	Output is correct
40	Correct	62 ms	6252 KB	Output is correct

Subtask #5
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	492 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	333 ms	5100 KB	Output is correct
12	Correct	301 ms	5228 KB	Output is correct
13	Correct	270 ms	4460 KB	Output is correct
14	Correct	261 ms	4460 KB	Output is correct
15	Correct	342 ms	5356 KB	Output is correct
16	Correct	269 ms	4588 KB	Output is correct
17	Correct	286 ms	4588 KB	Output is correct
18	Correct	1547 ms	6412 KB	Output is correct
19	Correct	246 ms	3436 KB	Output is correct
20	Correct	340 ms	5228 KB	Output is correct
21	Correct	445 ms	5996 KB	Output is correct
22	Correct	453 ms	6252 KB	Output is correct
23	Correct	280 ms	5356 KB	Output is correct
24	Correct	269 ms	5100 KB	Output is correct
25	Correct	588 ms	7020 KB	Output is correct
26	Correct	325 ms	5612 KB	Output is correct
27	Correct	333 ms	5484 KB	Output is correct
28	Correct	230 ms	7148 KB	Output is correct
29	Correct	258 ms	3436 KB	Output is correct
30	Correct	508 ms	5740 KB	Output is correct
31	Correct	353 ms	5356 KB	Output is correct
32	Correct	297 ms	5356 KB	Output is correct
33	Correct	276 ms	4332 KB	Output is correct
34	Correct	287 ms	4204 KB	Output is correct
35	Correct	339 ms	4588 KB	Output is correct
36	Correct	200 ms	3052 KB	Output is correct
37	Correct	311 ms	5100 KB	Output is correct
38	Correct	264 ms	3052 KB	Output is correct
39	Correct	297 ms	4332 KB	Output is correct
40	Correct	276 ms	4076 KB	Output is correct
41	Correct	117 ms	6380 KB	Output is correct
42	Correct	64 ms	6380 KB	Output is correct
43	Correct	46 ms	6252 KB	Output is correct
44	Correct	54 ms	6252 KB	Output is correct
45	Correct	47 ms	6380 KB	Output is correct
46	Correct	61 ms	6380 KB	Output is correct
47	Correct	62 ms	6252 KB	Output is correct
48	Correct	39 ms	6508 KB	Output is correct
49	Correct	48 ms	6252 KB	Output is correct
50	Correct	110 ms	6380 KB	Output is correct
51	Correct	122 ms	6380 KB	Output is correct
52	Correct	57 ms	6252 KB	Output is correct
53	Correct	44 ms	6252 KB	Output is correct
54	Correct	49 ms	6252 KB	Output is correct
55	Correct	60 ms	6380 KB	Output is correct
56	Correct	37 ms	6252 KB	Output is correct
57	Correct	114 ms	6508 KB	Output is correct
58	Correct	43 ms	6232 KB	Output is correct
59	Correct	49 ms	6252 KB	Output is correct
60	Correct	49 ms	6252 KB	Output is correct
61	Correct	42 ms	6252 KB	Output is correct
62	Correct	65 ms	6252 KB	Output is correct
63	Correct	60 ms	6252 KB	Output is correct
64	Correct	37 ms	6124 KB	Output is correct
65	Correct	65 ms	6124 KB	Output is correct
66	Correct	67 ms	6124 KB	Output is correct
67	Correct	63 ms	6124 KB	Output is correct
68	Correct	65 ms	6252 KB	Output is correct
69	Correct	63 ms	6124 KB	Output is correct
70	Correct	62 ms	6252 KB	Output is correct
71	Correct	1848 ms	11072 KB	Output is correct
72	Correct	777 ms	11372 KB	Output is correct
73	Correct	429 ms	9964 KB	Output is correct
74	Correct	642 ms	10348 KB	Output is correct
75	Correct	435 ms	12268 KB	Output is correct
76	Correct	729 ms	10504 KB	Output is correct
77	Correct	703 ms	10348 KB	Output is correct
78	Correct	292 ms	14188 KB	Output is correct
79	Correct	390 ms	8084 KB	Output is correct
80	Correct	1627 ms	11244 KB	Output is correct
81	Correct	1934 ms	11204 KB	Output is correct
82	Correct	578 ms	9964 KB	Output is correct
83	Correct	375 ms	9324 KB	Output is correct
84	Correct	469 ms	10076 KB	Output is correct
85	Correct	709 ms	10220 KB	Output is correct
86	Correct	244 ms	8048 KB	Output is correct
87	Correct	1755 ms	11012 KB	Output is correct
88	Correct	382 ms	7916 KB	Output is correct
89	Correct	467 ms	9708 KB	Output is correct
90	Correct	469 ms	9964 KB	Output is correct
91	Correct	336 ms	9196 KB	Output is correct
92	Correct	747 ms	10348 KB	Output is correct
93	Correct	693 ms	10348 KB	Output is correct
94	Correct	266 ms	7788 KB	Output is correct
95	Correct	767 ms	10064 KB	Output is correct
96	Correct	770 ms	9952 KB	Output is correct
97	Correct	759 ms	9708 KB	Output is correct
98	Correct	785 ms	9716 KB	Output is correct
99	Correct	766 ms	9780 KB	Output is correct
100	Correct	753 ms	9708 KB	Output is correct

답안 #330277

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