QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#367224 | #8512. Harmonic Operations | ucup-team266# | WA | 1ms | 3876kb | C++23 | 2.6kb | 2024-03-25 20:32:18 | 2024-03-25 20:32:18 |
Judging History
answer
//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define ull unsigned ll
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
void die(string S){puts(S.c_str());exit(0);}
string s;
int n,m;
int d;
struct tag
{
int r;
int s;
tag(){};
tag(int _r,int _s):r(_r),s(_s){}
};
tag merge(tag a,tag b)
{
return tag(a.r^b.r,(b.s+(b.r?d-a.s:a.s))%d);
}
tag A[200200],B[200200];
int type[200200],val[200200];
mt19937 rnd(20210448);
const ll mod=998244353,base=12345+rnd();
ll H1[400400],H2[400400];
ll pw;
ll get1(int l,int r)
{
return (H1[r]-H1[l-1]*pw%mod+mod)%mod;
}
ll get2(int l,int r)
{
return (H2[r]-H2[l-1]*pw%mod+mod)%mod;
}
ll cnt1[200200],cnt2[200200];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>s;
n=sz(s);
string s2=s;
for(int i=1;i<n;i++)
if(i<n-i)
swap(s2[i],s2[n-i]);
cin>>m;
for(int i=1;i<=n;i++)
if(n%i==0)
{
bool flag=1;
for(int j=0;j<n;j++)
if(s[j]!=s[(j+i)%n])
{
flag=0;
break;
}
if(flag)
{
d=i;
break;
}
}
s+=s;
s2+=s2;
for(int i=0;i<n+n;i++)
H1[i+1]=(H1[i]*base+s[i])%mod;
for(int i=0;i<n+n;i++)
H2[i+1]=(H2[i]*base+s2[i])%mod;
pw=1;
int pos=-1;
for(int i=0;i<d;i++)
if(get1(i+1,i+n)==get2(1,n))
pos=i;
for(int i=1;i<=n;i++)
pw=pw*base%mod;
A[0]=tag(0,0);
for(int i=1;i<=m;i++)
{
char ch;
cin>>ch;
if(ch=='R')
{
type[i]=1;
cin>>val[i];
val[i]%=d;
}
else if(ch=='L')
{
type[i]=1;
cin>>val[i];
val[i]=(d-val[i]%d)%d;
}
}
for(int i=1;i<=m;i++)
if(type[i])
A[i]=merge(A[i-1],tag(0,val[i]));
else
A[i]=merge(A[i-1],tag(1,d-1));
for(int i=1;i<=m;i++)
if(type[i])
B[i]=merge(tag(0,(d-val[i])%d),B[i-1]);
else
B[i]=merge(tag(1,d-1),B[i-1]);
ll ans=0;
for(int i=1;i<=m;i++)
{
if(B[i-1].r)
cnt2[B[i-1].s]++;
else
cnt1[B[i-1].s]++;
if(A[i].r)
{
ans+=cnt2[A[i].s];
if(pos!=-1)
ans+=cnt1[(A[i].s-pos+d)%d];
}
else
{
ans+=cnt1[(d-A[i].s)%d];
if(pos!=-1)
ans+=cnt2[(pos-A[i].s+d)%d];
}
}
cout<<ans<<endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3636kb
input:
pda 2 R 2 L 2
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3608kb
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: 3628kb
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: 3876kb
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: 1ms
memory: 3588kb
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: 0ms
memory: 3620kb
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:
47
result:
wrong answer 1st numbers differ - expected: '116', found: '47'