QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#545786 | #8512. Harmonic Operations | qwerasdf | WA | 0ms | 3616kb | C++20 | 3.1kb | 2024-09-03 17:16:28 | 2024-09-03 17:16:28 |
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};
}
pii get(pii x, pii y, int n){
x=get_inv(x,n);
if(y.first){
x.first=1-x.first;
x.second=(n-x.second)%n;
x.second=(x.second+y.second)%n;
}
else{
x.second=(x.second+y.second)%n;
}
return x;
}
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++;
}
}
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(s[0]=='w')
cout<<c<<'\n';
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;
}
}
}
if(s[0]=='w')
return;
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: 3616kb
input:
pda 2 R 2 L 2
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3552kb
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: 3484kb
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: 3552kb
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: -100
Wrong Answer
time: 0ms
memory: 3576kb
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:
R R I I R R L I L L R L I I L L L L L L I I R R I R L R R I I R R R L R R I L I L I I R R L I L I I I I L L L L R I L I R L I R L I L R L R L I R R R I R L R L R I I I R I R L R L L L L R I R I L I I
result:
wrong output format Expected integer, but "R" found