oj.uz

Submission #957897

# Submission time Handle Problem Language Result Execution time Memory
957897 2024-04-04T12:52:31 Z BhavayGoyal Snake Escaping (JOI18_snake_escaping) C++14
12 / 100
 2000 ms 9196 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 <= 12) {
            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 2 ms 2392 KB Output is correct
2 Correct 1 ms 2396 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 2392 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 2 ms 2396 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2392 KB Output is correct
2 Correct 1 ms 2396 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 2392 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 2 ms 2396 KB Output is correct
11 Correct 495 ms 6468 KB Output is correct
12 Correct 200 ms 5944 KB Output is correct
13 Correct 304 ms 5440 KB Output is correct
14 Correct 321 ms 5416 KB Output is correct
15 Correct 270 ms 6368 KB Output is correct
16 Correct 415 ms 5588 KB Output is correct
17 Correct 449 ms 5500 KB Output is correct
18 Correct 159 ms 7412 KB Output is correct
19 Correct 483 ms 4432 KB Output is correct
20 Correct 1022 ms 6040 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2392 KB Output is correct
2 Correct 1 ms 2396 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 2392 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 2 ms 2396 KB Output is correct
11 Correct 495 ms 6468 KB Output is correct
12 Correct 200 ms 5944 KB Output is correct
13 Correct 304 ms 5440 KB Output is correct
14 Correct 321 ms 5416 KB Output is correct
15 Correct 270 ms 6368 KB Output is correct
16 Correct 415 ms 5588 KB Output is correct
17 Correct 449 ms 5500 KB Output is correct
18 Correct 159 ms 7412 KB Output is correct
19 Correct 483 ms 4432 KB Output is correct
20 Correct 1022 ms 6040 KB Output is correct
21 Correct 866 ms 6560 KB Output is correct
22 Correct 240 ms 6484 KB Output is correct
23 Correct 436 ms 5540 KB Output is correct
24 Correct 393 ms 5340 KB Output is correct
25 Correct 333 ms 7504 KB Output is correct
26 Correct 720 ms 5968 KB Output is correct
27 Correct 931 ms 6112 KB Output is correct
28 Correct 161 ms 8388 KB Output is correct
29 Correct 1474 ms 4676 KB Output is correct
30 Execution timed out 2041 ms 4132 KB Time limit exceeded
31 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2392 KB Output is correct
2 Correct 1 ms 2396 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 2392 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 2 ms 2396 KB Output is correct
11 Correct 1888 ms 9076 KB Output is correct
12 Correct 45 ms 8744 KB Output is correct
13 Correct 96 ms 8668 KB Output is correct
14 Correct 92 ms 8716 KB Output is correct
15 Correct 57 ms 9040 KB Output is correct
16 Correct 563 ms 8832 KB Output is correct
17 Correct 564 ms 8732 KB Output is correct
18 Correct 38 ms 8892 KB Output is correct
19 Correct 1863 ms 8956 KB Output is correct
20 Execution timed out 2041 ms 9196 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2392 KB Output is correct
2 Correct 1 ms 2396 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 2392 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 2 ms 2396 KB Output is correct
11 Correct 495 ms 6468 KB Output is correct
12 Correct 200 ms 5944 KB Output is correct
13 Correct 304 ms 5440 KB Output is correct
14 Correct 321 ms 5416 KB Output is correct
15 Correct 270 ms 6368 KB Output is correct
16 Correct 415 ms 5588 KB Output is correct
17 Correct 449 ms 5500 KB Output is correct
18 Correct 159 ms 7412 KB Output is correct
19 Correct 483 ms 4432 KB Output is correct
20 Correct 1022 ms 6040 KB Output is correct
21 Correct 866 ms 6560 KB Output is correct
22 Correct 240 ms 6484 KB Output is correct
23 Correct 436 ms 5540 KB Output is correct
24 Correct 393 ms 5340 KB Output is correct
25 Correct 333 ms 7504 KB Output is correct
26 Correct 720 ms 5968 KB Output is correct
27 Correct 931 ms 6112 KB Output is correct
28 Correct 161 ms 8388 KB Output is correct
29 Correct 1474 ms 4676 KB Output is correct
30 Execution timed out 2041 ms 4132 KB Time limit exceeded
31 Halted 0 ms 0 KB -