QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#380016#8512. Harmonic Operationsucup-team004#WA 1ms3660kbC++202.2kb2024-04-06 20:37:242024-04-06 20:37:25

Judging History

你现在查看的是最新测评结果

  • [2024-04-06 20:37:25]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3660kb
  • [2024-04-06 20:37:24]
  • 提交

answer

#include <bits/stdc++.h>

using i64 = long long;

struct G {
    int k = 1;
    int b = 0;
};

int N;
G operator*(G a, G b) {
    return {a.k * b.k, ((a.b * b.k + b.b) % N + N) % N};
}

std::vector<int> manacher(std::string s) {
    std::string t = "#";
    for (auto c : s) {
        t += c;
        t += '#';
    }
    int n = t.size();
    std::vector<int> r(n);
    for (int i = 0, j = 0; i < n; i++) {
        if (2 * j - i >= 0 && j + r[j] > i) {
            r[i] = std::min(r[2 * j - i], j + r[j] - i);
        }
        while (i - r[i] >= 0 && i + r[i] < n && t[i - r[i]] == t[i + r[i]]) {
            r[i] += 1;
        }
        if (i + r[i] > j + r[j]) {
            j = i;
        }
    }
    return r;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::string S;
    std::cin >> S;

    N = S.size();
    std::vector<int> f(N + 1);
    for (int i = 1, j = 0; i < N; i++) {
        while (j && S[i] != S[j]) {
            j = f[j];
        }
        j += (S[i] == S[j]);
        f[i + 1] = j;
    }
    if (N % (N - f[N]) == 0) {
        N = N - f[N];
        S.resize(N);
    }
    
    int axis = -1;
    auto r = manacher(S + S);
    for (int i = 0; i < N; i++) {
        if (r[i + i + N] > N) {
            axis = i;
            break;
        }
    }

    int K;
    std::cin >> K;

    std::vector<G> a(K);
    for (int i = 0; i < K; i++) {
        char x;
        std::cin >> x;

        if (x == 'I') {
            a[i] = {-1, 0};
        } else {
            int y;
            std::cin >> y;

            a[i] = {1, (x == 'L' ? (N - y % N) % N : y % N)};
        }
    }

    std::vector<G> pre(K + 1);
    pre[0] = {1, 0};
    for (int i = 0; i < K; i++) {
        pre[i + 1] = pre[i] * a[i];
    }

    i64 ans = 0;
    std::vector cnt(2, std::vector<int>(N));
    for (int i = K; i >= 0; i--) {
        auto v = pre[i];
        ans += cnt[v.k == -1][v.b];
        if (axis != -1) {
            v = v * G{-1, 2 * axis % N};
            ans += cnt[v.k == -1][v.b];
        }
        cnt[pre[i].k == -1][pre[i].b]++;
    }
    std::cout << ans << "\n";

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3620kb

input:

pda
2
R 2
L 2

output:

1

result:

ok 1 number(s): "1"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3636kb

input:

aaa
4
R 1
I
I
R 1

output:

10

result:

ok 1 number(s): "10"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3572kb

input:

caso
6
L 1
I
I
R 1
I
I

output:

4

result:

ok 1 number(s): "4"

Test #4:

score: 0
Accepted
time: 0ms
memory: 3660kb

input:

qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq
100
L 12
I
R 47
L 54
I
I
R 80
L 86
L 19
R 5
L 53
L 40
R 20
L 11
R 40
I
I
R 66
R 6
L 76
L 93
R 39
I
I
L 24
R 59
R 99
L 52
I
I
R 77
L 11
R 60
L 16
I
L 40
I
R 35
L 64
R 11
L 34
I
R 35
I
L 87
I
I
L 42
L ...

output:

5050

result:

ok 1 number(s): "5050"

Test #5:

score: -100
Wrong Answer
time: 0ms
memory: 3564kb

input:

wewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewe
100
R 83
R 34
I
I
R 87
R 74
L 98
I
L 77
L 8
R 23
L 94
I
I
L 79
L 87
L 47
L 85
L 49
L 7
I
I
R 97
R 15
I
R 66
L 8
R 62
R 68
I
I
R 32
R 24
R 36
L 60
R 75
R 77
I
L 42
I
L 61
I
I
R 78
R 51
L 98
I
L 77
I
I...

output:

1295

result:

wrong answer 1st numbers differ - expected: '2556', found: '1295'