oj.uz

Submission #702382

# Submission time Handle Problem Language Result Execution time Memory
702382 2023-02-23T20:42:52 Z bebra Snake Escaping (JOI18_snake_escaping) C++17
12 / 100
 2000 ms 18220 KB 
#include <bits/stdc++.h>
using namespace std;

#define dbg(x) cerr << #x << ": " << x << endl;


constexpr int MAX_Q = 1e6 + 5;
constexpr int MAX_BIT = 20;
constexpr int MAX_N = 1 << 20;
constexpr int MAGIC = 11;

int ans[MAX_Q];
int dp[MAX_N];
int max_mask[MAX_N];


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

    int k, q;
    cin >> k >> q;

    string s;
    cin >> s;

    map<int, vector<pair<int, int>>> shifts;
    for (int j = 0; j < q; ++j) {
        string t;
        cin >> t;
        reverse(t.begin(), t.end());

        int mask = 0;
        int shift = 0;
        int bits_cnt = 0;
        for (int i = 0; i < k; ++i) {
            if (t[i] == '?') {
                mask |= 1 << i;
                ++bits_cnt;
            } else if (t[i] == '1') {
                shift |= 1 << i;
            }
        }

        if (bits_cnt <= MAGIC) {
            int res = s[shift] - '0';
            for (int submask = mask; submask > 0; submask = (submask - 1) & mask) {
                res += s[submask + shift] - '0';
            }
            ans[j] = res;
        } else {
            shifts[shift].emplace_back(mask, j);
            max_mask[shift] = max(max_mask[shift], __lg(mask) + 1);
        }
    }

    for (const auto& [shift, values] : shifts) {
        int n = 1 << max_mask[shift];

        for (int mask = 0; (mask | shift) < n; ++mask) {
            if ((mask & shift) == 0) {
                dp[mask] = s[mask | shift] - '0';
            }
        }

        for (int bit = 0; bit < k; ++bit) {
            if (shift & (1 << bit)) continue;

            for (int mask = 0; (mask | shift) < n; ++mask) {
                if ((mask & shift) != 0) continue;

                if (mask & (1 << bit)) {
                    dp[mask] += dp[mask ^ (1 << bit)];
                }
            }
        }

        for (const auto& [mask, idx] : values) {
            ans[idx] = dp[mask];
        }

        for (int mask = 0; (mask | shift) < n; ++mask) {
            dp[mask] = 0;
        }
    }

    for (int i = 0; i < q; ++i) {
        cout << ans[i] << '\n';
    }
    
    return 0;
}


/*
4
1
3141592653589793
?01?


*/

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 204 ms 8212 KB Output is correct
12 Correct 249 ms 7852 KB Output is correct
13 Correct 171 ms 7156 KB Output is correct
14 Correct 167 ms 7184 KB Output is correct
15 Correct 252 ms 8236 KB Output is correct
16 Correct 190 ms 7400 KB Output is correct
17 Correct 193 ms 7392 KB Output is correct
18 Correct 1222 ms 9168 KB Output is correct
19 Correct 134 ms 6232 KB Output is correct
20 Correct 256 ms 7964 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 204 ms 8212 KB Output is correct
12 Correct 249 ms 7852 KB Output is correct
13 Correct 171 ms 7156 KB Output is correct
14 Correct 167 ms 7184 KB Output is correct
15 Correct 252 ms 8236 KB Output is correct
16 Correct 190 ms 7400 KB Output is correct
17 Correct 193 ms 7392 KB Output is correct
18 Correct 1222 ms 9168 KB Output is correct
19 Correct 134 ms 6232 KB Output is correct
20 Correct 256 ms 7964 KB Output is correct
21 Correct 335 ms 8260 KB Output is correct
22 Correct 400 ms 8480 KB Output is correct
23 Correct 197 ms 7340 KB Output is correct
24 Correct 190 ms 7160 KB Output is correct
25 Correct 476 ms 9236 KB Output is correct
26 Correct 233 ms 7772 KB Output is correct
27 Correct 245 ms 7716 KB Output is correct
28 Correct 170 ms 18220 KB Output is correct
29 Correct 145 ms 6148 KB Output is correct
30 Incorrect 396 ms 8492 KB Output isn't correct
31 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 73 ms 2416 KB Output is correct
12 Correct 72 ms 6084 KB Output is correct
13 Correct 20 ms 2416 KB Output is correct
14 Correct 23 ms 2416 KB Output is correct
15 Execution timed out 2072 ms 10036 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 204 ms 8212 KB Output is correct
12 Correct 249 ms 7852 KB Output is correct
13 Correct 171 ms 7156 KB Output is correct
14 Correct 167 ms 7184 KB Output is correct
15 Correct 252 ms 8236 KB Output is correct
16 Correct 190 ms 7400 KB Output is correct
17 Correct 193 ms 7392 KB Output is correct
18 Correct 1222 ms 9168 KB Output is correct
19 Correct 134 ms 6232 KB Output is correct
20 Correct 256 ms 7964 KB Output is correct
21 Correct 335 ms 8260 KB Output is correct
22 Correct 400 ms 8480 KB Output is correct
23 Correct 197 ms 7340 KB Output is correct
24 Correct 190 ms 7160 KB Output is correct
25 Correct 476 ms 9236 KB Output is correct
26 Correct 233 ms 7772 KB Output is correct
27 Correct 245 ms 7716 KB Output is correct
28 Correct 170 ms 18220 KB Output is correct
29 Correct 145 ms 6148 KB Output is correct
30 Incorrect 396 ms 8492 KB Output isn't correct
31 Halted 0 ms 0 KB -