QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#149002#243. Lyndon Substringnameless_story0 242ms20144kbC++203.5kb2023-08-23 21:35:292023-08-23 21:35:31

Judging History

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

  • [2023-08-23 21:35:31]
  • 评测
  • 测评结果:0
  • 用时:242ms
  • 内存:20144kb
  • [2023-08-23 21:35:29]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;
#define N 30'0000

void output(vector<LL> &f){
    for (auto x:f) cout<<x<<' '; cout<<endl;
}
const LL B=233,mod=998244353;
LL pw[N];
struct hashstring{
    vector<LL> f;
    void build(string s){
        f.resize(s.size()+1);
        f[0]=0;
        for (LL i=0;i<s.size();++i){
            auto w=s[i];
            f[i+1]=(f[i]*B+w)%mod;
        }
    }
    LL calc(LL i,LL len){
        return (f[i+len]-f[i]*pw[len]%mod+mod)%mod;
    }
};
void init(LL n){
    pw[0]=1; for (LL i=1;i<=n;++i) pw[i]=pw[i-1]*B%mod;
}

void solve(){
    LL n,m; cin>>n>>m;
    vector<string> s(n);
    vector<hashstring> f(n);
    for (LL i=0;i<n;++i){
        cin>>s[i];
        f[i].build(s[i]);
    }
    vector<vector<LL>> lyndon(n),sim(n);
    vector<LL> ans(n);
    for (LL i=0;i<n;++i){
        auto st=s[i]+'0';
        for (LL lst=-1,cyc=1,j=1;j<st.size();++j){
            if (st[j]>st[j-cyc]) cyc=j-lst;
            else{
                if (st[j]<st[j-cyc]){
                    ans[i]=max(ans[i],cyc);
                    if (j==st.size()-1){
                        sim[i].push_back(lst+1);
                    }
                    for (lst+=cyc;lst<j;lst+=cyc){
                        lyndon[i].push_back(lst);
                    }
                    lst-=cyc;
                    cyc=1;
                    j=lst+1;
                }
            }
        }
    }
    for (LL i=0;i<n;++i){
        LL lst=0;
        for (LL x:lyndon[i]){
            ans[i]=max(ans[i],x-lst);
            lst=x;
        }
    }
    auto calc=[&](LL i,LL j,LL p,LL len){
        if (p+len<=s[i].size()) return f[i].calc(p,len);
        if (p>=s[i].size()) return f[j].calc(p-s[i].size(),len);
        LL t=s[i].size()-p;
        return (f[i].calc(p,t)*pw[len-t]+f[j].calc(0,len-t))%mod;
    };
    auto check=[&](LL i,LL j,LL p1,LL p2,LL len){
        if (calc(i,j,p1,len)==calc(i,j,p2,len)) return false;
        LL l=1,r=len,k=0;
        while (l<=r){
            LL mid=(l+r)>>1;
            if (calc(i,j,p1,mid)==calc(i,j,p2,mid)){
                k=mid;
                l=mid+1;
            }
            else{
                r=mid-1;
            }
        }
        auto c1=(p1+k<s[i].size())?s[i][p1+k]:s[j][p1+k-s[i].size()];
        auto c2=(p2+k<s[i].size())?s[i][p2+k]:s[j][p2+k-s[i].size()];
        return c1<c2;
    };
    while (m--){
        LL i,j; cin>>i>>j; --i; --j;
        LL tmp=max(ans[i],ans[j]);
        LL t=sim[i].back();
        for (LL k=0;k+1<sim[i].size();++k){
            LL l=1,r=s[j].size();
            LL p1=sim[i][k];
            LL p2=sim[i][k+1];
            LL len0=s[i].size()-p2,mx=0;
            if (check(i,j,p1,p2,len0+s[j].size())) t=sim[i][k];
        }
        if (check(i,j,t,s[i].size(),s[j].size())){
            LL l=0,r=lyndon[j].size()-1,pre=0;
            while (l<=r){
                LL mid=(l+r)>>1;
                LL L=mid==0?0:lyndon[j][mid-1]+1;
                LL R=lyndon[j][mid];
                if (check(i,j,t,s[i].size()+L,R-L+1)){
                    pre=lyndon[j][mid]+1;
                    l=mid+1;
                }
                else{
                    r=mid-1;
                }
            }
            tmp=max(tmp,(LL)s[i].size()-t+pre);
        }
        cout<<tmp<<'\n';
    }
}
int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    LL T; cin>>T;
    init(200000);
    while (T--) solve();
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 242ms
memory: 20144kb

input:

24
100 10000
ab
babbab
baabbbb
abbababbb
bb
bbbaaaba
b
aababaa
aaabbb
abbabbaaa
aaaab
bbab
bbabb
baaa
bbabbaaba
abaa
b
aabbbb
babbbbbb
bbaaba
aba
bbb
abbbaabaa
aa
bbaabaabbb
abbbbbb
aabbbaabba
ababba
aabbaab
ababa
aabbabbaab
b
aabaabaab
baaababa
babaaa
abaaaabbbb
aaaaabaa
bbb
bbab
baaa
bbabba
ababbb...

output:

2
3
6
11
4
5
3
5
6
8
5
4
4
3
4
2
3
6
10
4
2
5
6
2
8
9
5
7
4
2
7
3
3
6
3
8
6
5
4
3
4
8
3
4
7
2
2
3
9
7
2
2
7
11
3
5
5
8
3
6
6
3
5
4
4
8
4
2
5
8
3
5
5
4
5
3
2
5
3
10
4
5
5
9
4
4
7
3
5
3
5
9
4
4
3
7
8
6
5
3
3
3
6
11
7
8
3
5
6
8
5
7
7
3
7
3
3
6
13
7
3
8
6
3
8
9
5
7
4
3
7
3
3
6
3
8
6
8
7
3
7
8
3
4
10
3
3...

result:

wrong answer 443519th lines differ - expected: '18', found: '12'