QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#363618#8512. Harmonic OperationsGeorgia Tech: Days of Future Past (Jingbang Chen, Yu Gao)#WA 24ms6916kbC++234.1kb2024-03-24 00:59:282024-03-24 00:59:29

Judging History

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

  • [2024-03-24 00:59:29]
  • 评测
  • 测评结果:WA
  • 用时:24ms
  • 内存:6916kb
  • [2024-03-24 00:59:28]
  • 提交

answer

#pragma GCC optimize("O3,unroll-loops")
#include<bits/stdc++.h>
using namespace std;
const int inf = 1e9 + 7;
typedef long long LL;
typedef unsigned long long ULL;
#define fi first
#define se second
#define all(x) ((x).begin()), ((x).end())
#define pb push_back
typedef double D;
const int N = 200011;
int tp[N], d[N], nxt[N];
pair<string, int> find(string s) {
    int i, j, k, l, n = s.length();
    s += s;
    for(i = 0, j = 1; j < n; ) {
        for(k = 0; k < n && s[i + k] == s[j + k]; k++);
        if(k >= n) break;
        if(s[i + k] < s[j + k]) {
            j += k + 1;
        }
        else l = i + k, i = j, j = max(l, j) + 1;
    }
    return make_pair(s.substr(i, n), i);
    
}
struct Op {
    int coe, delta;
    void print() const {
        printf("c = %d, d = %d\n", coe, delta);
    }
};
int per;
Op operator + (const Op & a, const Op & b) {
    return Op{a.coe * b.coe, (a.delta * b.coe % per + b.delta + per) % per};
}
bool operator < (const Op & a, const Op & b) {
    return a.coe < b.coe || a.coe == b.coe && a.delta < b.delta;
}
int main() {
    string s;
    cin >> s;
    int n = s.size();
    int k;
    scanf("%d", &k);
    for(int i = 0; i < k; i++) {
        static char st[11];
        scanf("%s", st);
        tp[i] = st[0];
        //printf("tp[%d] = %c\n", i, tp[i]);
        if(tp[i] != 'I') {
            scanf("%d", &d[i]);
            if(tp[i] == 'L') {
                d[i] = d[i] % n;
            }else {
                d[i] = (-d[i] + n) % n;
            }
        }
    }
    int revdelta = -1;
    string t = s;
    reverse(all(t));
    pair<string, int> ms = find(s), mt = find(t);
    if(ms.first == mt.first) {
        revdelta = ms.se - mt.se;
    }
    s = '$' + s;
    nxt[0] = -1;
    for(int i = 1; i <= n; i++) {
        int p = nxt[i - 1];
        while(p != -1 && s[p + 1] != s[i]) {
            //printf("p = %d\n", p);
            p = nxt[p];
        }
        nxt[i] = p + 1;
    }
    per = n - nxt[n];
    if(n % per != 0) {
        per = n;
    }
    LL ans = 0;
    //printf("per = %d, revdelta = %d\n", per, revdelta);
    if(revdelta == -1) {
        Op cur{1, 0};
        map<Op, int> cnt;
        cnt[cur] = 1;
        for(int i = 0; i < k; i++) {
            Op opi;
            if(tp[i] == 'I') {
                opi = Op{-1, 0};
            } else {
                opi = Op{1, d[i] % per};
            }
            cur = cur + opi;
            //cur.print();
            ans += cnt[cur];
            cnt[cur]++;
        }
        /*for(int i = 0, j; i < k; i = j) {
            if(tp[i] == 'I') {
                j = i + 1;
                continue;
            }
            for(j = i; tp[j] != 'I'; j++);
            map<int, int> cnt;
            cnt[0] = 1;
            int cur = 0;
            for(int k = i; k < j; k++) {
                cur = (cur + d[k]) % per;
                ans += cnt[cur];
                cnt[cur]++;
            }
        }*/
    } else {
        /*if(per == 1) {
            ans = (k * (k + 1ll) / 2);
        } else */
        /*{
            map<int, int> cnt;
            cnt[0] = 1;
            int cur = 0;
            for(int i = 0; i < k; i++) {
                if(tp[i] == 'I') {
                    cur = (per - cur + revdelta) % per;
                } else {
                    cur = (cur + d[i]) % per;
                }
                ans += cnt[cur];
                cnt[cur]++;
            }
        }*/
        Op cur{1, 0};
        map<Op, int> cnt;
        cnt[cur] = 1;
        revdelta %= per;
        for(int i = 0; i < k; i++) {
            Op opi;
            if(tp[i] == 'I') {
                opi = Op{-1, revdelta};
            } else {
                opi = Op{1, d[i] % per};
            }
            cur = cur + opi;
            //cur.print();
            //cur.print();
            ans += cnt[cur];
            //printf("ans = %d\n",ans);
            ans += cnt[Op{-cur.coe, (per - cur.delta) % per}];
            //printf("ans = %d\n",ans);
            cnt[cur]++;
        }
    }
    printf("%lld\n", ans);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3800kb

input:

pda
2
R 2
L 2

output:

1

result:

ok 1 number(s): "1"

Test #2:

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

input:

aaa
4
R 1
I
I
R 1

output:

10

result:

ok 1 number(s): "10"

Test #3:

score: 0
Accepted
time: 1ms
memory: 5836kb

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

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

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

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: 1ms
memory: 5916kb

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

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

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: 0ms
memory: 4112kb

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: 1ms
memory: 4056kb

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

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:

75

result:

ok 1 number(s): "75"

Test #13:

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

input:

txgcggvgarkkflejgkaukutnsjogrglpdmocuhyiboientoffaaaffotneiobiyhucomdplgrgojsntukuakgjelfkkragvggcgxt
100
R 35
R 84
I
R 68
R 24
L 42
L 24
R 16
R 80
R 95
L 9
L 26
L 96
R 64
I
R 56
I
L 5
R 83
R 2
R 57
R 28
I
R 17
I
R 11
I
R 100
L 42
I
L 89
I
L 91
I
I
R 78
I
R 30
L 6
I
L 56
L 48
R 79
L 8
I
R 5
L 25
R 2...

output:

76

result:

ok 1 number(s): "76"

Test #14:

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

input:

qhygenaiejhluibjfyjbdoslylsodbjyfjbiulhjeianegyhqydgoxbmbcuslmfqgraeqkpuerbnbreupkqeargqfmlsucbmbxogdy
100
L 41
R 73
R 41
I
R 59
R 77
I
I
R 21
L 5
R 30
R 3
L 94
I
L 36
R 2
R 85
L 39
L 17
R 47
I
R 86
L 30
R 38
R 80
I
R 39
I
I
L 99
I
L 15
I
L 76
L 68
L 91
I
R 71
R 36
L 14
L 15
I
L 63
R 71
I
L 38
I
R 3...

output:

48

result:

ok 1 number(s): "48"

Test #15:

score: 0
Accepted
time: 19ms
memory: 6916kb

input:

yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy...

output:

20000100000

result:

ok 1 number(s): "20000100000"

Test #16:

score: 0
Accepted
time: 24ms
memory: 6912kb

input:

uuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu...

output:

20000100000

result:

ok 1 number(s): "20000100000"

Test #17:

score: 0
Accepted
time: 14ms
memory: 6900kb

input:

iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii...

output:

20000100000

result:

ok 1 number(s): "20000100000"

Test #18:

score: -100
Wrong Answer
time: 19ms
memory: 6892kb

input:

opopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopop...

output:

4999995412

result:

wrong answer 1st numbers differ - expected: '10000007832', found: '4999995412'