QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#376157#8512. Harmonic Operationsinstallb#WA 0ms3952kbC++202.0kb2024-04-03 22:12:192024-04-03 22:12:20

Judging History

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

  • [2024-04-03 22:12:20]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3952kb
  • [2024-04-03 22:12:19]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define M 200005
char S[M];
int q,n,P;
struct Node{
    int k,flg;
    Node(){}
    Node(int a,int b):k(a),flg(b){}
    Node Add(int kx){
        return Node((k+kx)%P,flg);
    }
    Node rev(){
        return Node((n-k)%P,!flg);
    }
    bool operator < (const Node &res)const{
        return k<res.k || k == res.k && flg < res.flg;
    }
    void print(){
        cout<<flg<<' '<<k<<endl;
    }
}A[M];
int Ask_per(){
    static int f[M];
    f[1]=0;
    for(int i=2,j=0;i<=n;i++){
        while(j && S[j+1]!=S[i])j=f[j];
        if(S[j+1]==S[i])j++;
        f[i]=j;
    }
    if(n%(n-f[n]) == 0)return n-f[n];
    else return n;
}
using ull = unsigned long long;
int Ask_K(){
    const int BS=37;
    ull pw = 1;
    for(int i=1;i<=n;i++)pw *= BS;
    ull bs = 0;
    for(int i=1;i<=n;i++)bs = BS*bs+S[i]-'a'+1;
    reverse(S+1,S+1+n);
    ull now = 0;
    for(int i=1;i<=n;i++)now = BS*now+S[i]-'a'+1;
    if(now == bs)return 0;
    for(int i=1;i<=n;i++){
        now *= bs;
        now -= pw * (S[i]-'a'+1);
        now += S[i];
        if(now == bs)return i;
    }
    return -1;
}
using ll = long long;
int main(){
    scanf("%s",S+1);
    n=strlen(S+1);
    cin>>q;
    P = Ask_per();
    Node t = Node(0,0);
    for(int i=1;i<=q;i++){
        char op[5];
        int k;
        scanf("%s",op);
        if(op[0]!='I')scanf("%d",&k);
        if(op[0] == 'L')t = t.Add(k);
        else if(op[0] == 'R')t = t.Add(n-k);
        else t = t.rev();
        A[i] = t;
        // t.print();
    }
    int K = Ask_K();
    map<Node,int>cnt;
    cnt[Node(0,0)]++;
    ll ans = 0;
    for(int i=1;i<=q;i++){
        if(A[i].flg){
            ans += cnt[Node(A[i].k,1)];
            if(K!=-1)ans += cnt[Node((P+A[i].k-K)%P,0)];
        }else{
            ans += cnt[Node(A[i].k,0)];
            if(K!=-1)ans += cnt[Node((P+A[i].k-K)%P,1)];
        }
        cnt[A[i]]++;
        // cout<<ans<<endl;
    }
    cout<<ans<<endl;
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

pda
2
R 2
L 2

output:

1

result:

ok 1 number(s): "1"

Test #2:

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

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

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

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

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'