oj.uz

Submission #957950

# Submission time Handle Problem Language Result Execution time Memory
957950 2024-04-04T14:04:48 Z BhavayGoyal Snake Escaping (JOI18_snake_escaping) C++14
100 / 100
 1188 ms 38796 KB 
#include <bits/stdc++.h>
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template<class T> using oset = 
            tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define ll long long
#define ld long double
#define ar array
#define vi vector<int>
#define vii vector<vector<int>>
#define pii pair<int, int>
#define pb push_back
#define all(x) x.begin(), x.end()
#define f first
#define s second
#define endl "\n"

const int MOD = 1e9+7;
const int inf = 1e9;
const ll linf = 1e18;

const int d4i[4]={-1, 0, 1, 0}, d4j[4]={0, 1, 0, -1};
const int d8i[8]={-1, -1, 0, 1, 1, 1, 0, -1}, d8j[8]={0, 1, 1, 1, 0, -1, -1, -1};

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());


// -------------------------------------------------- Main Code --------------------------------------------------

const int N = (1<<20)+5;
int n, q, arr[N], dp[N], dp2[N];

void sol() {
    cin >> n >> q;
    for (int i = 0; i < (1<<n); i++) {char x; cin >> x; arr[i] = x-'0';}

    for (int i = 0; i < (1<<n); i++) dp[i] = arr[i], dp2[i] = arr[i];
    for (int i = 0; i < n; i++) {
        for (int mask = 0; mask < (1<<n); mask++) {
            if (mask&(1<<i)) dp[mask] += dp[mask^(1<<i)];
            if ((mask&(1<<i)) == 0) dp2[mask] += dp2[mask^(1<<i)];
        }
    }


    while (q--) {
        string s; cin >> s;
        int one = 0, zero = 0, question = 0;
        for (int i = 0; i < n; i++) {
            one += s[i]=='1';
            zero += s[i]=='0';
            question += s[i]=='?';
        }

        if (question <= 6) {
            vi temp;
            int num = 0;
            reverse(all(s));
            for (int i = 0; i < n; i++) {
                if (s[i] == '?') temp.pb(i);
                if (s[i] == '1') num += (1<<i);
            }

            int ans = 0;
            for (int i = 0; i < (1<<temp.size()); i++) {
                int tempNum = num;
                for (int j = 0; j < temp.size(); j++) {
                    if (i&(1<<j)) {
                        tempNum ^= (1<<temp[j]);
                    }
                }
                ans += arr[tempNum];
            }
            cout << ans << endl;
        }
        else if (one <= 6) {
            vi temp;
            int num = 0;
            reverse(all(s));
            for (int i = 0; i < n; i++) {
                if (s[i] == '1') temp.pb(i);
                if (s[i] == '1' || s[i] == '?') num += (1<<i);
            }

            int ans = 0;
            for (int i = 0; i < (1<<temp.size()); i++) {
                int tempNum = num, ct = 0;
                for (int j = 0; j < temp.size(); j++) {
                    if (i&(1<<j)) {
                        tempNum ^= (1<<temp[j]);
                        ct++;
                    }
                }
                if (ct%2 != 0) ans -= dp[tempNum];
                else ans += dp[tempNum];
            }

            cout << ans << endl;
        }
        else {
            vi temp;
            int num = 0;
            reverse(all(s));
            for (int i = 0; i < n; i++) {
                if (s[i] == '0') temp.pb(i);
                if (s[i] == '1') num += (1<<i);
            }

            int ans = 0;
            for (int i = 0; i < (1<<temp.size()); i++) {
                int tempNum = num, ct = 0;
                for (int j = 0; j < temp.size(); j++) {
                    if (!(i&(1<<j))) {
                        tempNum ^= (1<<temp[j]);
                        ct++;
                    }
                }
                if (ct%2 != 0) ans -= dp2[tempNum];
                else ans += dp2[tempNum];
            }

            cout << ans << endl;
        }
    }
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t = 1;
    // cin >> t; 
    while (t--) {
        sol();
    }
    return 0;
}

Compilation message

