답안 #771468

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
771468	2023-07-03T03:53:27 Z	vjudge1	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	1454 ms	39268 KB

snake_escaping

// #cheat_when_I_was_young
// #cheatkhitacontre #khionhatoicheat
// #thaycuckythatvong
#include "bits/stdc++.h"
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
const int N = 1<<20;
int n, q, dp[N], sup[N];
string s, t;
int backtrack1(int idx, int num) {
    if (idx == n) return s[num];
    if (t[idx] == '0') return backtrack1(idx+1, num);
    if (t[idx] == '1') return backtrack1(idx+1, num | (1<<idx));
    return backtrack1(idx+1, num) + backtrack1(idx+1, num | (1<<idx));
}
int backtrack2(int idx, int num, int change) {
    if (idx == n) {
        if (change % 2) return -dp[num];
        return dp[num];
    }
    if (t[idx] == '0') return backtrack2(idx+1, num, change);
    if (t[idx] == '?') return backtrack2(idx+1, num | (1<<idx), change);
    return backtrack2(idx+1, num, change+1) + backtrack2(idx+1, num | (1<<idx), change);
}
int backtrack3(int idx, int num, int change) {
    if (idx == n) {
        if (change % 2) return -sup[num];
        return sup[num];
    }
    if (t[idx] == '1') return backtrack3(idx+1, num | (1<<idx), change);
    if (t[idx] == '?') return backtrack3(idx+1, num, change);
    return backtrack3(idx+1, num, change) + backtrack3(idx+1, num | (1<<idx), change+1);
}
signed main() {
	IOS;
    cin >> n >> q >> s;
    for (int mask = 0; mask < 1<<n; ++mask) {
        s[mask] -= '0';
        dp[mask] = sup[mask] = s[mask];
    }
    for (int i = n-1; i >= 0; --i) for (int mask = 0; mask < 1<<n; ++mask) if (mask & (1<<i)) dp[mask] += dp[mask^(1<<i)];
    for (int i = n-1; i >= 0; --i) for (int mask = (1<<n)-1; mask >= 0; --mask) if (!(mask & (1<<i))) sup[mask] += sup[mask^(1<<i)];
    while (q--) {
        cin >> t;
        reverse(t.begin(), t.end());
        int cnt[] = {0, 0, 0};
        for (char &c: t) {
            if (c == '0') ++cnt[0];
            else if (c == '1') ++cnt[1];
            else ++cnt[2];
        }
        int mi = *min_element(cnt, cnt+3);
        if (cnt[2] == mi) cout << backtrack1(0, 0) << "\n";
        else if (cnt[1] == mi) cout << backtrack2(0, 0, 0) << "\n";
        else cout << backtrack3(0, 0, 0) << "\n";
    }
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	336 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	336 KB	Output is correct
11	Correct	192 ms	5052 KB	Output is correct
12	Correct	231 ms	4684 KB	Output is correct
13	Correct	309 ms	3996 KB	Output is correct
14	Correct	386 ms	4108 KB	Output is correct
15	Correct	261 ms	5024 KB	Output is correct
16	Correct	354 ms	4248 KB	Output is correct
17	Correct	333 ms	4260 KB	Output is correct
18	Correct	147 ms	6016 KB	Output is correct
19	Correct	184 ms	3056 KB	Output is correct
20	Correct	228 ms	4776 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	336 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	336 KB	Output is correct
11	Correct	192 ms	5052 KB	Output is correct
12	Correct	231 ms	4684 KB	Output is correct
13	Correct	309 ms	3996 KB	Output is correct
14	Correct	386 ms	4108 KB	Output is correct
15	Correct	261 ms	5024 KB	Output is correct
16	Correct	354 ms	4248 KB	Output is correct
17	Correct	333 ms	4260 KB	Output is correct
18	Correct	147 ms	6016 KB	Output is correct
19	Correct	184 ms	3056 KB	Output is correct
20	Correct	228 ms	4776 KB	Output is correct
21	Correct	254 ms	5184 KB	Output is correct
22	Correct	262 ms	5224 KB	Output is correct
23	Correct	430 ms	4256 KB	Output is correct
24	Correct	619 ms	4100 KB	Output is correct
25	Correct	306 ms	6164 KB	Output is correct
26	Correct	528 ms	4608 KB	Output is correct
27	Correct	471 ms	4564 KB	Output is correct
28	Correct	156 ms	7112 KB	Output is correct
29	Correct	244 ms	3148 KB	Output is correct
30	Correct	269 ms	5296 KB	Output is correct
31	Correct	408 ms	5072 KB	Output is correct
32	Correct	596 ms	5156 KB	Output is correct
33	Correct	312 ms	4064 KB	Output is correct
34	Correct	532 ms	4160 KB	Output is correct
35	Correct	464 ms	4540 KB	Output is correct
36	Correct	159 ms	3236 KB	Output is correct
37	Correct	243 ms	5152 KB	Output is correct
38	Correct	274 ms	3116 KB	Output is correct
39	Correct	414 ms	4288 KB	Output is correct
40	Correct	609 ms	4084 KB	Output is correct

Subtask #4
53.0 / 53.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	336 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	336 KB	Output is correct
11	Correct	55 ms	11956 KB	Output is correct
12	Correct	65 ms	11996 KB	Output is correct
13	Correct	79 ms	11848 KB	Output is correct
14	Correct	106 ms	11852 KB	Output is correct
15	Correct	61 ms	11964 KB	Output is correct
16	Correct	100 ms	11888 KB	Output is correct
17	Correct	93 ms	11820 KB	Output is correct
18	Correct	47 ms	12144 KB	Output is correct
19	Correct	54 ms	11720 KB	Output is correct
20	Correct	55 ms	11884 KB	Output is correct
21	Correct	80 ms	11908 KB	Output is correct
22	Correct	113 ms	11956 KB	Output is correct
23	Correct	65 ms	11836 KB	Output is correct
24	Correct	101 ms	11848 KB	Output is correct
25	Correct	88 ms	11836 KB	Output is correct
26	Correct	47 ms	11708 KB	Output is correct
27	Correct	54 ms	11956 KB	Output is correct
28	Correct	57 ms	11724 KB	Output is correct
29	Correct	81 ms	11884 KB	Output is correct
30	Correct	111 ms	11884 KB	Output is correct
31	Correct	64 ms	11812 KB	Output is correct
32	Correct	98 ms	11876 KB	Output is correct
33	Correct	89 ms	11832 KB	Output is correct
34	Correct	47 ms	11720 KB	Output is correct
35	Correct	76 ms	11884 KB	Output is correct
36	Correct	79 ms	11836 KB	Output is correct
37	Correct	77 ms	11872 KB	Output is correct
38	Correct	75 ms	11836 KB	Output is correct
39	Correct	76 ms	11832 KB	Output is correct
40	Correct	76 ms	11904 KB	Output is correct

Subtask #5
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	336 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	336 KB	Output is correct
11	Correct	192 ms	5052 KB	Output is correct
12	Correct	231 ms	4684 KB	Output is correct
13	Correct	309 ms	3996 KB	Output is correct
14	Correct	386 ms	4108 KB	Output is correct
15	Correct	261 ms	5024 KB	Output is correct
16	Correct	354 ms	4248 KB	Output is correct
17	Correct	333 ms	4260 KB	Output is correct
18	Correct	147 ms	6016 KB	Output is correct
19	Correct	184 ms	3056 KB	Output is correct
20	Correct	228 ms	4776 KB	Output is correct
21	Correct	254 ms	5184 KB	Output is correct
22	Correct	262 ms	5224 KB	Output is correct
23	Correct	430 ms	4256 KB	Output is correct
24	Correct	619 ms	4100 KB	Output is correct
25	Correct	306 ms	6164 KB	Output is correct
26	Correct	528 ms	4608 KB	Output is correct
27	Correct	471 ms	4564 KB	Output is correct
28	Correct	156 ms	7112 KB	Output is correct
29	Correct	244 ms	3148 KB	Output is correct
30	Correct	269 ms	5296 KB	Output is correct
31	Correct	408 ms	5072 KB	Output is correct
32	Correct	596 ms	5156 KB	Output is correct
33	Correct	312 ms	4064 KB	Output is correct
34	Correct	532 ms	4160 KB	Output is correct
35	Correct	464 ms	4540 KB	Output is correct
36	Correct	159 ms	3236 KB	Output is correct
37	Correct	243 ms	5152 KB	Output is correct
38	Correct	274 ms	3116 KB	Output is correct
39	Correct	414 ms	4288 KB	Output is correct
40	Correct	609 ms	4084 KB	Output is correct
41	Correct	55 ms	11956 KB	Output is correct
42	Correct	65 ms	11996 KB	Output is correct
43	Correct	79 ms	11848 KB	Output is correct
44	Correct	106 ms	11852 KB	Output is correct
45	Correct	61 ms	11964 KB	Output is correct
46	Correct	100 ms	11888 KB	Output is correct
47	Correct	93 ms	11820 KB	Output is correct
48	Correct	47 ms	12144 KB	Output is correct
49	Correct	54 ms	11720 KB	Output is correct
50	Correct	55 ms	11884 KB	Output is correct
51	Correct	80 ms	11908 KB	Output is correct
52	Correct	113 ms	11956 KB	Output is correct
53	Correct	65 ms	11836 KB	Output is correct
54	Correct	101 ms	11848 KB	Output is correct
55	Correct	88 ms	11836 KB	Output is correct
56	Correct	47 ms	11708 KB	Output is correct
57	Correct	54 ms	11956 KB	Output is correct
58	Correct	57 ms	11724 KB	Output is correct
59	Correct	81 ms	11884 KB	Output is correct
60	Correct	111 ms	11884 KB	Output is correct
61	Correct	64 ms	11812 KB	Output is correct
62	Correct	98 ms	11876 KB	Output is correct
63	Correct	89 ms	11832 KB	Output is correct
64	Correct	47 ms	11720 KB	Output is correct
65	Correct	76 ms	11884 KB	Output is correct
66	Correct	79 ms	11836 KB	Output is correct
67	Correct	77 ms	11872 KB	Output is correct
68	Correct	75 ms	11836 KB	Output is correct
69	Correct	76 ms	11832 KB	Output is correct
70	Correct	76 ms	11904 KB	Output is correct
71	Correct	383 ms	36296 KB	Output is correct
72	Correct	387 ms	36404 KB	Output is correct
73	Correct	854 ms	34924 KB	Output is correct
74	Correct	1432 ms	35252 KB	Output is correct
75	Correct	501 ms	37248 KB	Output is correct
76	Correct	1259 ms	35624 KB	Output is correct
77	Correct	1057 ms	35352 KB	Output is correct
78	Correct	215 ms	39268 KB	Output is correct
79	Correct	369 ms	33208 KB	Output is correct
80	Correct	383 ms	36300 KB	Output is correct
81	Correct	794 ms	36192 KB	Output is correct
82	Correct	1383 ms	35264 KB	Output is correct
83	Correct	519 ms	34492 KB	Output is correct
84	Correct	1254 ms	35276 KB	Output is correct
85	Correct	1047 ms	35388 KB	Output is correct
86	Correct	217 ms	33188 KB	Output is correct
87	Correct	394 ms	36380 KB	Output is correct
88	Correct	412 ms	33204 KB	Output is correct
89	Correct	835 ms	35000 KB	Output is correct
90	Correct	1454 ms	35320 KB	Output is correct
91	Correct	550 ms	34488 KB	Output is correct
92	Correct	1276 ms	35632 KB	Output is correct
93	Correct	1069 ms	35440 KB	Output is correct
94	Correct	205 ms	33244 KB	Output is correct
95	Correct	795 ms	35312 KB	Output is correct
96	Correct	816 ms	35440 KB	Output is correct
97	Correct	825 ms	35272 KB	Output is correct
98	Correct	816 ms	35324 KB	Output is correct
99	Correct	810 ms	35248 KB	Output is correct
100	Correct	819 ms	35352 KB	Output is correct

답안 #771468

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