QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#372542#8512. Harmonic Operationsarnold518WA 1ms5952kbC++172.4kb2024-03-31 15:13:442024-03-31 15:13:45

Judging History

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

  • [2024-03-31 15:13:45]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5952kb
  • [2024-03-31 15:13:44]
  • 提交

answer

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2e5;

typedef pair<int, bool> pib;

int N, M, T, K;
char S[MAXN+10], S2[MAXN+10];
pib A[MAXN+10], B[MAXN+10];

int mmod(int x, int N) { return (x%N+N)%N; }
pib operator + (pib a, pib b) { return pib{mmod(a.first+(a.second ? -1 : 1)*b.first, N), a.second^b.second}; }

int F[MAXN+10];
void getFail()
{
    F[0]=-1;
    for(int i=1; i<=N; i++)
    {
        int j=F[i-1];
        while(j>=0 && S[j+1]!=S[i]) j=F[j];
        F[i]=j+1;
    }
}

int P[MAXN*2+10];
void getManacher(int N)
{
    int pos=0;
    for(int i=1; i<=N; i++)
    {
        if(i<=pos+P[pos]) P[i]=min(pos+P[pos]-i, P[pos+pos-i]);
        while(i+P[i]+1<=N && i-P[i]-1>=1 && S[i-P[i]-1]==S[i+P[i]+1]) P[i]++;
        if(P[pos]+pos<P[i]+i) pos=i;
    }
}
bool ispal(int l, int r)
{
    if(l>r) return true;
    l=l*2-1; r=r*2-1;
    int t=l+r>>1;
    if(t-P[t]<=l && r<=t+P[t]) return true;
    return false;
}

int cnt[MAXN+10][2];

int main()
{
    scanf("%s", S+1); N=strlen(S+1);
    scanf("%d", &M);
    for(int i=1; i<=M; i++)
    {
        char c; int p;
        scanf(" %c", &c);
        if(c=='R')
        {
            scanf("%d", &p);
            A[i]=A[i-1]+pib{mmod(-p, N), 0};
        }
        else if(c=='L')
        {
            scanf("%d", &p);
            A[i]=A[i-1]+pib{mmod(p, N), 0};
        }
        else
        {
            A[i]=A[i-1]+pib{0, 1};
        }
        if(!A[i].second) B[i]=pib{mmod(-A[i].first, N), 0};
        else B[i]=A[i];
    }

    getFail();
    T=N;
    for(int i=F[N]; i>0; i=F[i])
    {
        if(N%(N-i)==0)
        {
            T=N-i;
            break;
        }
    }

    for(int i=1; i<=N+N-1; i++)
    {
        if(i%2) S2[i]=S[i/2+1];
        else S2[i]='?';
    }
    getManacher(N+N-1);

    K=-1;
    for(int i=0; i<T; i++)
    {
        if(ispal(1, i) && ispal(i+1, T)) K=i;
    }

    ll ans=0;
    for(int i=1; i<=M; i++)
    {
        cnt[mmod(B[i-1].first, T)][B[i-1].second]++;

        if(!A[i].second)
        {
            ans+=cnt[mmod(-A[i].first, T)][0];
            if(K!=-1) ans+=cnt[mmod(A[i].first+K, T)][1];
        }
        else
        {
            if(K!=-1) ans+=cnt[mmod(K-A[i].first, T)][0];
            ans+=cnt[mmod(A[i].first, T)][1];
        }
    }
    printf("%lld\n", ans);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

pda
2
R 2
L 2

output:

1

result:

ok 1 number(s): "1"

Test #2:

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

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

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

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

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

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:

62

result:

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