oj.uz

Submission #771460

# Submission time Handle Problem Language Result Execution time Memory
771460 2023-07-03T03:34:53 Z vjudge1 Snake Escaping (JOI18_snake_escaping) C++17
22 / 100
 620 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<<21, M = 25;
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];
        }
        int mi = *min_element(cnt, cnt+3);
        if (cnt[2] == mi) cout << backtrack1(0, 0) << "\n";
        else if (cnt[1] == mi) 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 460 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 464 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 460 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 464 KB Output is correct
11 Correct 203 ms 6364 KB Output is correct
12 Correct 226 ms 6052 KB Output is correct
13 Correct 303 ms 5356 KB Output is correct
14 Correct 382 ms 5420 KB Output is correct
15 Correct 268 ms 6460 KB Output is correct
16 Correct 357 ms 5652 KB Output is correct
17 Correct 345 ms 5580 KB Output is correct
18 Correct 154 ms 7560 KB Output is correct
19 Correct 179 ms 4456 KB Output is correct
20 Correct 259 ms 6128 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 460 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 464 KB Output is correct
11 Correct 203 ms 6364 KB Output is correct
12 Correct 226 ms 6052 KB Output is correct
13 Correct 303 ms 5356 KB Output is correct
14 Correct 382 ms 5420 KB Output is correct
15 Correct 268 ms 6460 KB Output is correct
16 Correct 357 ms 5652 KB Output is correct
17 Correct 345 ms 5580 KB Output is correct
18 Correct 154 ms 7560 KB Output is correct
19 Correct 179 ms 4456 KB Output is correct
20 Correct 259 ms 6128 KB Output is correct
21 Correct 257 ms 7900 KB Output is correct
22 Correct 303 ms 8008 KB Output is correct
23 Correct 439 ms 7080 KB Output is correct
24 Correct 615 ms 6816 KB Output is correct
25 Correct 309 ms 8928 KB Output is correct
26 Correct 555 ms 7348 KB Output is correct
27 Correct 476 ms 7372 KB Output is correct
28 Correct 158 ms 9804 KB Output is correct
29 Correct 255 ms 5808 KB Output is correct
30 Correct 276 ms 8048 KB Output is correct
31 Correct 447 ms 7864 KB Output is correct
32 Correct 620 ms 7792 KB Output is correct
33 Correct 320 ms 6712 KB Output is correct
34 Correct 527 ms 6788 KB Output is correct
35 Correct 471 ms 7464 KB Output is correct
36 Correct 167 ms 5808 KB Output is correct
37 Correct 252 ms 7928 KB Output is correct
38 Correct 269 ms 5888 KB Output is correct
39 Correct 417 ms 7040 KB Output is correct
40 Correct 593 ms 6876 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 460 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 464 KB Output is correct
11 Runtime error 32 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 460 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 464 KB Output is correct
11 Correct 203 ms 6364 KB Output is correct
12 Correct 226 ms 6052 KB Output is correct
13 Correct 303 ms 5356 KB Output is correct
14 Correct 382 ms 5420 KB Output is correct
15 Correct 268 ms 6460 KB Output is correct
16 Correct 357 ms 5652 KB Output is correct
17 Correct 345 ms 5580 KB Output is correct
18 Correct 154 ms 7560 KB Output is correct
19 Correct 179 ms 4456 KB Output is correct
20 Correct 259 ms 6128 KB Output is correct
21 Correct 257 ms 7900 KB Output is correct
22 Correct 303 ms 8008 KB Output is correct
23 Correct 439 ms 7080 KB Output is correct
24 Correct 615 ms 6816 KB Output is correct
25 Correct 309 ms 8928 KB Output is correct
26 Correct 555 ms 7348 KB Output is correct
27 Correct 476 ms 7372 KB Output is correct
28 Correct 158 ms 9804 KB Output is correct
29 Correct 255 ms 5808 KB Output is correct
30 Correct 276 ms 8048 KB Output is correct
31 Correct 447 ms 7864 KB Output is correct
32 Correct 620 ms 7792 KB Output is correct
33 Correct 320 ms 6712 KB Output is correct
34 Correct 527 ms 6788 KB Output is correct
35 Correct 471 ms 7464 KB Output is correct
36 Correct 167 ms 5808 KB Output is correct
37 Correct 252 ms 7928 KB Output is correct
38 Correct 269 ms 5888 KB Output is correct
39 Correct 417 ms 7040 KB Output is correct
40 Correct 593 ms 6876 KB Output is correct
41 Runtime error 32 ms 65536 KB Execution killed with signal 9
42 Halted 0 ms 0 KB -