QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#361973 | #8505. Almost Aligned | ucup-team206# | WA | 0ms | 9728kb | C++17 | 2.1kb | 2024-03-23 13:48:04 | 2024-03-23 13:48:05 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+1e3+7,P=(1ll<<61)-1,bs=13131;
struct O{
int k,b;
};
int n;
string s;
O operator +(const O &a,const O &b)
{
return {a.k^b.k,(a.b*(b.k?-1:1)+b.b+n)%n};
}
O inv(const O &a)
{
return {a.k,(-a.b*(a.k?-1:1)+n)%n};
}
int mul(const int &a,const int & b)
{
return (__int128)a*b%P;
}
int add(const int &a,const int &b)
{
return a+b>=P?a+b-P:a+b;
}
int pw[N],hs[N],ht[N];
int geth(int *h,int l,int r)
{
if(l>r)
return 0;
return add(h[r],P-mul(!l?0:h[l-1],pw[r-l+1]));
}
int m;
int cnt[2][N];
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>s;
n=s.size();
pw[0]=1;
for(int i=1;i<=n;i++)
pw[i]=mul(pw[i-1],bs);
hs[0]=s[0];
for(int i=1;i<n;i++)
hs[i]=add(mul(hs[i-1],bs),s[i]);
ht[0]=s[0];
for(int i=1;i<n;i++)
ht[i]=add(mul(ht[i-1],bs),s[n-i]);
int r=0;
for(int i=1;i<=n;i++)
if(n%i==0)
{
if(geth(hs,0,n-1-i)==geth(hs,i,n-1))
{
r=i;
break;
}
}
int t=-1;
for(int i=0;i<n;i++)
{
if(hs[n-1]==add(mul(geth(ht,i,n-1),pw[i]),geth(ht,0,i-1)))
{
t=i;
break;
}
}
O s,is;
s.k=s.b=0,is.k=is.b=0;
cnt[0][0]++;
int ans=0;
cin>>m;
for(int i=1;i<=m;i++)
{
string op;
cin>>op;
O w;
if(op[0]=='I')
{
w.k=1,w.b=n-1;
}
else if(op[0]=='R')
{
int y;
cin>>y;
w.k=0,w.b=(n-y)%n;
}
else
{
int y;
cin>>y;
w.k=0,w.b=y;
}
s=s+w;
is=inv(w)+is;
{
ans+=cnt[s.k][(n-s.b*(s.k?-1:1))%r];
}
{
if(t!=-1)
{
ans+=cnt[s.k^1][(t+n-s.b*(s.k?-1:1))%r];
}
}
cnt[is.k][is.b%r]++;
}
cout<<ans<<"\n";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 9728kb
input:
4 0 0 10 10 0 0 10 10 10 10 -10 -10 10 0 -20 0
output:
0
result:
wrong answer 1st numbers differ - expected: '22.2222222', found: '0.0000000', error = '1.0000000'