QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#545914 | #8512. Harmonic Operations | qwerasdf | WA | 0ms | 3612kb | C++20 | 2.9kb | 2024-09-03 18:10:08 | 2024-09-03 18:10:08 |
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){
k=(n-(i-n+1))%n;
//rotation[1][k]=1;
break;
}
else j++;
}
}
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;
move%=n;
if(c=='L')move=(n-move)%n;
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];
// rotate+cur
if(!x.first){ // ?+x=0 -> ?=n-x
ans+=rotation[0][(n-x.second)%n];
}
else{ // ?+inv+x=inv+k -> inv+n-?+x=inv+k -> ?=n-k+x
if(k>=0){
ans+=rotation[0][(n-k+x.second)%n];
}
}
// inv+rotate + cur
if(!f){
if(!x.first){ // inv+?+x=inv+k -> ?=k-x
if(k>=0){
ans+=rotation[1][(k-x.second+n)%n];
}
}
else{ // inv+? + inv+x = 0 -> n-?+x=0 -> ?=n+x=x
ans+=rotation[1][x.second];
}
}
pii y=get_inv(x,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: 3608kb
input:
pda 2 R 2 L 2
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3592kb
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: 3608kb
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: 0ms
memory: 3612kb
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: 0ms
memory: 3604kb
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: 3528kb
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:
118
result:
wrong answer 1st numbers differ - expected: '116', found: '118'