QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#371555#8512. Harmonic OperationsMo_Han136#WA 0ms3964kbC++202.3kb2024-03-30 13:58:302024-03-30 13:58:38

Judging History

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

  • [2024-03-30 13:58:38]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3964kb
  • [2024-03-30 13:58:30]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N=2e5+100;
bool bk[N],bz[N];
char s[2*N],ss[2*N];int a[N],b[N],Cnt[2][N],qz[2][N],g[2*N],nex[2*N];

int main()
{

    scanf("%s",s+1);
    int n=strlen(s+1);

    int m;scanf("%d",&m);
    for(int i=1;i<=m;i++){
        char op[4];
        scanf("%s",op+1);
        if(op[1]=='L') a[i]=1,scanf("%d",&b[i]);
        else if(op[1]=='R') a[i]=2,scanf("%d",&b[i]);
        else a[i]=3;
    }

    for(int i=1;i<=n;i++) s[i+n]=s[i];

    nex[1]=0;int K;
    for(int i=2;i<=2*n;i++){
        int t=nex[i-1];
        while(t&&s[t+1]!=s[i]) t=nex[t];
        if(s[t+1]!=s[i]) nex[i]=0;
        else nex[i]=t+1;
        if(nex[i]==n) {K=i-n;break;}
    }

    int mx=0,md=0;

    for(int i=1;i<=2*n;i++){
        if(i%2==1) ss[i]=s[i/2+1];
        else if(i<2*n) ss[i]='#';
    }

    for(int i=1;i<=2*n-1;i++){
        if(i<=mx){
            int t=2*md-i;
            g[i]=min(g[t],mx-i);
        }
        while(i+g[i]+1<=2*n-1&&ss[i+g[i]+1]==ss[i-g[i]-1]) g[i]++;
        if(mx<i+g[i]) mx=i+g[i];
    }

    for(int i=1;i<=2*n;i++){
        if(i-g[i]==1){
            int R=i+g[i];
            bk[R/2+1]=true;
        }
        if(i+g[i]==2*n-1){
            int L=i-g[i];
            bz[L/2]=true;
        }
    }

    // for(int i=1;i<=n;i++) printf("%d %d\n",bk[i],bz[i]);

    bz[n]=true;
    int las=-1,ww=-1;
    for(int i=1;i<=n;i++){
        if(bz[i]&&bk[i]){
            if(las==-1) las=i;
            else {ww=i-las;break;}
        }
    }

    Cnt[0][0]=qz[0][0]=1;
    int ty=0,Sum=0;ll Ans=0;

    for(int i=1;i<=m;i++){
        if(a[i]==3){
            ty^=1;
        }
        else if(a[i]==2){
            if(ty) Sum=(Sum+b[i])%n;
            else Sum=(Sum-b[i]+n)%n;
        }
        else{
            if(ty) Sum=(Sum-b[i]+n)%n;
            else Sum=(Sum+b[i])%n;
        }
        Ans=Ans+Cnt[ty][Sum%K];
        if(ww!=-1){
            Ans=Ans+qz[ty^1][Sum%ww];
            qz[ty][Sum%ww]++;
        }
        else if(las!=-1){
            if(ty) Ans=Ans+qz[ty^1][(Sum-las+n)%n];
            else Ans=Ans+qz[ty^1][(Sum+las)%n];
            qz[ty][Sum]++;
        }
        // printf("%d %d\n",ty,Sum);
        Cnt[ty][Sum%K]++;
    }

    printf("%lld\n",Ans);

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

pda
2
R 2
L 2

output:

1

result:

ok 1 number(s): "1"

Test #2:

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

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

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

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

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:

2542

result:

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