QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#710948	#9536. Athlete Welcome Ceremony	WA_automaton^#	RE	39ms	212676kb	C++23	4.6kb	2024-11-04 23:25:03	2024-11-04 23:25:03

Judging History

This is the latest submission verdict.

[2024-11-04 23:25:03]
Judged

Verdict: RE
Time: 39ms
Memory: 212676kb

Show

[2024-11-04 23:25:03]
Submitted

answer

#include <bits/stdc++.h>
#define int long long
#define x first
#define y second
#define pb push_back
void debug() {std::cerr << "\n";}
template<class T, class... OtherArgs>
void debug(T &&var, OtherArgs &&... args) {
    std::cerr << std::forward<T>(var) << " ";
    debug(std::forward<OtherArgs>(args)...);
}
#define SZ(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
using i64 = long long;
using u64 = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
constexpr int N = 210;
constexpr int P = 1e9 + 7;

void add(int &x, int y) {
    x += y;
    if (x >= P) {
        x -= P;
    }
}

int power(int a, int b, int p = P) {
    int res = 1 % p;
    for (; b; b /= 2, a = a * a % p) {
        if (b % 2) {
            res = res * a % p;
        }
    }
    return res;
}

int f[3][N][N][N], g[3][N][N][N];

void solve() {
    int n, q;
    cin >> n >> q;
    string s;
    cin >> s;

    int inv2 = power(2, P - 2);

    int m = 0;
    f[0][0][0][0] = f[1][0][0][0] = f[2][0][0][0] = 1;
    for (int i = 0; i < n; i++) {
        if (s[i] == '?') {
            m++;
            for (int x = 0; x <= m; x++) {
                for (int y = 0; x + y <= m; y++) {
                    int z = m - x - y;
                    g[0][x][y][z] = 0;
                    g[1][x][y][z] = 0;
                    g[2][x][y][z] = 0;
                }
            }
            for (int x = 0; x < m; x++) {
                for (int y = 0; x + y < m; y++) {
                    int z = m - 1 - x - y;
                    add(g[0][x + 1][y][z], f[1][x][y][z]);
                    add(g[0][x + 1][y][z], f[2][x][y][z]);
                    add(g[1][x][y + 1][z], f[0][x][y][z]);
                    add(g[1][x][y + 1][z], f[2][x][y][z]);
                    add(g[2][x][y][z + 1], f[0][x][y][z]);
                    add(g[2][x][y][z + 1], f[1][x][y][z]);
                    f[0][x][y][z] = f[1][x][y][z] = f[2][x][y][z] = 0;
                }
            }
        } else {
            for (int x = 0; x <= m; x++) {
                for (int y = 0; x + y <= m; y++) {
                    int z = m - x - y;
                    g[0][x][y][z] = 0;
                    g[1][x][y][z] = 0;
                    g[2][x][y][z] = 0;
                }
            }
            int t = s[i] - 'a';
            for (int x = 0; x <= m; x++) {
                for (int y = 0; x + y <= m; y++) {
                    int z = m - x - y;
                    add(g[t][x][y][z], f[(t + 1) % 3][x][y][z]);
                    add(g[t][x][y][z], f[(t + 2) % 3][x][y][z]);
                }
            }
        }
        for (int x = 0; x <= m; x++) {
            for (int y = 0; x + y <= m; y++) {
                int z = m - x - y;
                f[0][x][y][z] = g[0][x][y][z];
                f[1][x][y][z] = g[1][x][y][z];
                f[2][x][y][z] = g[2][x][y][z];
            }
        }
    }

    for (int t = 0; t < 3; t++) {
        for (int x = 1; x <= n; x++) {
            for (int y = 0; y <= n; y++) {
                for (int z = 0; z <= n; z++) {
                    add(f[t][x][y][z], f[t][x - 1][y][z]);
                }
            }
        }
        for (int x = 0; x <= n; x++) {
            for (int y = 1; y <= n; y++) {
                for (int z = 0; z <= n; z++) {
                    add(f[t][x][y][z], f[t][x][y - 1][z]);
                }
            }
        }
        for (int x = 0; x <= n; x++) {
            for (int y = 0; y <= n; y++) {
                for (int z = 1; z <= n; z++) {
                    add(f[t][x][y][z], f[t][x][y][z - 1]);
                }
            }
        }
    }

    // for (int x = 0; x <= n; x++) {
    //     for (int y = 0; y <= n; y++) {
    //         for (int z = 0; z <= n; z++) {
    //             debug("?", x, y, z, f[0][x][y][z], f[1][x][y][z], f[2][x][y][z]);
    //         }
    //     }
    // }

    while (q--) {
        int x, y, z;
        cin >> x >> y >> z;
        int ans = 0;
        if (s.back() == '?') {
            add(ans, f[0][x][y][z]);
            add(ans, f[1][x][y][z]);
            add(ans, f[2][x][y][z]);
        } else {
            ans = f[s.back() - 'a'][x][y][z];
        }
        cout << ans * inv2 % P << '\n';
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(20);
    int _ = 1;
    // cin >> _;
    while (_--) {
        solve();
    }
}

Source code, Language: C++23

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 0ms

memory: 18108kb

input:

6 3
a?b??c
2 2 2
1 1 1
1 0 2

output:

3
1
1

result:

ok 3 lines

Test #2:

score: 0

Accepted

time: 0ms

memory: 26328kb

input:

6 3
??????
2 2 2
2 3 3
3 3 3

output:

30
72
96

result:

ok 3 lines

Test #3:

score: 0

Accepted

time: 0ms

memory: 13824kb

input:

1 1
?
0 1 1

output:

result:

ok single line: '2'

Test #4:

score: 0

Accepted

time: 0ms

memory: 18476kb

input:

output:

result:

ok 10 lines

Test #5:

score: 0

Accepted

time: 0ms

memory: 22264kb

input:

output:

result:

ok 10 lines

Test #6:

score: 0

Accepted

time: 0ms

memory: 33272kb

input:

50 100
?abacbacab?cbcbcb?acabcbabcbcacbababc?caba?acacbca
8 3 8
2 4 8
8 7 3
0 9 2
10 8 7
7 6 5
4 10 2
6 9 3
3 6 6
9 10 8
2 5 8
8 1 0
3 5 0
1 0 6
5 0 8
6 5 5
1 7 9
7 7 10
4 7 5
6 6 4
10 1 2
4 1 7
10 0 8
7 6 3
1 9 1
4 7 2
8 4 0
8 6 1
5 10 4
5 8 2
5 8 4
4 5 9
5 2 1
1 10 9
4 10 1
8 4 3
8 9 9
8 0 1
0 8 0...

output:

result:

ok 100 lines

Test #7:

score: 0

Accepted

time: 4ms

memory: 80148kb

input:

50 100
b????????bca?????c?b??ca?acac?b?b???ca?ab???a?a???
35 43 36
12 49 47
7 11 34
38 44 22
42 17 10
49 8 38
18 26 44
6 18 14
28 29 6
48 32 47
29 15 48
1 5 33
24 17 18
10 27 32
19 10 34
2 23 9
14 24 39
46 12 34
9 49 26
21 8 46
43 43 3
31 16 2
8 27 7
24 41 35
17 25 31
0 13 47
24 31 23
33 40 30
36 39...

output:

result:

ok 100 lines

Test #8:

score: 0

Accepted

time: 19ms

memory: 72924kb

input:

100 1000
c?cbababcabacbacbacacbacabcbabababacababcbcab?cbabacbacbcbcacbab?bcabcbcababcacbabacbcb?babcbab?baca
13 11 4
4 17 20
14 5 2
16 14 15
8 12 17
19 5 11
5 17 12
20 7 6
19 10 1
6 5 0
13 1 9
7 17 1
20 4 16
11 12 18
19 2 16
18 1 11
19 16 3
7 1 0
6 9 16
6 9 16
6 20 7
0 16 20
1 2 8
16 5 20
18 14 18
...

output:

result:

ok 1000 lines

Test #9:

score: 0

Accepted

time: 39ms

memory: 212676kb

input:

100 1000
?????c??????????????????????????b???a????a?????????????????????????c????????????????????????????????
43 38 20
27 40 32
39 27 33
28 50 43
50 3 46
38 46 14
42 48 10
45 25 28
49 10 49
38 17 42
41 49 22
41 18 44
46 47 25
17 44 35
34 43 22
47 42 32
32 44 40
36 41 24
45 38 45
49 44 18
42 34 32
43...

output:

result:

ok 1000 lines

Test #10:

score: 0

Accepted

time: 24ms

memory: 113012kb

input:

100 1000
c???cacacbcab?cb?acb???ac?bab?bcbcbc?c?bcbcaba??b?ba?c?aca?a?bac?cbcbcba??ca?b????ac?baba?ab?cba?c?c
99 70 32
52 98 84
12 78 77
84 8 87
16 36 0
48 70 100
25 4 15
95 54 35
33 35 90
20 4 69
6 11 76
27 96 48
16 24 18
99 48 1
43 54 35
9 81 75
27 58 52
50 94 14
29 67 27
59 68 53
42 31 46
12 90 2...

output:

result:

ok 1000 lines

Test #11:

score: -100

Runtime Error

input:

300 100000
abcacacbabacbcababcacacb?babacbcbacbcababcbcbabcacbcbacacabacacacbacbcbcacbabacbcbcbabcacbababcabcabcabababacbcacbacabcbacbacacacbababababacbcababcbcacacbcbabacabcabababcabacbcbcbabcabacbabacacbcbcacacacbcabcbabcbcabababababcacabcabababcbcbcbcbcabacbabacbabcacbcababacacbcbababababcacacaba...