oj.uz

Submission #957892

# Submission time Handle Problem Language Result Execution time Memory
957892 2024-04-04T12:49:21 Z BhavayGoyal Snake Escaping (JOI18_snake_escaping) C++14
22 / 100
 2000 ms 22220 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];

int getAns(string &s) {
    int num = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == '?') {num = -1; break;}
        else num += (1<<(n-i-1))*(s[i]-'0');
    }
    if (num != -1) {
        return arr[num];
    }

    int ans = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == '?') {
            s[i] = '1';
            ans += getAns(s);
            s[i] = '0';
            ans += getAns(s);
            s[i] = '?';
            break;
        }
    }

    return ans;
}

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

    // for (int mask = 0; mask < (1<<n); mask++) {
    //     dp[mask] = arr[mask];
    //     for (int i = 0; i < n; i++) {
    //         if (mask&(1<<i)) {
    //             dp[mask] = dp[mask] + dp[mask^(1<<i)];
    //         }
    //     }
    // }
    for(int i = 0; i<(1<<n); ++i)
        dp[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)];
    }

    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 (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 {
            cout << getAns(s) << 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:103:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |                 for (int j = 0; j < temp.size(); j++) {
      |                                 ~~^~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2524 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 502 ms 14956 KB Output is correct
12 Correct 207 ms 14416 KB Output is correct
13 Correct 307 ms 13668 KB Output is correct
14 Correct 314 ms 13908 KB Output is correct
15 Correct 274 ms 14956 KB Output is correct
16 Correct 404 ms 13904 KB Output is correct
17 Correct 412 ms 13908 KB Output is correct
18 Correct 157 ms 15956 KB Output is correct
19 Correct 503 ms 12872 KB Output is correct
20 Correct 492 ms 14540 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2524 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 502 ms 14956 KB Output is correct
12 Correct 207 ms 14416 KB Output is correct
13 Correct 307 ms 13668 KB Output is correct
14 Correct 314 ms 13908 KB Output is correct
15 Correct 274 ms 14956 KB Output is correct
16 Correct 404 ms 13904 KB Output is correct
17 Correct 412 ms 13908 KB Output is correct
18 Correct 157 ms 15956 KB Output is correct
19 Correct 503 ms 12872 KB Output is correct
20 Correct 492 ms 14540 KB Output is correct
21 Correct 863 ms 17220 KB Output is correct
22 Correct 244 ms 17256 KB Output is correct
23 Correct 426 ms 16668 KB Output is correct
24 Correct 396 ms 16212 KB Output is correct
25 Correct 335 ms 18272 KB Output is correct
26 Correct 521 ms 16980 KB Output is correct
27 Correct 522 ms 19556 KB Output is correct
28 Correct 169 ms 22220 KB Output is correct
29 Correct 131 ms 18256 KB Output is correct
30 Correct 990 ms 20176 KB Output is correct
31 Correct 465 ms 20052 KB Output is correct
32 Correct 402 ms 20100 KB Output is correct
33 Correct 348 ms 19176 KB Output is correct
34 Correct 546 ms 19028 KB Output is correct
35 Correct 521 ms 19460 KB Output is correct
36 Correct 137 ms 18340 KB Output is correct
37 Correct 227 ms 20032 KB Output is correct
38 Correct 394 ms 18200 KB Output is correct
39 Correct 923 ms 19280 KB Output is correct
40 Correct 587 ms 19312 KB Output is correct

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2524 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Execution timed out 2063 ms 10916 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2524 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 502 ms 14956 KB Output is correct
12 Correct 207 ms 14416 KB Output is correct
13 Correct 307 ms 13668 KB Output is correct
14 Correct 314 ms 13908 KB Output is correct
15 Correct 274 ms 14956 KB Output is correct
16 Correct 404 ms 13904 KB Output is correct
17 Correct 412 ms 13908 KB Output is correct
18 Correct 157 ms 15956 KB Output is correct
19 Correct 503 ms 12872 KB Output is correct
20 Correct 492 ms 14540 KB Output is correct
21 Correct 863 ms 17220 KB Output is correct
22 Correct 244 ms 17256 KB Output is correct
23 Correct 426 ms 16668 KB Output is correct
24 Correct 396 ms 16212 KB Output is correct
25 Correct 335 ms 18272 KB Output is correct
26 Correct 521 ms 16980 KB Output is correct
27 Correct 522 ms 19556 KB Output is correct
28 Correct 169 ms 22220 KB Output is correct
29 Correct 131 ms 18256 KB Output is correct
30 Correct 990 ms 20176 KB Output is correct
31 Correct 465 ms 20052 KB Output is correct
32 Correct 402 ms 20100 KB Output is correct
33 Correct 348 ms 19176 KB Output is correct
34 Correct 546 ms 19028 KB Output is correct
35 Correct 521 ms 19460 KB Output is correct
36 Correct 137 ms 18340 KB Output is correct
37 Correct 227 ms 20032 KB Output is correct
38 Correct 394 ms 18200 KB Output is correct
39 Correct 923 ms 19280 KB Output is correct
40 Correct 587 ms 19312 KB Output is correct
41 Execution timed out 2063 ms 10916 KB Time limit exceeded
42 Halted 0 ms 0 KB -