QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#369805#8512. Harmonic OperationswillowWA 3ms10152kbC++174.0kb2024-03-28 18:07:572024-03-28 18:07:58

Judging History

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

  • [2024-03-28 18:07:58]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:10152kb
  • [2024-03-28 18:07:57]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 4e5 + 5;
char s[maxn], t[maxn];
int n, k;
int Check(int x) {
    for(int i = 1; i <= n; ++ i) {
        if(s[i] != s[(i + x - 1) % n + 1]) {
            return 0;
        }
    }
    return 1;
}
int sh = -1, g;
struct Arr {
    int del, rev, who, cnt[maxn];
    void Init(int _who) {
        del = rev = 0;
        who = _who;
        fill(cnt, cnt + maxn, 0);
    }
    void Reverse() {
        rev ^= 1;
        who ^= 1;
    }
    void Left(int w) {
        if(rev) {
            del += w;
        }
        else {
            del -= w;
        }
    }
    void Right(int w) {
        if(rev) {
            del -= w;
        }
        else {
            del += w;
        }
    }
    void Add(int x) {
// cerr << "Add delta = " << del << " rev = " << rev << " who = " << who << " x = " << x << endl;
        if(rev) {
            ++ cnt[((-(del + x)) % g + g) % g];
        }
        else {
            ++ cnt[((x - del) % g + g) % g];
        }
    }
    int Query() {
        int tar = 0;
        if(who) {
            if(sh == -1)
                return 0;
            tar = sh;
        }
// cerr << "Query tar = " << tar << endl;
        if(rev) {
// cerr << "pos = " << (((-(del + tar)) % g + g) % g) << " " << cnt[((-(del + tar)) % g + g) % g] << endl;
            return cnt[((-(del + tar)) % g + g) % g];
        }
        else {
// cerr << "pos = " << (((tar - del) % g + g) % g) << " " << cnt[((tar - del) % g + g) % g] << endl;
            return cnt[((tar - del) % g + g) % g];
        }
    }
}a[2];
char op[5];
int fail[maxn];
main() {
    scanf("%s", s + 1);
    n = strlen(s + 1);
    g = n;
    for(int i = 1; i * i <= n; ++ i) {
        if(n % i == 0) {
            if(Check(i)) {
                g = min(g, i);
            }
            if(Check(n / i)) {
                g = min(g, n / i);
            }
        }
    }
    for(int i = 1; i <= n; ++ i) {
        t[i + n] = t[i] = s[n - i + 1];
    }
    fail[1] = 0;
    int p = 0;
    for(int i = 2; i <= n; ++ i) {
        while(p && s[i] != s[p + 1])
            p = fail[p];
        if(s[i] == s[p + 1])
            ++ p;
        fail[i] = p;
    }
    int now = 0;
    for(int i = 1; i <= 2 * n; ++ i) {
        while(now && t[i] != s[now + 1])
            now = fail[now];
        if(t[i] == s[now + 1])
            ++ now;
// cerr << i << " " << now << endl;
        if(now == n) {
            sh = i - n;
            break;
        }
    }
// cerr << g << " " << sh << endl;
    a[0].Init(0), a[1].Init(1);
    scanf("%lld", &k);
    long long ans = 0;
    for(int i = 1, w; i <= k; ++ i) {
        scanf("%s", op + 1);
        if(op[1] == 'I') { // reverse
            a[0].Reverse();
            a[1].Reverse();
            if(a[0].who)
                a[0].Add(0);
            else
                a[1].Add(0);
        }
        else {
            scanf("%lld", &w);
            if(op[1] == 'L') { // to_left w
                a[0].Left(w);
                a[1].Left(w);
                if(!a[0].who)
                    a[0].Add(g - w);
                else
                    a[1].Add(g - w);
            }
            else { // to_right w
                a[0].Right(w);
                a[1].Right(w);
                if(!a[0].who)
                    a[0].Add(w);
                else
                    a[1].Add(w);
            }
        }
// cerr << "a[0]: rev = " << a[0].rev << " delta = " << a[0].del << " who = " << a[0].who << ": ";
// for(int i = 0; i < g; ++ i)
//     cerr << a[0].cnt[i] << " ";
// cerr << endl;
// cerr << "a[1]: rev = " << a[1].rev << " delta = " << a[1].del << " who = " << a[1].who << ": ";
// for(int i = 0; i < g; ++ i)
//     cerr << a[1].cnt[i] << " ";
// cerr << endl;
        ans += a[0].Query();
        ans += a[1].Query();
// cerr << "? Right = " << i << " ans = " << ans << endl;
    }
    printf("%lld\n", ans);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 10064kb

input:

pda
2
R 2
L 2

output:

1

result:

ok 1 number(s): "1"

Test #2:

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

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

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

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: 3ms
memory: 10136kb

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

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:

116

result:

ok 1 number(s): "116"

Test #7:

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

input:

tcldtcldtcldtcldtcldtcldtcldtcldtcld
100
L 20
I
I
I
L 20
R 13
L 16
L 19
R 10
I
I
I
L 11
R 30
R 30
I
L 35
I
L 28
R 23
R 24
L 20
R 15
I
I
L 13
I
R 1
I
R 6
I
I
L 22
I
L 22
R 22
L 30
L 30
I
I
I
R 35
I
R 3
L 1
R 4
I
R 11
R 2
R 21
R 15
I
R 5
L 2
L 4
L 7
L 19
L 29
R 8
I
L 24
I
I
I
L 29
I
R 35
R 32
I
R 14
L...

output:

703

result:

ok 1 number(s): "703"

Test #8:

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

input:

wflbkhwflbkhwflbkhwflbkhwflbkhwflbkh
100
I
R 28
R 13
R 7
R 29
I
I
I
R 25
R 10
R 23
I
R 26
I
I
L 18
I
R 18
L 6
I
I
R 8
R 8
I
R 6
L 16
I
R 2
R 17
L 31
R 31
L 22
R 26
L 21
L 20
R 10
L 13
R 33
R 13
R 35
R 22
L 2
L 4
R 19
L 32
L 25
I
L 31
R 10
R 17
R 15
L 6
L 9
R 31
R 20
I
I
R 4
I
L 30
L 30
L 2
R 18
R 35...

output:

442

result:

ok 1 number(s): "442"

Test #9:

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

input:

mzgaokjwpmzgaokjwpmzgaokjwpmzgaokjwp
100
R 10
I
L 24
L 8
I
L 19
L 25
I
I
R 27
R 24
I
I
L 16
I
I
L 35
R 14
I
L 23
R 17
R 16
R 4
R 4
L 29
I
R 11
R 9
R 15
I
L 18
I
I
L 25
R 13
L 24
I
I
L 8
I
I
I
I
L 24
I
I
L 19
L 23
I
L 20
R 35
L 31
I
I
R 27
I
I
I
L 35
R 16
L 10
R 28
R 14
I
I
R 30
R 18
L 16
L 6
L 12
R ...

output:

280

result:

ok 1 number(s): "280"

Test #10:

score: 0
Accepted
time: 3ms
memory: 10036kb

input:

gtvcymjngzntgtvcymjngzntgtvcymjngznt
100
L 33
L 5
R 31
R 18
I
R 14
R 9
L 1
I
R 1
R 15
L 15
I
I
I
L 13
R 7
I
I
L 2
I
L 3
I
L 19
L 22
L 2
R 32
I
L 1
R 24
R 23
I
R 25
L 11
R 34
R 25
I
L 25
R 22
R 34
I
I
L 2
R 13
L 3
I
L 30
I
R 7
R 20
I
R 24
L 34
R 23
I
L 26
R 22
I
I
I
R 17
I
I
L 14
R 27
R 35
I
L 34
L 3...

output:

206

result:

ok 1 number(s): "206"

Test #11:

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

input:

dvaauyemcqhrmduoumdvaauyemcqhrmduoum
100
L 21
R 12
R 30
L 13
I
I
L 1
L 31
R 4
L 20
I
L 6
I
L 29
R 19
L 12
R 25
R 25
I
R 21
I
L 12
L 25
R 35
L 8
R 7
R 29
I
R 4
L 24
R 29
I
I
I
L 12
L 24
R 19
L 33
L 4
I
R 35
I
R 16
I
R 10
I
R 18
R 7
L 33
I
I
R 22
L 16
L 7
L 20
R 32
I
I
R 27
I
L 9
R 16
I
I
R 32
I
R 1
L...

output:

180

result:

ok 1 number(s): "180"

Test #12:

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

input:

pkmsckbnjeeojagpdtfxlmlgofbrygcuqiahynrwooxgdruurdgxoowrnyhaiqucgyrbfoglmlxftdpgajoeejnbkcsmkplhxxhl
100
L 14
R 54
L 88
L 66
L 38
R 91
I
I
I
I
R 56
L 4
L 76
R 12
L 86
I
I
I
I
R 52
L 98
L 98
L 39
R 60
L 14
R 23
R 92
R 99
L 71
I
I
I
I
L 1
R 33
I
R 65
L 72
I
I
I
R 20
R 48
L 81
L 7
I
R 72
R 14
I
I
R 10
...

output:

82

result:

wrong answer 1st numbers differ - expected: '75', found: '82'