QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#363010#8512. Harmonic Operationsucup-team3215#WA 1ms3824kbC++172.1kb2024-03-23 17:53:232024-03-23 17:53:23

Judging History

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

  • [2024-03-23 17:53:23]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3824kb
  • [2024-03-23 17:53:23]
  • 提交

answer

#include <bits/stdc++.h>

using ll = signed long long int;

#define all(x) (x).begin(), (x).end()

using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;

using namespace std;

using vi = vector<int>;

vi z_func(const string& s) {
    int n = s.size();
    vi z(n);
    int l = 0, r = 0;
    for (int i = 1; i < n; ++i) {
        if (i < r) {
            z[i] = min(r - i - 1, z[i - l]);
        }
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
            ++z[i];
        }
        if (i + z[i] > r) {
            l = i, r = i + z[i];
        }
    }
    return z;
}

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

    string s;
    cin >> s;
    vi z = z_func(s);
    int n = s.size(), period = n;
    for (int i = 1; i < n; ++i) {
        if (n % i == 0 && i + z[i] == n) {
            period = i;
            break;
        }
    }
    string p(s.begin(), s.begin() + period);
    string pr(p.rbegin(), p.rend());
    int x = -1;
    vi z2 = z_func(p + "$" + pr + pr);
    for (int i = period + 1; i < z2.size(); ++i) {
        if (z2[i] == period) {
            x = i - period - 1;
            break;
        }
    }
    int q;
    cin >> q;
    vector<map<int, int>> cnt(2);
    cnt[0][0] = 1;
    int pref = 0;
    bool flag = 0;
    ll ans = 0;
    while (q--) {
        char c;
        cin >> c;
        if (c == 'I') {
            flag ^= 1;
        } else {
            int d;
            cin >> d;
            pref += (flag ^ (c == 'R') ? 1 : -1) * d;
            pref %= period;
            if (pref < 0) {
                pref += period;
            }
        }
        if (cnt[flag].count(pref)) {
            ans += cnt[flag][pref];
        }
        if (x != -1) {
            int di = ((flag ? x : -x) - pref) % period;
            if (di < 0) {
                di += period;
            }
            if (cnt[flag ^ 1].count(di)) {
                ans += cnt[flag ^ 1][di];
            }
        }
        ++cnt[flag][pref];
    }
    cout << ans << endl;
}

详细

Test #1:

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

input:

pda
2
R 2
L 2

output:

1

result:

ok 1 number(s): "1"

Test #2:

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

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: 3584kb

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: 3824kb

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: 0
Accepted
time: 0ms
memory: 3600kb

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:

2556

result:

ok 1 number(s): "2556"

Test #6:

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

input:

rtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtr
100
R 27
R 68
I
L 29
L 51
L 19
L 12
L 10
L 52
L 38
L 17
R 30
L 29
L 51
L 17
R 29
I
R 96
R 50
R 56
I
I
I
L 73
L 15
I
R 1
R 81
L 94
R 27
R 52
R 57
R 44
I
I
L 53
I
R 87
L 39
L 25
I
I
R 25
I
I
I
L 88
L ...

output:

58

result:

wrong answer 1st numbers differ - expected: '116', found: '58'