oj.uz

Submission #702378

# Submission time Handle Problem Language Result Execution time Memory
702378 2023-02-23T20:31:21 Z bebra Snake Escaping (JOI18_snake_escaping) C++17
12 / 100
 2000 ms 9388 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 = 15;

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;
        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);
        }
    }

    int n = 1 << k;
    for (const auto& [shift, values] : shifts) {
        memset(dp, 0, sizeof(dp));

        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 < 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 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 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 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 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 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 203 ms 8240 KB Output is correct
12 Correct 249 ms 7832 KB Output is correct
13 Correct 166 ms 7084 KB Output is correct
14 Correct 177 ms 7168 KB Output is correct
15 Correct 245 ms 8220 KB Output is correct
16 Correct 194 ms 7412 KB Output is correct
17 Correct 186 ms 7340 KB Output is correct
18 Correct 1207 ms 9388 KB Output is correct
19 Correct 134 ms 6208 KB Output is correct
20 Correct 246 ms 7800 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 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 203 ms 8240 KB Output is correct
12 Correct 249 ms 7832 KB Output is correct
13 Correct 166 ms 7084 KB Output is correct
14 Correct 177 ms 7168 KB Output is correct
15 Correct 245 ms 8220 KB Output is correct
16 Correct 194 ms 7412 KB Output is correct
17 Correct 186 ms 7340 KB Output is correct
18 Correct 1207 ms 9388 KB Output is correct
19 Correct 134 ms 6208 KB Output is correct
20 Correct 246 ms 7800 KB Output is correct
21 Correct 327 ms 8168 KB Output is correct
22 Correct 410 ms 8548 KB Output is correct
23 Correct 198 ms 7372 KB Output is correct
24 Correct 191 ms 7292 KB Output is correct
25 Correct 454 ms 9272 KB Output is correct
26 Correct 231 ms 7708 KB Output is correct
27 Correct 239 ms 7684 KB Output is correct
28 Execution timed out 2073 ms 1216 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 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 77 ms 2416 KB Output is correct
12 Correct 161 ms 6036 KB Output is correct
13 Correct 18 ms 2416 KB Output is correct
14 Correct 28 ms 2416 KB Output is correct
15 Correct 448 ms 2416 KB Output is correct
16 Correct 33 ms 3840 KB Output is correct
17 Correct 285 ms 7956 KB Output is correct
18 Correct 34 ms 8964 KB Output is correct
19 Correct 14 ms 3760 KB Output is correct
20 Execution timed out 2072 ms 7816 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 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 203 ms 8240 KB Output is correct
12 Correct 249 ms 7832 KB Output is correct
13 Correct 166 ms 7084 KB Output is correct
14 Correct 177 ms 7168 KB Output is correct
15 Correct 245 ms 8220 KB Output is correct
16 Correct 194 ms 7412 KB Output is correct
17 Correct 186 ms 7340 KB Output is correct
18 Correct 1207 ms 9388 KB Output is correct
19 Correct 134 ms 6208 KB Output is correct
20 Correct 246 ms 7800 KB Output is correct
21 Correct 327 ms 8168 KB Output is correct
22 Correct 410 ms 8548 KB Output is correct
23 Correct 198 ms 7372 KB Output is correct
24 Correct 191 ms 7292 KB Output is correct
25 Correct 454 ms 9272 KB Output is correct
26 Correct 231 ms 7708 KB Output is correct
27 Correct 239 ms 7684 KB Output is correct
28 Execution timed out 2073 ms 1216 KB Time limit exceeded
29 Halted 0 ms 0 KB -