QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#371555 | #8512. Harmonic Operations | Mo_Han136# | WA | 0ms | 3964kb | C++20 | 2.3kb | 2024-03-30 13:58:30 | 2024-03-30 13:58:38 |
Judging History
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'