oj.uz

Submission #1037892

# Submission time Handle Problem Language Result Execution time Memory
1037892 2024-07-29T09:50:01 Z vjudge1 Snake Escaping (JOI18_snake_escaping) C++17
100 / 100
 1114 ms 47604 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define pb                  push_back
#define all(x)              x.begin(), x.end()

const int mxn = 2e6 + 3;
const int lg = 21;

int n, q;

int A[mxn];
int dp[mxn], pd[mxn];

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> q;
    string s; cin >> s;
    for(int i = 0; i < (1 << n); i ++) {
        int x = (s[i] - '0');
        A[i] = x;
        dp[i] = pd[i] = x;
    }

    for(int i = 0; i < n; i ++)
        for(int mask = 0; mask < (1 << n); mask ++)
            if(mask >> i & 1)
                dp[mask] += dp[mask ^ (1 << i)];
            else
                pd[mask] += pd[mask ^ (1 << i)];

    while(q --) {
        vector<int> c0, c1, c2; int x = 0;
        string st; cin >> st;
        reverse(all(st));
        for(int i = 0; i < n; i ++) {
            char c = st[i];
            if(c == '1')
                x += (1 << i);
            if(c == '0') c0.pb(i);
            if(c == '1') c1.pb(i);
            if(c == '?') c2.pb(i);
        }
        if(c2.size() <= 6) {
            int f = c2.size(), ans = 0;
            for(int mask = 0; mask < (1 << f); mask ++) {
                int y = x;
                for(int i = 0; i < f; i ++)
                    if(mask >> i & 1)
                        y ^= (1 << c2[i]);
                ans += A[y];
            }
            cout << ans << '\n';
            continue;
        }
        if(c1.size() <= 6) {
            int f = c1.size();
            for(int i : c2)
                x ^= (1 << i);
            int ans = 0;
            for(int mask = 0; mask < (1 << f); mask ++) {
                int y = x;
                for(int i = 0; i < f; i ++)
                    if(mask >> i & 1)
                        y ^= (1 << c1[i]);
                if(__builtin_popcount(mask) & 1)
                    ans -= dp[y];
                else
                    ans += dp[y];
            }
            cout << ans << '\n';
            continue;
        }
        if(c0.size() <= 6) {
            int f = c0.size();
            int ans = 0;
            for(int mask = 0; mask < (1 << f); mask ++) {
                int y = x;
                for(int i = 0; i < f; i ++)
                    if(mask >> i & 1)
                        y ^= (1 << c0[i]);
                if(__builtin_popcount(mask) & 1)
                    ans -= pd[y];
                else
                    ans += pd[y];
            }
            cout << ans << '\n';
            continue;
        }
    }

    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4592 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4592 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 389 ms 19280 KB Output is correct
