QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#372542 | #8512. Harmonic Operations | arnold518 | WA | 1ms | 5952kb | C++17 | 2.4kb | 2024-03-31 15:13:44 | 2024-03-31 15:13:45 |
Judging History
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'