QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#367224#8512. Harmonic Operationsucup-team266#WA 1ms3876kbC++232.6kb2024-03-25 20:32:182024-03-25 20:32:18

Judging History

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

  • [2024-03-25 20:32:18]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3876kb
  • [2024-03-25 20:32:18]
  • 提交

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'