12 Correct 400 ms 18828 KB Output is correct
13 Correct 338 ms 18112 KB Output is correct
14 Correct 382 ms 18260 KB Output is correct
15 Correct 591 ms 19320 KB Output is correct
16 Correct 433 ms 18256 KB Output is correct
17 Correct 435 ms 18332 KB Output is correct
18 Correct 244 ms 20308 KB Output is correct
19 Correct 286 ms 17236 KB Output is correct
20 Correct 449 ms 18856 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4592 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 389 ms 19280 KB Output is correct
12 Correct 400 ms 18828 KB Output is correct
13 Correct 338 ms 18112 KB Output is correct
14 Correct 382 ms 18260 KB Output is correct
15 Correct 591 ms 19320 KB Output is correct
16 Correct 433 ms 18256 KB Output is correct
17 Correct 435 ms 18332 KB Output is correct
18 Correct 244 ms 20308 KB Output is correct
19 Correct 286 ms 17236 KB Output is correct
20 Correct 449 ms 18856 KB Output is correct
21 Correct 732 ms 22264 KB Output is correct
22 Correct 471 ms 22352 KB Output is correct
23 Correct 469 ms 21332 KB Output is correct
24 Correct 461 ms 21208 KB Output is correct
25 Correct 394 ms 23252 KB Output is correct
26 Correct 577 ms 21840 KB Output is correct
27 Correct 571 ms 21756 KB Output is correct
28 Correct 214 ms 24264 KB Output is correct
29 Correct 307 ms 20308 KB Output is correct
30 Correct 672 ms 22372 KB Output is correct
31 Correct 776 ms 22256 KB Output is correct
32 Correct 544 ms 22264 KB Output is correct
33 Correct 385 ms 21076 KB Output is correct
34 Correct 468 ms 21180 KB Output is correct
35 Correct 578 ms 21596 KB Output is correct
36 Correct 229 ms 20064 KB Output is correct
37 Correct 717 ms 22092 KB Output is correct
38 Correct 328 ms 20284 KB Output is correct
39 Correct 499 ms 21328 KB Output is correct
40 Correct 443 ms 21076 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4592 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 43 ms 20480 KB Output is correct
12 Correct 44 ms 20464 KB Output is correct
13 Correct 59 ms 20208 KB Output is correct
14 Correct 73 ms 20444 KB Output is correct
15 Correct 51 ms 20508 KB Output is correct
16 Correct 69 ms 20240 KB Output is correct
17 Correct 66 ms 20208 KB Output is correct
18 Correct 36 ms 20468 KB Output is correct
19 Correct 44 ms 20212 KB Output is correct
20 Correct 47 ms 20260 KB Output is correct
21 Correct 60 ms 20464 KB Output is correct
22 Correct 70 ms 20240 KB Output is correct
23 Correct 50 ms 20208 KB Output is correct
24 Correct 72 ms 20208 KB Output is correct
25 Correct 69 ms 20240 KB Output is correct
26 Correct 34 ms 20216 KB Output is correct
27 Correct 44 ms 20476 KB Output is correct
28 Correct 44 ms 20212 KB Output is correct
29 Correct 58 ms 20244 KB Output is correct
30 Correct 67 ms 20208 KB Output is correct
31 Correct 55 ms 20284 KB Output is correct
32 Correct 79 ms 20244 KB Output is correct
33 Correct 65 ms 20204 KB Output is correct
34 Correct 36 ms 20256 KB Output is correct
35 Correct 59 ms 20208 KB Output is correct
36 Correct 63 ms 20208 KB Output is correct
37 Correct 59 ms 20216 KB Output is correct
38 Correct 59 ms 20292 KB Output is correct
39 Correct 58 ms 20212 KB Output is correct
40 Correct 58 ms 20208 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4592 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 389 ms 19280 KB Output is correct
12 Correct 400 ms 18828 KB Output is correct
13 Correct 338 ms 18112 KB Output is correct
14 Correct 382 ms 18260 KB Output is correct
15 Correct 591 ms 19320 KB Output is correct
16 Correct 433 ms 18256 KB Output is correct
17 Correct 435 ms 18332 KB Output is correct
18 Correct 244 ms 20308 KB Output is correct
19 Correct 286 ms 17236 KB Output is correct
20 Correct 449 ms 18856 KB Output is correct
21 Correct 732 ms 22264 KB Output is correct
22 Correct 471 ms 22352 KB Output is correct
23 Correct 469 ms 21332 KB Output is correct
24 Correct 461 ms 21208 KB Output is correct
25 Correct 394 ms 23252 KB Output is correct
26 Correct 577 ms 21840 KB Output is correct
27 Correct 571 ms 21756 KB Output is correct
28 Correct 214 ms 24264 KB Output is correct
29 Correct 307 ms 20308 KB Output is correct
30 Correct 672 ms 22372 KB Output is correct
31 Correct 776 ms 22256 KB Output is correct
32 Correct 544 ms 22264 KB Output is correct
33 Correct 385 ms 21076 KB Output is correct
34 Correct 468 ms 21180 KB Output is correct
35 Correct 578 ms 21596 KB Output is correct
36 Correct 229 ms 20064 KB Output is correct
37 Correct 717 ms 22092 KB Output is correct
38 Correct 328 ms 20284 KB Output is correct
39 Correct 499 ms 21328 KB Output is correct
40 Correct 443 ms 21076 KB Output is correct
41 Correct 43 ms 20480 KB Output is correct
42 Correct 44 ms 20464 KB Output is correct
43 Correct 59 ms 20208 KB Output is correct
44 Correct 73 ms 20444 KB Output is correct
45 Correct 51 ms 20508 KB Output is correct
46 Correct 69 ms 20240 KB Output is correct
47 Correct 66 ms 20208 KB Output is correct
48 Correct 36 ms 20468 KB Output is correct
49 Correct 44 ms 20212 KB Output is correct
50 Correct 47 ms 20260 KB Output is correct
51 Correct 60 ms 20464 KB Output is correct
52 Correct 70 ms 20240 KB Output is correct
53 Correct 50 ms 20208 KB Output is correct
54 Correct 72 ms 20208 KB Output is correct
55 Correct 69 ms 20240 KB Output is correct
56 Correct 34 ms 20216 KB Output is correct
57 Correct 44 ms 20476 KB Output is correct
58 Correct 44 ms 20212 KB Output is correct
59 Correct 58 ms 20244 KB Output is correct
60 Correct 67 ms 20208 KB Output is correct
61 Correct 55 ms 20284 KB Output is correct
62 Correct 79 ms 20244 KB Output is correct
63 Correct 65 ms 20204 KB Output is correct
64 Correct 36 ms 20256 KB Output is correct
65 Correct 59 ms 20208 KB Output is correct
66 Correct 63 ms 20208 KB Output is correct
67 Correct 59 ms 20216 KB Output is correct
68 Correct 59 ms 20292 KB Output is correct
69 Correct 58 ms 20212 KB Output is correct
70 Correct 58 ms 20208 KB Output is correct
71 Correct 498 ms 44644 KB Output is correct
72 Correct 516 ms 44700 KB Output is correct
73 Correct 741 ms 43176 KB Output is correct
74 Correct 1114 ms 43512 KB Output is correct
75 Correct 627 ms 45552 KB Output is correct
76 Correct 986 ms 43892 KB Output is correct
77 Correct 924 ms 43928 KB Output is correct
78 Correct 306 ms 47604 KB Output is correct
79 Correct 443 ms 41716 KB Output is correct
80 Correct 531 ms 44852 KB Output is correct
81 Correct 798 ms 44712 KB Output is correct
82 Correct 1049 ms 43560 KB Output is correct
83 Correct 591 ms 42740 KB Output is correct
84 Correct 1012 ms 43512 KB Output is correct
85 Correct 880 ms 43928 KB Output is correct
86 Correct 270 ms 41528 KB Output is correct
87 Correct 478 ms 44556 KB Output is correct
88 Correct 549 ms 40864 KB Output is correct
89 Correct 720 ms 43244 KB Output is correct
90 Correct 933 ms 43584 KB Output is correct
91 Correct 598 ms 42740 KB Output is correct
92 Correct 1061 ms 44024 KB Output is correct
93 Correct 897 ms 43820 KB Output is correct
94 Correct 261 ms 41516 KB Output is correct
95 Correct 756 ms 43752 KB Output is correct
96 Correct 769 ms 43652 KB Output is correct
97 Correct 775 ms 43756 KB Output is correct
98 Correct 765 ms 43736 KB Output is correct
99 Correct 767 ms 43760 KB Output is correct
100 Correct 765 ms 43760 KB Output is correct