oj.uz

Submission #1105684

# Submission time Handle Problem Language Result Execution time Memory
1105684 2024-10-27T10:29:59 Z FucKanh Snake Escaping (JOI18_snake_escaping) C++11
100 / 100
 1081 ms 54444 KB 
#include<bits/stdc++.h>
#define ll long long
#define int ll
#define pii pair<int,int>

using namespace std;

const int BIT = 20;

int f[1<<BIT], g[1<<BIT], h[1<<BIT], ans;

void solve2(int i, vector<int> &v, int val) {
    if (i==v.size()) {
        ans += h[val];
        return;
    }
    val &= ~(1<<v[i]);
    solve2(i+1,v,val);
    val |= (1<<v[i]);
    solve2(i+1,v,val);
}

void solve1(int i, vector<int> &v, int val, int cnt) {
    if (i==v.size()) {
        if (cnt==0) return;
        if (cnt%2) {
            ans -= f[val];
        }
        else {
            ans += f[val];
        }
        return;
    }
    val |= (1<<v[i]);
    solve1(i+1,v,val,cnt);
    val &= ~(1<<v[i]);
    solve1(i+1,v,val,cnt+1);
}

void solve0(int i, vector<int> &v, int val, int cnt) {
    if (i==v.size()) {
        if (cnt==0) return;
        if (cnt%2) {
            ans -= g[val];
        }
        else {
            ans += g[val];
        }
        return;
    }
    val |= (1<<v[i]);
    solve0(i+1,v,val,cnt+1);
    val &= ~(1<<v[i]);
    solve0(i+1,v,val,cnt);
}

void solve() {
    int n,q; cin >> n >> q;
    for (int i =0; i < (1<<n); i++) {
        char c; cin >> c;
        f[i] += c - '0';
        g[i] += c - '0';
        h[i] += c - '0';
//        cerr << "cin >> " << bitset<5>(i) << " :" << c << endl;
    }
    for (int i = 0; i < n; i++) {
        for (int x = 0; x < (1<<n); x++) {
            if (x&(1<<i)) f[x] += f[x^(1<<i)];
            else g[x] += g[x^(1<<i)];
        }
    }

    for (int i = 0; i < q; i++) {
        string s; cin >> s;
        reverse(s.begin(), s.end());
        int cnt = 0, val = 0, val2 = 0,val1 = 0;
        vector<int> v1,v2,v0;
        for (char c : s) {
            if (c!='0') {
                val |= (1<<cnt);
                if (c=='1') {
                    val2 |= (1<<cnt);
                    v1.push_back(cnt);
                }
                else {
                    v2.push_back(cnt);
                    val1 |= (1<<cnt);
                }
            }
            else {
                v0.push_back(cnt);
            }
            cnt++;
        }
        if (v2.size() <= v1.size() && v2.size() <= v0.size()) {
            ans = 0;
            solve2(0,v2,val);
        }
        else if (v1.size() <= v2.size() && v1.size() <= v0.size()) {
            ans = f[val];
            solve1(0,v1,val,0);
        }
        else {
            ans = g[val2];
            solve0(0,v0,val2,0);
        }
        cout << ans << '\n';
    }
}

signed main() {
    cin.tie(0) -> sync_with_stdio(0);
    solve();
    return 0;
}

Compilation message

