oj.uz

Submission #702386

# Submission time Handle Problem Language Result Execution time Memory
702386 2023-02-23T20:59:46 Z bebra Snake Escaping (JOI18_snake_escaping) C++17
22 / 100
 2000 ms 23816 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 = 6;

int ans[MAX_Q];
int dp[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;
        for (int i = 0; i < k; ++i) {
            if (t[i] == '?') {
                mask |= 1 << i;
            } else if (t[i] == '1') {
                shift |= 1 << i;
            }
        }
        shifts[shift].emplace_back(mask, j);
    }

    for (const auto& [shift, values] : shifts) {
        if (values.size() >= MAGIC) {
            int total_mask = ((1 << k) - 1) & (~shift);

            dp[0] = s[shift] - '0';
            for (int mask = total_mask; mask > 0; mask = (mask - 1) & total_mask) {
                dp[mask] = s[mask | shift] - '0';
            }

            for (int bit = 0; bit < k; ++bit) {
                if (shift & (1 << bit)) continue;
                for (int mask = total_mask; mask > 0; mask = (mask - 1) & total_mask) {
                    if (mask & (1 << bit)) {
                        dp[mask] += dp[mask ^ (1 << bit)];
                    }
                }
            }

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

            for (int mask = total_mask; mask > 0; mask = (mask - 1) & total_mask) {
                dp[mask] = 0;
            }

        } else {
            for (const auto& [mask, idx] : values) {
                ans[idx] = s[shift] - '0';
                for (int submask = mask; submask > 0; submask = (submask - 1) & mask) {
                    ans[idx] += s[submask | shift] - '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 1 ms 340 KB Output is correct
9 Correct 1 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 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 224 ms 17244 KB Output is correct
12 Correct 205 ms 15808 KB Output is correct
13 Correct 225 ms 17424 KB Output is correct
14 Correct 237 ms 19748 KB Output is correct
15 Correct 228 ms 20264 KB Output is correct
16 Correct 247 ms 19360 KB Output is correct
17 Correct 255 ms 20124 KB Output is correct
18 Correct 146 ms 17216 KB Output is correct
19 Correct 223 ms 15244 KB Output is correct
20 Correct 246 ms 17684 KB Output is correct

Subtask #3
10.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 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 224 ms 17244 KB Output is correct
12 Correct 205 ms 15808 KB Output is correct
13 Correct 225 ms 17424 KB Output is correct
14 Correct 237 ms 19748 KB Output is correct
15 Correct 228 ms 20264 KB Output is correct
16 Correct 247 ms 19360 KB Output is correct
17 Correct 255 ms 20124 KB Output is correct
18 Correct 146 ms 17216 KB Output is correct
19 Correct 223 ms 15244 KB Output is correct
20 Correct 246 ms 17684 KB Output is correct
21 Correct 268 ms 23816 KB Output is correct
22 Correct 218 ms 16372 KB Output is correct
23 Correct 325 ms 19020 KB Output is correct
24 Correct 275 ms 19660 KB Output is correct
25 Correct 283 ms 20512 KB Output is correct
26 Correct 351 ms 20904 KB Output is correct
27 Correct 354 ms 21272 KB Output is correct
28 Correct 163 ms 18180 KB Output is correct
29 Correct 245 ms 21580 KB Output is correct
30 Correct 396 ms 21836 KB Output is correct
31 Correct 366 ms 20176 KB Output is correct
32 Correct 263 ms 20256 KB Output is correct
33 Correct 254 ms 18716 KB Output is correct
34 Correct 409 ms 20192 KB Output is correct
35 Correct 344 ms 21248 KB Output is correct
36 Correct 163 ms 14184 KB Output is correct
37 Correct 204 ms 16188 KB Output is correct
38 Correct 330 ms 19744 KB Output is correct
39 Correct 279 ms 22836 KB Output is correct
40 Correct 286 ms 18764 KB Output is correct

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 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 207 ms 6500 KB Output is correct
12 Correct 41 ms 6752 KB Output is correct
13 Execution timed out 2078 ms 9188 KB Time limit exceeded
14 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 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 224 ms 17244 KB Output is correct
12 Correct 205 ms 15808 KB Output is correct
13 Correct 225 ms 17424 KB Output is correct
14 Correct 237 ms 19748 KB Output is correct
15 Correct 228 ms 20264 KB Output is correct
16 Correct 247 ms 19360 KB Output is correct
17 Correct 255 ms 20124 KB Output is correct
18 Correct 146 ms 17216 KB Output is correct
19 Correct 223 ms 15244 KB Output is correct
20 Correct 246 ms 17684 KB Output is correct
21 Correct 268 ms 23816 KB Output is correct
22 Correct 218 ms 16372 KB Output is correct
23 Correct 325 ms 19020 KB Output is correct
24 Correct 275 ms 19660 KB Output is correct
25 Correct 283 ms 20512 KB Output is correct
26 Correct 351 ms 20904 KB Output is correct
27 Correct 354 ms 21272 KB Output is correct
28 Correct 163 ms 18180 KB Output is correct
29 Correct 245 ms 21580 KB Output is correct
30 Correct 396 ms 21836 KB Output is correct
31 Correct 366 ms 20176 KB Output is correct
32 Correct 263 ms 20256 KB Output is correct
33 Correct 254 ms 18716 KB Output is correct
34 Correct 409 ms 20192 KB Output is correct
35 Correct 344 ms 21248 KB Output is correct
36 Correct 163 ms 14184 KB Output is correct
37 Correct 204 ms 16188 KB Output is correct
38 Correct 330 ms 19744 KB Output is correct
39 Correct 279 ms 22836 KB Output is correct
40 Correct 286 ms 18764 KB Output is correct
41 Correct 207 ms 6500 KB Output is correct
42 Correct 41 ms 6752 KB Output is correct
43 Execution timed out 2078 ms 9188 KB Time limit exceeded
44 Halted 0 ms 0 KB -