snake_escaping.cpp: In function 'void sol()':
snake_escaping.cpp:72:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |                 for (int j = 0; j < temp.size(); j++) {
      |                                 ~~^~~~~~~~~~~~~
snake_escaping.cpp:93:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |                 for (int j = 0; j < temp.size(); j++) {
      |                                 ~~^~~~~~~~~~~~~
snake_escaping.cpp:117:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |                 for (int j = 0; j < temp.size(); j++) {
      |                                 ~~^~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4444 KB Output is correct
2 Correct 2 ms 4572 KB Output is correct
3 Correct 2 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 2 ms 4444 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 1 ms 4440 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 2 ms 4444 KB Output is correct
2 Correct 2 ms 4572 KB Output is correct
3 Correct 2 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 2 ms 4444 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 1 ms 4440 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 526 ms 17296 KB Output is correct
12 Correct 488 ms 16820 KB Output is correct
13 Correct 321 ms 16180 KB Output is correct
14 Correct 325 ms 16380 KB Output is correct
15 Correct 930 ms 17252 KB Output is correct
16 Correct 425 ms 16500 KB Output is correct
17 Correct 419 ms 16308 KB Output is correct
18 Correct 178 ms 18072 KB Output is correct
19 Correct 222 ms 15108 KB Output is correct
20 Correct 516 ms 16760 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4444 KB Output is correct
2 Correct 2 ms 4572 KB Output is correct
3 Correct 2 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 2 ms 4444 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 1 ms 4440 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 526 ms 17296 KB Output is correct
12 Correct 488 ms 16820 KB Output is correct
13 Correct 321 ms 16180 KB Output is correct
14 Correct 325 ms 16380 KB Output is correct
15 Correct 930 ms 17252 KB Output is correct
16 Correct 425 ms 16500 KB Output is correct
17 Correct 419 ms 16308 KB Output is correct
18 Correct 178 ms 18072 KB Output is correct
19 Correct 222 ms 15108 KB Output is correct
20 Correct 516 ms 16760 KB Output is correct
21 Correct 914 ms 19856 KB Output is correct
22 Correct 485 ms 19944 KB Output is correct
23 Correct 446 ms 19132 KB Output is correct
24 Correct 422 ms 18732 KB Output is correct
25 Correct 358 ms 20772 KB Output is correct
26 Correct 578 ms 18988 KB Output is correct
27 Correct 545 ms 18928 KB Output is correct
28 Correct 180 ms 21648 KB Output is correct
29 Correct 237 ms 17580 KB Output is correct
30 Correct 692 ms 19680 KB Output is correct
31 Correct 956 ms 19224 KB Output is correct
32 Correct 596 ms 19248 KB Output is correct
33 Correct 347 ms 18212 KB Output is correct
34 Correct 433 ms 18428 KB Output is correct
35 Correct 534 ms 18884 KB Output is correct
36 Correct 213 ms 17544 KB Output is correct
37 Correct 933 ms 19424 KB Output is correct
38 Correct 242 ms 17452 KB Output is correct
39 Correct 446 ms 18632 KB Output is correct
40 Correct 441 ms 18384 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4444 KB Output is correct
2 Correct 2 ms 4572 KB Output is correct
3 Correct 2 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 2 ms 4444 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 1 ms 4440 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 45 ms 14936 KB Output is correct
12 Correct 53 ms 14656 KB Output is correct
13 Correct 67 ms 14504 KB Output is correct
14 Correct 85 ms 14824 KB Output is correct
15 Correct 55 ms 14768 KB Output is correct
16 Correct 77 ms 14552 KB Output is correct
17 Correct 84 ms 14752 KB Output is correct
18 Correct 39 ms 14860 KB Output is correct
19 Correct 47 ms 14528 KB Output is correct
20 Correct 48 ms 14928 KB Output is correct
21 Correct 64 ms 14652 KB Output is correct
22 Correct 84 ms 14944 KB Output is correct
23 Correct 54 ms 14676 KB Output is correct
24 Correct 82 ms 14536 KB Output is correct
25 Correct 72 ms 14652 KB Output is correct
26 Correct 46 ms 14532 KB Output is correct
27 Correct 48 ms 14792 KB Output is correct
28 Correct 45 ms 14588 KB Output is correct
29 Correct 64 ms 14476 KB Output is correct
30 Correct 88 ms 14824 KB Output is correct
31 Correct 53 ms 14672 KB Output is correct
32 Correct 77 ms 14588 KB Output is correct
33 Correct 93 ms 14676 KB Output is correct
34 Correct 39 ms 14624 KB Output is correct
35 Correct 75 ms 14676 KB Output is correct
36 Correct 79 ms 15188 KB Output is correct
37 Correct 64 ms 14676 KB Output is correct
38 Correct 92 ms 14528 KB Output is correct
39 Correct 73 ms 14956 KB Output is correct
40 Correct 65 ms 14676 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4444 KB Output is correct
2 Correct 2 ms 4572 KB Output is correct
3 Correct 2 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 2 ms 4444 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 1 ms 4440 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 526 ms 17296 KB Output is correct
12 Correct 488 ms 16820 KB Output is correct
13 Correct 321 ms 16180 KB Output is correct
14 Correct 325 ms 16380 KB Output is correct
15 Correct 930 ms 17252 KB Output is correct
16 Correct 425 ms 16500 KB Output is correct
17 Correct 419 ms 16308 KB Output is correct
18 Correct 178 ms 18072 KB Output is correct
19 Correct 222 ms 15108 KB Output is correct
20 Correct 516 ms 16760 KB Output is correct
21 Correct 914 ms 19856 KB Output is correct
22 Correct 485 ms 19944 KB Output is correct
23 Correct 446 ms 19132 KB Output is correct
24 Correct 422 ms 18732 KB Output is correct
25 Correct 358 ms 20772 KB Output is correct
26 Correct 578 ms 18988 KB Output is correct
27 Correct 545 ms 18928 KB Output is correct
28 Correct 180 ms 21648 KB Output is correct
29 Correct 237 ms 17580 KB Output is correct
30 Correct 692 ms 19680 KB Output is correct
31 Correct 956 ms 19224 KB Output is correct
32 Correct 596 ms 19248 KB Output is correct
33 Correct 347 ms 18212 KB Output is correct
34 Correct 433 ms 18428 KB Output is correct
35 Correct 534 ms 18884 KB Output is correct
36 Correct 213 ms 17544 KB Output is correct
37 Correct 933 ms 19424 KB Output is correct
38 Correct 242 ms 17452 KB Output is correct
39 Correct 446 ms 18632 KB Output is correct
40 Correct 441 ms 18384 KB Output is correct
41 Correct 45 ms 14936 KB Output is correct
42 Correct 53 ms 14656 KB Output is correct
43 Correct 67 ms 14504 KB Output is correct
44 Correct 85 ms 14824 KB Output is correct
45 Correct 55 ms 14768 KB Output is correct
46 Correct 77 ms 14552 KB Output is correct
47 Correct 84 ms 14752 KB Output is correct
48 Correct 39 ms 14860 KB Output is correct
49 Correct 47 ms 14528 KB Output is correct
50 Correct 48 ms 14928 KB Output is correct
51 Correct 64 ms 14652 KB Output is correct
52 Correct 84 ms 14944 KB Output is correct
53 Correct 54 ms 14676 KB Output is correct
54 Correct 82 ms 14536 KB Output is correct
55 Correct 72 ms 14652 KB Output is correct
56 Correct 46 ms 14532 KB Output is correct
57 Correct 48 ms 14792 KB Output is correct
58 Correct 45 ms 14588 KB Output is correct
59 Correct 64 ms 14476 KB Output is correct
60 Correct 88 ms 14824 KB Output is correct
61 Correct 53 ms 14672 KB Output is correct
62 Correct 77 ms 14588 KB Output is correct
63 Correct 93 ms 14676 KB Output is correct
64 Correct 39 ms 14624 KB Output is correct
65 Correct 75 ms 14676 KB Output is correct
66 Correct 79 ms 15188 KB Output is correct
67 Correct 64 ms 14676 KB Output is correct
68 Correct 92 ms 14528 KB Output is correct
69 Correct 73 ms 14956 KB Output is correct
70 Correct 65 ms 14676 KB Output is correct
71 Correct 388 ms 34352 KB Output is correct
72 Correct 420 ms 34636 KB Output is correct
73 Correct 718 ms 32992 KB Output is correct
74 Correct 1131 ms 33200 KB Output is correct
75 Correct 568 ms 35584 KB Output is correct
76 Correct 1188 ms 33692 KB Output is correct
77 Correct 1002 ms 33412 KB Output is correct
78 Correct 291 ms 37592 KB Output is correct
79 Correct 383 ms 31172 KB Output is correct
80 Correct 501 ms 34472 KB Output is correct
81 Correct 755 ms 34304 KB Output is correct
82 Correct 1101 ms 27848 KB Output is correct
83 Correct 558 ms 26780 KB Output is correct
84 Correct 1137 ms 27720 KB Output is correct
85 Correct 926 ms 27884 KB Output is correct
86 Correct 259 ms 25656 KB Output is correct
87 Correct 366 ms 28688 KB Output is correct
88 Correct 418 ms 25524 KB Output is correct
89 Correct 720 ms 27592 KB Output is correct
90 Correct 1142 ms 31148 KB Output is correct
91 Correct 545 ms 37916 KB Output is correct
92 Correct 1074 ms 38796 KB Output is correct
93 Correct 1008 ms 38448 KB Output is correct
94 Correct 275 ms 36100 KB Output is correct
95 Correct 798 ms 38364 KB Output is correct
96 Correct 799 ms 38248 KB Output is correct
97 Correct 757 ms 38300 KB Output is correct
98 Correct 758 ms 38436 KB Output is correct
99 Correct 795 ms 38228 KB Output is correct
100 Correct 749 ms 38228 KB Output is correct