QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#361973#8505. Almost Aligneducup-team206#WA 0ms9728kbC++172.1kb2024-03-23 13:48:042024-03-23 13:48:05

Judging History

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

  • [2024-03-23 13:48:05]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:9728kb
  • [2024-03-23 13:48:04]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

#define int long long

const int N=2e5+1e3+7,P=(1ll<<61)-1,bs=13131;

struct O{
    int k,b;
};

int n;

string s;

O operator +(const O &a,const O &b)
{
    return {a.k^b.k,(a.b*(b.k?-1:1)+b.b+n)%n};
}

O inv(const O &a)
{
    return {a.k,(-a.b*(a.k?-1:1)+n)%n};
}

int mul(const int &a,const int & b)
{
    return (__int128)a*b%P;
}

int add(const int &a,const int &b)
{
    return a+b>=P?a+b-P:a+b;
}

int pw[N],hs[N],ht[N];

int geth(int *h,int l,int r)
{
    if(l>r)
        return 0;
    return add(h[r],P-mul(!l?0:h[l-1],pw[r-l+1]));
}

int m;

int cnt[2][N];

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>s;
    n=s.size();
    pw[0]=1;
    for(int i=1;i<=n;i++)
        pw[i]=mul(pw[i-1],bs);
    hs[0]=s[0];
    for(int i=1;i<n;i++)
        hs[i]=add(mul(hs[i-1],bs),s[i]);
    ht[0]=s[0];
    for(int i=1;i<n;i++)
        ht[i]=add(mul(ht[i-1],bs),s[n-i]);
    int r=0;
    for(int i=1;i<=n;i++)
        if(n%i==0)
        {
            if(geth(hs,0,n-1-i)==geth(hs,i,n-1))
            {
                r=i;
                break;
            }
        }
    int t=-1;
    for(int i=0;i<n;i++)
    {
        if(hs[n-1]==add(mul(geth(ht,i,n-1),pw[i]),geth(ht,0,i-1)))
        {
            t=i;
            break;
        }
    }
    O s,is;
    s.k=s.b=0,is.k=is.b=0;
    cnt[0][0]++;
    int ans=0;
    cin>>m;
    for(int i=1;i<=m;i++)
    {
        string op;
        cin>>op;
        O w;
        if(op[0]=='I')
        {
            w.k=1,w.b=n-1;
        }
        else if(op[0]=='R')
        {
            int y;
            cin>>y;
            w.k=0,w.b=(n-y)%n;
        }
        else
        {
            int y;
            cin>>y;
            w.k=0,w.b=y;
        }
        s=s+w;
        is=inv(w)+is;
        {
            ans+=cnt[s.k][(n-s.b*(s.k?-1:1))%r];
        }
        {
            if(t!=-1)
            {
                ans+=cnt[s.k^1][(t+n-s.b*(s.k?-1:1))%r];
            }
        }
        cnt[is.k][is.b%r]++;
    }
    cout<<ans<<"\n";
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 9728kb

input:

4
0 0 10 10
0 0 10 10
10 10 -10 -10
10 0 -20 0

output:

0

result:

wrong answer 1st numbers differ - expected: '22.2222222', found: '0.0000000', error = '1.0000000'