QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#376169 | #8512. Harmonic Operations | installb# | WA | 1ms | 5664kb | C++20 | 2.0kb | 2024-04-03 22:39:32 | 2024-04-03 22:39:34 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define M 200005
char S[M];
int q,n,P;
struct Node{
int k,flg;
Node(){}
Node(int a,int b):k(a),flg(b){}
Node Add(int kx){
return Node((k+kx)%P,flg);
}
Node rev(){
return Node((n-k)%P,!flg);
}
bool operator < (const Node &res)const{
return k<res.k || k == res.k && flg < res.flg;
}
void print(){
cout<<flg<<' '<<k<<endl;
}
}A[M];
int Ask_per(){
static int f[M];
f[1]=0;
for(int i=2,j=0;i<=n;i++){
while(j && S[j+1]!=S[i])j=f[j];
if(S[j+1]==S[i])j++;
f[i]=j;
}
if(n%(n-f[n]) == 0)return n-f[n];
else return n;
}
using ull = unsigned long long;
int Ask_K(){
const int BS=37;
ull pw = 1;
for(int i=1;i<=n;i++)pw *= BS;
ull bs = 0;
for(int i=1;i<=n;i++)bs = BS*bs+S[i]-'a'+1;
reverse(S+1,S+1+n);
ull now = 0;
for(int i=1;i<=n;i++)now = BS*now+S[i]-'a'+1;
if(now == bs)return 0;
for(int i=1;i<=n;i++){
now *= BS;
now -= pw * (S[i]-'a'+1);
now += S[i]-'a'+1;
if(now == bs)return i;
}
return -1;
}
using ll = long long;
int main(){
scanf("%s",S+1);
n=strlen(S+1);
cin>>q;
P = Ask_per();
Node t = Node(0,0);
for(int i=1;i<=q;i++){
char op[5];
int k;
scanf("%s",op);
if(op[0]!='I')scanf("%d",&k);
if(op[0] == 'L')t = t.Add(k);
else if(op[0] == 'R')t = t.Add(n-k);
else t = t.rev();
A[i] = t;
// t.print();
}
int K = Ask_K();
// cout<<K<<endl;
map<Node,int>cnt;
cnt[Node(0,0)]++;
ll ans = 0;
for(int i=1;i<=q;i++){
if(A[i].flg){
ans += cnt[Node(A[i].k,1)];
if(K!=-1)ans += cnt[Node((P+A[i].k-K)%P,0)];
}else{
ans += cnt[Node(A[i].k,0)];
if(K!=-1)ans += cnt[Node((P+A[i].k-K)%P,1)];
}
cnt[A[i]]++;
// cout<<ans<<endl;
}
cout<<ans<<endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 5652kb
input:
pda 2 R 2 L 2
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 1ms
memory: 3736kb
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: 3728kb
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: 3652kb
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: 5664kb
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: 3604kb
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:
58
result:
wrong answer 1st numbers differ - expected: '116', found: '58'