Submission #1127758

---

Source Code Expand

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

struct cww{cww(){
    ios::sync_with_stdio(false);cin.tie(0);
}}star;
#define fin "\n"
#define FOR(i,bg,ed) for(int i=(bg);i<(ed);i++)
#define REP(i,n) FOR(i,0,n)
#define fi first
#define se second
#define pb push_back
#define DEBUG if(0)
template <typename T>inline void chmin(T &l,T r){l=min(l,r);}
template <typename T>inline void chmax(T &l,T r){l=max(l,r);}
template <typename T>
istream& operator>>(istream &is,vector<T> &v){
    for(auto &it:v)is>>it;
    return is;
}

namespace SA {
    int n, k;
    int R[500000];
    int T[500000];
    bool compare_sa(int i, int j) {
        if (R[i] != R[j])return R[i] < R[j];
        else {
            int ri = i + k <= n ? R[i + k] : -1;
            int rj = j + k <= n ? R[j + k] : -1;
            return ri < rj;
        }
    }
    vector<int> construct_sa(string& S) {
        n = S.size();
        vector<int> sa(n + 1);
        for (int i = 0; i <= n; i++) {
            sa[i] = i;
            R[i] = i < n ? S[i] : -1;
        }
 
        for (k = 1; k <= n; k *= 2) {
            sort(sa.begin(), sa.end(), compare_sa);
            T[sa[0]] = 0;
            for (int i = 1; i <= n; i++) 
                T[sa[i]] = T[sa[i - 1]] + (compare_sa(sa[i - 1], sa[i]) ? 1 : 0);
            for (int i = 0; i <= n; i++)
                R[i] = T[i];
        }
        return sa;
    }
    vector<int> construct_lcp(string& S, vector<int> &sa) {
        n = S.size();
        for (int i = 0; i <= n; i++)R[sa[i]] = i;
        int h = 0;
        vector<int> lcp(n + 1, 0);
        for (int i = 0; i < n; i++) {
            int j = sa[R[i] - 1];
            if (h > 0)h--;
            for (; j + h < n&&i + h < n; h++) {
                if (S[j + h] != S[i + h])break;
            }
            lcp[R[i] - 1] = h;
        }
        return lcp;
    }
}

const int INF=114514;

typedef int A;
struct node{
    A a;

};
A mg(node& v,int l,int r){
    return v.a;
}
A mg(A l,A r){
    return min(l,r);
}
namespace ST{
    node mem[1][2123456];
    int cnt=0;
    node* get(){return mem[cnt++];}
}
struct seg_tree{
    int size;
    node *seg;
    void init(int l,int r,vector<int> &lcp,int k=0){
        auto &v=seg[k];
        //flag関連の処理

        if(r-l==1){
            //葉の時の処理
            if(l>=lcp.size())v.a=INF;
            else v.a=lcp[l];
        }
        else if(r-l>1){
            int m=(l+r)/2;
            init(l,m,lcp,k*2+1);init(m,r,lcp,k*2+2);
            v.a=mg(mg(seg[k*2+1],l,m),mg(seg[k*2+2],m,r));
        }
    }
    seg_tree(int n,vector<int> &lcp){
        size=1;
        while(size<n)size*=2;
        seg=ST::get();
        init(0,size,lcp);
    }

#define LQ a,b,k*2+1,l,m
#define RQ a,b,k*2+2,m,r
    A get(int a,int b,int k,int l,int r){
        if(a<=l&&r<=b)return mg(seg[k],l,r);
        //push(k,l,r);          
        int m=(l+r)/2;
        bool ll=!(m<=a||b<=l);
        bool rr=!(r<=a||b<=m);
        A ret;
        if(ll&&rr)ret=mg(get(LQ),get(RQ));
        else if(ll)ret=get(LQ);
        else ret=get(RQ);
        seg[k].a=mg(mg(seg[k*2+1],l,m),mg(seg[k*2+2],m,r));
        return ret;
    }
    A get(int a,int b){return get(a,b,0,0,size);}
};
int main(){
    int K;string S;
    cin>>K>>S;
    int N=S.size();
    K++;
    int max_len=(N+K-1)/K;
    auto sa=SA::construct_sa(S);
    auto lcp=SA::construct_lcp(S,sa);
    auto rid=sa;
    REP(i,sa.size())rid[sa[i]]=i;
    vector<int> ids;
    for(auto &it:sa){
        if(N-it>=max_len)ids.pb(it);
    }
    seg_tree st(N+1,lcp);
    auto cmp=[&](int l,int r){
        if(rid[l]>rid[r])swap(l,r);
        if(l==r)return true;
        return st.get(rid[l]+1,rid[r]+1)>=max_len;
    };
    auto f=[&](int id){
        int now_cost=0;
        int lb=1;
        int ub=1;
        REP(i,N){
            if(i+max_len>N||rid[i]<=rid[id]||cmp(i,id))
                chmax(ub,i+max_len+1);
            else chmax(ub,i+max_len);
            if(i+1>ub)return false;
            if(i+1==lb){
                lb=ub;
                now_cost++;
            }
        }
        return now_cost<=K;
    };
    int ok=ids.size()-1,ng=-1;
    while(ok-ng>1){
        const int mid=(ok+ng)/2;
        if(f(ids[mid]))ok=mid;
        else ng=mid;
    }
    REP(i,max_len)cout<<S[ids[ok]+i];cout<<endl;
    return 0;
}

Submission Info

Judge Result