QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#545799 | #8512. Harmonic Operations | qwerasdf | WA | 0ms | 3628kb | C++20 | 2.8kb | 2024-09-03 17:21:54 | 2024-09-03 17:21:54 |
Judging History
answer
//#include <atcoder/all>
#include <bits/stdc++.h>
using namespace std;
//using namespace atcoder; //https://github.com/atcoder/ac-library
#define rep(i, l, r) for (int i = (l); i < (r); i++)
#define bit(n, k) ((n >> k) & 1)
#define all(v) (v).begin(), (v).end()
typedef long long ll;
typedef pair<int, int> pii;
pii get_inv(pii x, int n){
if(x.first)return x;
return {0,(n-x.second)%n};
}
void test_case(int tt){
string s; cin>>s;
int n=(int)s.length();
vector<int> fail(n,0);
for(int i=1,j=0; i<n; i++){
while(j>0 && s[i]!=s[j])j=fail[j-1];
if(s[i]==s[j])fail[i]=++j;
}
int pow=1, k=fail[n-1]; // n*(i-1)/i <=k
for(ll i=2; (i-1)*n<=k*i; i++){
if(n%i==0 && n*(i-1)==k*i)pow=i;
}
s=s.substr(0,n/pow);
n=(int)s.length();
fail=vector<int>(n,0);
for(int i=1,j=0; i<n; i++){
while(j>0 && s[i]!=s[j])j=fail[j-1];
if(s[i]==s[j])fail[i]=++j;
}
string t=s;
reverse(all(t));
int f=(t.compare(s)==0);
t+=t;
vector<vector<int>> rotation(2,vector<int>(n,0));
rotation[0][0]=1;
k=-1;
for(int i=0, j=0; i<2*n-1; i++){
while(j>0 && t[i]!=s[j])j=fail[j-1];
if(t[i]==s[j]){
if(j==n-1){
rotation[1][i-n+1]=1;
k=i-n+1;
break;
}
else j++;
}
}
puts("1");
return;
int m; cin>>m;
vector<pii> ps(m+1); // inv|move
ps[0]={0,0};
rep(i,0,m){
ps[i+1]=ps[i];
char c; cin>>c;
if(c=='I'){
ps[i+1].first=1-ps[i+1].first;
ps[i+1].second=(n-ps[i+1].second)%n;
}
else{
int move; cin>>move;
if(c=='L')move=n-move;
ps[i+1].second=(ps[i+1].second+move)%n;
}
if(f){
if(ps[i+1].first){
ps[i+1].first=0;
ps[i+1].second=(n-ps[i+1].second)%n;
}
}
}
ll ans=0;
rep(i,0,m){
pii x=ps[i+1];
pii y=get_inv(x,n);
if(!x.first){
ans+=rotation[0][(n-x.second)%n];
}
else{
if(k>-1)
ans+=rotation[0][(k-x.second+n)%n];
}
if(!f){
if(!x.first){
if(k>-1)
ans+=rotation[1][(k-x.second+n)%n];
}
else{
if(k>-1)
ans+=rotation[1][(x.second-k+n)%n];
}
}
rotation[y.first][y.second]++;
}
cout<<ans<<'\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
int t = 1;
//cin>>t;
rep(i, 1, t + 1)
{
test_case(i);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3628kb
input:
pda 2 R 2 L 2
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 3608kb
input:
aaa 4 R 1 I I R 1
output:
1
result:
wrong answer 1st numbers differ - expected: '10', found: '1'