oj.uz

Submission #771463

# Submission time Handle Problem Language Result Execution time Memory
771463 2023-07-03T03:42:14 Z vjudge1 Snake Escaping (JOI18_snake_escaping) C++17
22 / 100
 949 ms 65536 KB 
// #cheat_when_I_was_young
// #cheatkhitacontre #khionhatoicheat
// #thaycuckythatvong
#include "bits/stdc++.h"
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
const int N = 1<<20, M = 21;
int n, q, dp[N][M], sup[N][M];
string s, t;
int backtrack1(int idx, int num) {
    if (idx == n) return s[num];
    if (t[idx] == '0') return backtrack1(idx+1, num);
    if (t[idx] == '1') return backtrack1(idx+1, num | (1<<idx));
    return backtrack1(idx+1, num) + backtrack1(idx+1, num | (1<<idx));
}
int backtrack2(int idx, int num, int change) {
    if (idx == n) {
        if (change % 2) return -dp[num][0];
        return dp[num][0];
    }
    if (t[idx] == '0') return backtrack2(idx+1, num, change);
    if (t[idx] == '?') return backtrack2(idx+1, num | (1<<idx), change);
    return backtrack2(idx+1, num, change+1) + backtrack2(idx+1, num | (1<<idx), change);
}
int backtrack3(int idx, int num, int change) {
    if (idx == n) {
        if (change % 2) return -sup[num][0];
        return sup[num][0];
    }
    if (t[idx] == '1') return backtrack3(idx+1, num | (1<<idx), change);
    if (t[idx] == '?') return backtrack3(idx+1, num, change);
    return backtrack3(idx+1, num, change) + backtrack3(idx+1, num | (1<<idx), change+1);
}
signed main() {
	IOS;
    cin >> n >> q >> s;
    for (int mask = 0; mask < 1<<n; ++mask) {
        s[mask] -= '0';
        dp[mask][n] = sup[mask][n] = s[mask];
    }
    for (int mask = 0; mask < 1<<n; ++mask) for (int i = n-1; i >= 0; --i) {
        dp[mask][i] = dp[mask][i+1];
        if (mask & (1<<i)) dp[mask][i] += dp[mask^(1<<i)][i+1];
    }
    for (int mask = (1<<n)-1; mask >= 0; --mask) for (int i = n-1; i >= 0; --i) {
        sup[mask][i] = sup[mask][i+1];
        if (!(mask & (1<<i))) sup[mask][i] += sup[mask^(1<<i)][i+1];
    }
    while (q--) {
        cin >> t;
        reverse(t.begin(), t.end());
        int cnt[] = {0, 0, 0};
        for (char &c: t) {
            if (c == '0') ++cnt[0];
            else if (c == '1') ++cnt[1];
            else ++cnt[2];
        }
        if (cnt[2] <= 6) cout << backtrack1(0, 0) << "\n";
        else if (cnt[1] <= 6) cout << backtrack2(0, 0, 0) << "\n";
        else cout << backtrack3(0, 0, 0) << "\n";
    }
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 404 ms 4400 KB Output is correct
12 Correct 388 ms 4136 KB Output is correct
13 Correct 352 ms 3400 KB Output is correct
14 Correct 367 ms 3492 KB Output is correct
15 Correct 719 ms 4524 KB Output is correct
16 Correct 448 ms 3672 KB Output is correct
17 Correct 431 ms 3588 KB Output is correct
18 Correct 141 ms 5428 KB Output is correct
19 Correct 167 ms 2444 KB Output is correct
20 Correct 439 ms 4056 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 404 ms 4400 KB Output is correct
12 Correct 388 ms 4136 KB Output is correct
13 Correct 352 ms 3400 KB Output is correct
14 Correct 367 ms 3492 KB Output is correct
15 Correct 719 ms 4524 KB Output is correct
16 Correct 448 ms 3672 KB Output is correct
17 Correct 431 ms 3588 KB Output is correct
18 Correct 141 ms 5428 KB Output is correct
19 Correct 167 ms 2444 KB Output is correct
20 Correct 439 ms 4056 KB Output is correct
21 Correct 907 ms 5660 KB Output is correct
22 Correct 437 ms 5788 KB Output is correct
23 Correct 568 ms 4800 KB Output is correct
24 Correct 585 ms 4664 KB Output is correct
25 Correct 400 ms 6592 KB Output is correct
26 Correct 636 ms 5268 KB Output is correct
27 Correct 630 ms 5100 KB Output is correct
28 Correct 164 ms 7596 KB Output is correct
29 Correct 228 ms 3648 KB Output is correct
30 Correct 691 ms 5804 KB Output is correct
31 Correct 949 ms 5780 KB Output is correct
32 Correct 745 ms 5712 KB Output is correct
33 Correct 361 ms 4564 KB Output is correct
34 Correct 599 ms 4700 KB Output is correct
35 Correct 628 ms 5148 KB Output is correct
36 Correct 147 ms 3636 KB Output is correct
37 Correct 733 ms 5688 KB Output is correct
38 Correct 247 ms 3620 KB Output is correct
39 Correct 534 ms 4864 KB Output is correct
40 Correct 588 ms 4600 KB Output is correct

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Runtime error 28 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 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 404 ms 4400 KB Output is correct
12 Correct 388 ms 4136 KB Output is correct
13 Correct 352 ms 3400 KB Output is correct
14 Correct 367 ms 3492 KB Output is correct
15 Correct 719 ms 4524 KB Output is correct
16 Correct 448 ms 3672 KB Output is correct
17 Correct 431 ms 3588 KB Output is correct
18 Correct 141 ms 5428 KB Output is correct
19 Correct 167 ms 2444 KB Output is correct
20 Correct 439 ms 4056 KB Output is correct
21 Correct 907 ms 5660 KB Output is correct
22 Correct 437 ms 5788 KB Output is correct
23 Correct 568 ms 4800 KB Output is correct
24 Correct 585 ms 4664 KB Output is correct
25 Correct 400 ms 6592 KB Output is correct
26 Correct 636 ms 5268 KB Output is correct
27 Correct 630 ms 5100 KB Output is correct
28 Correct 164 ms 7596 KB Output is correct
29 Correct 228 ms 3648 KB Output is correct
30 Correct 691 ms 5804 KB Output is correct
31 Correct 949 ms 5780 KB Output is correct
32 Correct 745 ms 5712 KB Output is correct
33 Correct 361 ms 4564 KB Output is correct
34 Correct 599 ms 4700 KB Output is correct
35 Correct 628 ms 5148 KB Output is correct
36 Correct 147 ms 3636 KB Output is correct
37 Correct 733 ms 5688 KB Output is correct
38 Correct 247 ms 3620 KB Output is correct
39 Correct 534 ms 4864 KB Output is correct
40 Correct 588 ms 4600 KB Output is correct
41 Runtime error 28 ms 65536 KB Execution killed with signal 9
42 Halted 0 ms 0 KB -