oj.uz

Submission #957811

# Submission time Handle Problem Language Result Execution time Memory
957811 2024-04-04T11:08:25 Z BhavayGoyal Snake Escaping (JOI18_snake_escaping) C++14
12 / 100
 2000 ms 65536 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];
map<string, int> mp;

int sol(string s) {
    if (mp.find(s) != mp.end()) {
        return mp[s];
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == '?') {
            s[i] = '0';
            ans = (ans + sol(s));
            s[i] = '1';
            ans = (ans + sol(s));
            s[i] = '?';
            break;
        }
    }
    return mp[s] = ans;
}

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++) {
        string s(n,'0');
        for (int j = 0; j < n; j++) {
            if (i&(1<<j)) s[j] = '1';
        }
        reverse(all(s));
        mp[s] = arr[i];
    }

    string s(n, '?');
    sol(s);

    while (q--) {
        string s; cin >> s;
        cout << sol(s) << endl;
    }
}

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

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 604 KB Output is correct
2 Correct 4 ms 860 KB Output is correct
3 Correct 4 ms 860 KB Output is correct
4 Correct 5 ms 860 KB Output is correct
5 Correct 10 ms 1372 KB Output is correct
6 Correct 6 ms 1116 KB Output is correct
7 Correct 7 ms 1116 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 5 ms 904 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 604 KB Output is correct
2 Correct 4 ms 860 KB Output is correct
3 Correct 4 ms 860 KB Output is correct
4 Correct 5 ms 860 KB Output is correct
5 Correct 10 ms 1372 KB Output is correct
6 Correct 6 ms 1116 KB Output is correct
7 Correct 7 ms 1116 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 5 ms 904 KB Output is correct
11 Correct 393 ms 14676 KB Output is correct
12 Correct 440 ms 15292 KB Output is correct
13 Correct 515 ms 15060 KB Output is correct
14 Correct 491 ms 15116 KB Output is correct
15 Correct 509 ms 16924 KB Output is correct
16 Correct 567 ms 16468 KB Output is correct
17 Correct 655 ms 18860 KB Output is correct
18 Correct 335 ms 16224 KB Output is correct
19 Correct 361 ms 13336 KB Output is correct
20 Correct 457 ms 15188 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 604 KB Output is correct
2 Correct 4 ms 860 KB Output is correct
3 Correct 4 ms 860 KB Output is correct
4 Correct 5 ms 860 KB Output is correct
5 Correct 10 ms 1372 KB Output is correct
6 Correct 6 ms 1116 KB Output is correct
7 Correct 7 ms 1116 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 5 ms 904 KB Output is correct
11 Correct 393 ms 14676 KB Output is correct
12 Correct 440 ms 15292 KB Output is correct
13 Correct 515 ms 15060 KB Output is correct
14 Correct 491 ms 15116 KB Output is correct
15 Correct 509 ms 16924 KB Output is correct
16 Correct 567 ms 16468 KB Output is correct
17 Correct 655 ms 18860 KB Output is correct
18 Correct 335 ms 16224 KB Output is correct
19 Correct 361 ms 13336 KB Output is correct
20 Correct 457 ms 15188 KB Output is correct
21 Correct 550 ms 21368 KB Output is correct
22 Correct 618 ms 22936 KB Output is correct
23 Correct 1541 ms 43348 KB Output is correct
24 Correct 1369 ms 38344 KB Output is correct
25 Correct 1437 ms 51836 KB Output is correct
26 Execution timed out 2036 ms 65504 KB Time limit exceeded
27 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 604 KB Output is correct
2 Correct 4 ms 860 KB Output is correct
3 Correct 4 ms 860 KB Output is correct
4 Correct 5 ms 860 KB Output is correct
5 Correct 10 ms 1372 KB Output is correct
6 Correct 6 ms 1116 KB Output is correct
7 Correct 7 ms 1116 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 5 ms 904 KB Output is correct
11 Runtime error 230 ms 65536 KB Execution killed with signal 9
12 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 604 KB Output is correct
2 Correct 4 ms 860 KB Output is correct
3 Correct 4 ms 860 KB Output is correct
4 Correct 5 ms 860 KB Output is correct
5 Correct 10 ms 1372 KB Output is correct
6 Correct 6 ms 1116 KB Output is correct
7 Correct 7 ms 1116 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 5 ms 904 KB Output is correct
11 Correct 393 ms 14676 KB Output is correct
12 Correct 440 ms 15292 KB Output is correct
13 Correct 515 ms 15060 KB Output is correct
14 Correct 491 ms 15116 KB Output is correct
15 Correct 509 ms 16924 KB Output is correct
16 Correct 567 ms 16468 KB Output is correct
17 Correct 655 ms 18860 KB Output is correct
18 Correct 335 ms 16224 KB Output is correct
19 Correct 361 ms 13336 KB Output is correct
20 Correct 457 ms 15188 KB Output is correct
21 Correct 550 ms 21368 KB Output is correct
22 Correct 618 ms 22936 KB Output is correct
23 Correct 1541 ms 43348 KB Output is correct
24 Correct 1369 ms 38344 KB Output is correct
25 Correct 1437 ms 51836 KB Output is correct
26 Execution timed out 2036 ms 65504 KB Time limit exceeded
27 Halted 0 ms 0 KB -