snake_escaping.cpp: In function 'void solve2(long long int, std::vector<long long int>&, long long int)':
snake_escaping.cpp:13:10: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     if (i==v.size()) {
      |         ~^~~~~~~~~~
snake_escaping.cpp: In function 'void solve1(long long int, std::vector<long long int>&, long long int, long long int)':
snake_escaping.cpp:24:10: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     if (i==v.size()) {
      |         ~^~~~~~~~~~
snake_escaping.cpp: In function 'void solve0(long long int, std::vector<long long int>&, long long int, long long int)':
snake_escaping.cpp:41:10: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     if (i==v.size()) {
      |         ~^~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4432 KB Output is correct
2 Correct 2 ms 4432 KB Output is correct
3 Correct 2 ms 4432 KB Output is correct
4 Correct 2 ms 4432 KB Output is correct
5 Correct 1 ms 4432 KB Output is correct
6 Correct 1 ms 4432 KB Output is correct
7 Correct 2 ms 4444 KB Output is correct
8 Correct 2 ms 4432 KB Output is correct
9 Correct 1 ms 4432 KB Output is correct
10 Correct 1 ms 4432 KB Output is correct
11 Correct 282 ms 19272 KB Output is correct
12 Correct 320 ms 18760 KB Output is correct
13 Correct 340 ms 18248 KB Output is correct
14 Correct 360 ms 18224 KB Output is correct
15 Correct 307 ms 19272 KB Output is correct
16 Correct 339 ms 18504 KB Output is correct
17 Correct 429 ms 18248 KB Output is correct
18 Correct 202 ms 20112 KB Output is correct
19 Correct 290 ms 17232 KB Output is correct
20 Correct 271 ms 18820 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4432 KB Output is correct
2 Correct 2 ms 4432 KB Output is correct
3 Correct 2 ms 4432 KB Output is correct
4 Correct 2 ms 4432 KB Output is correct
5 Correct 1 ms 4432 KB Output is correct
6 Correct 1 ms 4432 KB Output is correct
7 Correct 2 ms 4444 KB Output is correct
8 Correct 2 ms 4432 KB Output is correct
9 Correct 1 ms 4432 KB Output is correct
10 Correct 1 ms 4432 KB Output is correct
11 Correct 282 ms 19272 KB Output is correct
12 Correct 320 ms 18760 KB Output is correct
13 Correct 340 ms 18248 KB Output is correct
14 Correct 360 ms 18224 KB Output is correct
15 Correct 307 ms 19272 KB Output is correct
16 Correct 339 ms 18504 KB Output is correct
17 Correct 429 ms 18248 KB Output is correct
18 Correct 202 ms 20112 KB Output is correct
19 Correct 290 ms 17232 KB Output is correct
20 Correct 271 ms 18820 KB Output is correct
21 Correct 331 ms 22172 KB Output is correct
22 Correct 359 ms 22304 KB Output is correct
23 Correct 413 ms 21492 KB Output is correct
24 Correct 464 ms 21576 KB Output is correct
25 Correct 367 ms 23112 KB Output is correct
26 Correct 430 ms 21660 KB Output is correct
27 Correct 450 ms 21612 KB Output is correct
28 Correct 214 ms 24136 KB Output is correct
29 Correct 312 ms 20240 KB Output is correct
30 Correct 336 ms 22340 KB Output is correct
31 Correct 422 ms 22088 KB Output is correct
32 Correct 447 ms 22080 KB Output is correct
33 Correct 336 ms 21080 KB Output is correct
34 Correct 445 ms 21320 KB Output is correct
35 Correct 423 ms 21732 KB Output is correct
36 Correct 193 ms 20304 KB Output is correct
37 Correct 307 ms 22120 KB Output is correct
38 Correct 304 ms 20320 KB Output is correct
39 Correct 396 ms 21316 KB Output is correct
40 Correct 418 ms 21320 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4432 KB Output is correct
2 Correct 2 ms 4432 KB Output is correct
3 Correct 2 ms 4432 KB Output is correct
4 Correct 2 ms 4432 KB Output is correct
5 Correct 1 ms 4432 KB Output is correct
6 Correct 1 ms 4432 KB Output is correct
7 Correct 2 ms 4444 KB Output is correct
8 Correct 2 ms 4432 KB Output is correct
9 Correct 1 ms 4432 KB Output is correct
10 Correct 1 ms 4432 KB Output is correct
11 Correct 53 ms 27208 KB Output is correct
12 Correct 55 ms 27368 KB Output is correct
13 Correct 74 ms 27216 KB Output is correct
14 Correct 101 ms 27208 KB Output is correct
15 Correct 57 ms 27208 KB Output is correct
16 Correct 88 ms 27104 KB Output is correct
17 Correct 74 ms 27104 KB Output is correct
18 Correct 44 ms 27464 KB Output is correct
19 Correct 53 ms 27144 KB Output is correct
20 Correct 53 ms 27292 KB Output is correct
21 Correct 66 ms 27216 KB Output is correct
22 Correct 79 ms 27160 KB Output is correct
23 Correct 56 ms 27208 KB Output is correct
24 Correct 75 ms 27216 KB Output is correct
25 Correct 74 ms 27312 KB Output is correct
26 Correct 44 ms 27160 KB Output is correct
27 Correct 58 ms 27212 KB Output is correct
28 Correct 51 ms 27104 KB Output is correct
29 Correct 63 ms 27220 KB Output is correct
30 Correct 78 ms 27208 KB Output is correct
31 Correct 57 ms 27208 KB Output is correct
32 Correct 79 ms 27208 KB Output is correct
33 Correct 82 ms 27208 KB Output is correct
34 Correct 47 ms 27220 KB Output is correct
35 Correct 68 ms 27224 KB Output is correct
36 Correct 72 ms 27332 KB Output is correct
37 Correct 71 ms 27220 KB Output is correct
38 Correct 76 ms 27208 KB Output is correct
39 Correct 69 ms 27184 KB Output is correct
40 Correct 69 ms 27220 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4432 KB Output is correct
2 Correct 2 ms 4432 KB Output is correct
3 Correct 2 ms 4432 KB Output is correct
4 Correct 2 ms 4432 KB Output is correct
5 Correct 1 ms 4432 KB Output is correct
6 Correct 1 ms 4432 KB Output is correct
7 Correct 2 ms 4444 KB Output is correct
8 Correct 2 ms 4432 KB Output is correct
9 Correct 1 ms 4432 KB Output is correct
10 Correct 1 ms 4432 KB Output is correct
11 Correct 282 ms 19272 KB Output is correct
12 Correct 320 ms 18760 KB Output is correct
13 Correct 340 ms 18248 KB Output is correct
14 Correct 360 ms 18224 KB Output is correct
15 Correct 307 ms 19272 KB Output is correct
16 Correct 339 ms 18504 KB Output is correct
17 Correct 429 ms 18248 KB Output is correct
18 Correct 202 ms 20112 KB Output is correct
19 Correct 290 ms 17232 KB Output is correct
20 Correct 271 ms 18820 KB Output is correct
21 Correct 331 ms 22172 KB Output is correct
22 Correct 359 ms 22304 KB Output is correct
23 Correct 413 ms 21492 KB Output is correct
24 Correct 464 ms 21576 KB Output is correct
25 Correct 367 ms 23112 KB Output is correct
26 Correct 430 ms 21660 KB Output is correct
27 Correct 450 ms 21612 KB Output is correct
28 Correct 214 ms 24136 KB Output is correct
29 Correct 312 ms 20240 KB Output is correct
30 Correct 336 ms 22340 KB Output is correct
31 Correct 422 ms 22088 KB Output is correct
32 Correct 447 ms 22080 KB Output is correct
33 Correct 336 ms 21080 KB Output is correct
34 Correct 445 ms 21320 KB Output is correct
35 Correct 423 ms 21732 KB Output is correct
36 Correct 193 ms 20304 KB Output is correct
37 Correct 307 ms 22120 KB Output is correct
38 Correct 304 ms 20320 KB Output is correct
39 Correct 396 ms 21316 KB Output is correct
40 Correct 418 ms 21320 KB Output is correct
41 Correct 53 ms 27208 KB Output is correct
42 Correct 55 ms 27368 KB Output is correct
43 Correct 74 ms 27216 KB Output is correct
44 Correct 101 ms 27208 KB Output is correct
45 Correct 57 ms 27208 KB Output is correct
46 Correct 88 ms 27104 KB Output is correct
47 Correct 74 ms 27104 KB Output is correct
48 Correct 44 ms 27464 KB Output is correct
49 Correct 53 ms 27144 KB Output is correct
50 Correct 53 ms 27292 KB Output is correct
51 Correct 66 ms 27216 KB Output is correct
52 Correct 79 ms 27160 KB Output is correct
53 Correct 56 ms 27208 KB Output is correct
54 Correct 75 ms 27216 KB Output is correct
55 Correct 74 ms 27312 KB Output is correct
56 Correct 44 ms 27160 KB Output is correct
57 Correct 58 ms 27212 KB Output is correct
58 Correct 51 ms 27104 KB Output is correct
59 Correct 63 ms 27220 KB Output is correct
60 Correct 78 ms 27208 KB Output is correct
61 Correct 57 ms 27208 KB Output is correct
62 Correct 79 ms 27208 KB Output is correct
63 Correct 82 ms 27208 KB Output is correct
64 Correct 47 ms 27220 KB Output is correct
65 Correct 68 ms 27224 KB Output is correct
66 Correct 72 ms 27332 KB Output is correct
67 Correct 71 ms 27220 KB Output is correct
68 Correct 76 ms 27208 KB Output is correct
69 Correct 69 ms 27184 KB Output is correct
70 Correct 69 ms 27220 KB Output is correct
71 Correct 494 ms 51392 KB Output is correct
72 Correct 474 ms 51528 KB Output is correct
73 Correct 659 ms 50248 KB Output is correct
74 Correct 892 ms 50460 KB Output is correct
75 Correct 498 ms 52616 KB Output is correct
76 Correct 1081 ms 50864 KB Output is correct
77 Correct 961 ms 51044 KB Output is correct
78 Correct 314 ms 54444 KB Output is correct
79 Correct 489 ms 48492 KB Output is correct
80 Correct 564 ms 51840 KB Output is correct
81 Correct 753 ms 51404 KB Output is correct
82 Correct 971 ms 50436 KB Output is correct
83 Correct 554 ms 49696 KB Output is correct
84 Correct 912 ms 50540 KB Output is correct
85 Correct 842 ms 50616 KB Output is correct
86 Correct 269 ms 48456 KB Output is correct
87 Correct 471 ms 51528 KB Output is correct
88 Correct 577 ms 48492 KB Output is correct
89 Correct 681 ms 50176 KB Output is correct
90 Correct 872 ms 50384 KB Output is correct
91 Correct 574 ms 49780 KB Output is correct
92 Correct 1065 ms 50760 KB Output is correct
93 Correct 966 ms 50752 KB Output is correct
94 Correct 393 ms 48528 KB Output is correct
95 Correct 830 ms 50504 KB Output is correct
96 Correct 739 ms 50504 KB Output is correct
97 Correct 702 ms 50612 KB Output is correct
98 Correct 829 ms 50608 KB Output is correct
99 Correct 795 ms 50496 KB Output is correct
100 Correct 755 ms 50504 KB Output is correct