QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#545914#8512. Harmonic OperationsqwerasdfWA 0ms3612kbC++202.9kb2024-09-03 18:10:082024-09-03 18:10:08

Judging History

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

  • [2024-09-03 18:10:08]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3612kb
  • [2024-09-03 18:10:08]
  • 提交

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'