結果

問題 No.3188 K-th Lexmin
ユーザー GOTKAKO
提出日時 2025-06-22 18:13:20
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 10,676 bytes
コンパイル時間 3,194 ms
コンパイル使用メモリ 230,056 KB
実行使用メモリ 30,924 KB
最終ジャッジ日時 2025-06-22 18:13:43
合計ジャッジ時間 20,236 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 26 TLE * 1 -- * 20
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:322:22: warning: ‘k’ may be used uninitialized [-Wmaybe-uninitialized]
  322 |             for(; k++,k<=l;){
      |                   ~~~^~~~~
main.cpp:316:29: note: ‘k’ was declared here
  316 |             int l = L.at(i),k;
      |                             ^

ソースコード

diff # 

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

vector<int> SAIS(vector<int> &A){
    //元が数列なら座圧してから.
    if(A.size() == 1) return {1,0};
    for(auto &a : A) a++;
    A.push_back(0);
    int siz = A.size();
    stack<int> st;
    vector<int> SL(siz);
    for(int i=0; i<siz-1; i++){
        if(A.at(i) == A.at(i+1)) st.push(i);
        else if(A.at(i) < A.at(i+1)){while(st.size()) st.pop();}
        else{
            SL.at(i) = 1;
            while(st.size()){SL.at(st.top()) = 1,st.pop();}
        }
    }
    int siz2 = max(siz,128);
    vector<bool> isLMS(siz);
    vector<vector<int>> LMS(siz2),LMS2(siz2),LMS3(siz2);
    for(int i=siz-1; i>0; i--){
        if(SL.at(i-1) != 1 || SL.at(i) != 0) continue;
        LMS.at(A.at(i)).push_back(i); isLMS.at(i) = true;
    }
    for(int i=0; i<siz2; i++){
        for(int k=0; k<LMS2.at(i).size(); k++){
            int pos = LMS2.at(i).at(k);
            if(pos == 0) continue;
            if(SL.at(pos-1) == 0) continue;
            LMS2.at(A.at(pos-1)).push_back(pos-1);
        }
        for(auto pos : LMS.at(i)){
            if(pos == 0) continue;
            if(SL.at(pos-1) == 0) break;
            LMS2.at(A.at(pos-1)).push_back(pos-1);
        }
    }
    LMS2.at(0).push_back(siz-1);
    for(int i=siz2-1; i>=0; i--){
        for(int k=0; k<LMS3.at(i).size(); k++){
            int pos = LMS3.at(i).at(k);
            if(pos == 0) continue;
            if(SL.at(pos-1) == 1) continue;
            LMS3.at(A.at(pos-1)).push_back(pos-1);
        }
        for(int k=LMS2.at(i).size()-1; k>=0; k--){
            int pos = LMS2.at(i).at(k);
            if(pos == 0) continue;
            if(SL.at(pos-1) == 1) continue;
            LMS3.at(A.at(pos-1)).push_back(pos-1);
        }
    }
 
    vector<int> check,Next(siz);
    for(int i=0; i<siz2; i++){
        for(auto &a : LMS2.at(i)) if(isLMS.at(a)) check.push_back(a);
        for(int k=LMS3.at(i).size()-1; k>=0; k--){
            int &a = LMS3.at(i).at(k);
            if(isLMS.at(a)) check.push_back(a);
        }
    }
    int siz3 = check.size();
    bool More = false;
    for(int i=0; i<siz3-1; i++){
        int pos1 = check.at(i),pos2 = check.at(i+1);
        if(i == 0){Next.at(pos2) = 1; continue;}
        if(A.at(pos1) != A.at(pos2)){Next.at(check.at(i+1)) = Next.at(check.at(i))+1; continue;}
        while(true){
            pos1++,pos2++;
           if(A.at(pos1) != A.at(pos2)){Next.at(check.at(i+1)) = Next.at(check.at(i))+1; break;}
            if(isLMS.at(pos1)){
                if(isLMS.at(pos2)) Next.at(check.at(i+1)) = Next.at(check.at(i)),More = true;
                else Next.at(check.at(i+1)) = Next.at(check.at(i))+1;
                break;
            }
        }
    }
 
    vector<int> Take,Give,Rev;
    for(int i=0; i<siz; i++) if(isLMS.at(i)) Give.push_back(Next.at(i)),Rev.push_back(i);
    if(More){
        Take = SAIS(Give);
        for(int i=1; i<Take.size(); i++) check.at(i-1) = Rev.at(Take.at(i));
    }
    LMS.assign(siz2,{}),LMS2.assign(siz2,{}); LMS3.assign(siz2,{});
    for(auto c : check) LMS.at(A.at(c)).push_back(c);
    for(int i=0; i<siz2; i++){
        for(int k=0; k<LMS2.at(i).size(); k++){
            int pos = LMS2.at(i).at(k);
            if(pos == 0) continue;
            if(SL.at(pos-1) == 0) continue;
            LMS2.at(A.at(pos-1)).push_back(pos-1);
        }
        for(auto pos : LMS.at(i)){
            if(pos == 0) continue;
            if(SL.at(pos-1) == 0) break;
            LMS2.at(A.at(pos-1)).push_back(pos-1);
        }
    }
    LMS2.at(0).push_back(siz-1);
    for(int i=siz2-1; i>=0; i--){
        for(int k=0; k<LMS3.at(i).size(); k++){
            int pos = LMS3.at(i).at(k);
            if(pos == 0) continue;
            if(SL.at(pos-1) == 1) continue;
            LMS3.at(A.at(pos-1)).push_back(pos-1);
        }
        for(int k=LMS2.at(i).size()-1; k>=0; k--){
            int pos = LMS2.at(i).at(k);
            if(pos == 0) continue;
            if(SL.at(pos-1) == 1) continue;
            LMS3.at(A.at(pos-1)).push_back(pos-1);
        }
    }
 
    vector<int> check2;
    for(int i=0; i<siz2; i++){
        for(auto &a : LMS2.at(i)) check2.push_back(a);
        for(int k=LMS3.at(i).size()-1; k>=0; k--){
            int &a = LMS3.at(i).at(k);
            check2.push_back(a);
        }
    }
 
    A.pop_back();
    for(auto &a : A) a--;
    return check2;
}
void to_int(string &s,vector<int> &A){for(char c : s) A.push_back(c);}
vector<int> LCP(vector<int> &SA,vector<int> &A){
    A.push_back(-1);
    int siz = SA.size();
    vector<int> Look(siz);
    for(int i=0; i<siz; i++) Look.at(SA.at(i)) = i;
    int lcp = 0;
    vector<int> ret(siz-1);
    for(int i=0; i<siz; i++){
        int pos = Look.at(i);
        assert(SA.at(pos) == i);
        if(pos == siz-1){lcp = 0; continue;}
        int pos1 = SA.at(pos),pos2 = SA.at(pos+1);
        while(A.at(pos1+lcp) == A.at(pos2+lcp)) lcp++;
        ret.at(pos) = lcp; lcp = max(lcp-1,0);
    }
    A.pop_back();
    return ret;
}

using SS = int;
class SegmentTree{
    public:
    int siz = -1,n = -1;
    vector<SS> dat;
 
    SS op(SS a, SS b){return min(a,b);}
    SS e(){return 1001001001;}
    void renew (SS &a,SS x){
        a = op(a,x);
        //a = x; //set(pos,x)で可能.
        //その他.
    }
 
    SegmentTree(int N){init(N);}
    SegmentTree(const vector<SS> &A){//長さ配列サイズに合わせる.
        siz = 1; n = A.size();
        while(siz < n) siz *= 2;
        dat.resize(siz*2,e());
        for(int i=0; i<n; i++) dat.at(i+siz) = A.at(i);
        for(int i=siz-1; i>0; i--) dat.at(i) = op(dat.at(i*2),dat.at(i*2+1));
    }
    void init(int N){
        //全要素単位元に初期化.
        siz = 1; n = N;
        while(siz < n) siz *= 2;
        dat.assign(siz*2,e());
    }
    void init(const vector<SS> &A){//長さ配列サイズに合わせる.
        siz = 1; n = A.size();
        while(siz < n) siz *= 2;
        dat.resize(siz*2,e());
        for(int i=0; i<n; i++) dat.at(i+siz) = A.at(i);
        for(int i=siz-1; i>0; i--) dat.at(i) = op(dat.at(i*2),dat.at(i*2+1));
    }
    void set(int pos,SS x){
        pos = pos+siz;
        dat.at(pos) = x;
        while(pos != 1){
            pos = pos/2;
            dat.at(pos) = op(dat.at(pos*2),dat.at(pos*2+1));
        }
    }
    void update(int pos,SS x){
        pos = pos+siz;
        renew(dat.at(pos),x);
        while(pos != 1){
            pos = pos/2;
            dat.at(pos) = op(dat.at(pos*2),dat.at(pos*2+1));
        }
    } 
    SS findans(int l, int r){
        SS retl = e(),retr = e();
        l += siz,r += siz;
        while(l < r){
            if(l&1) retl = op(retl,dat.at(l++));
            if(r&1) retr = op(dat.at(--r),retr);
            l >>= 1; r >>= 1;
        }
        return op(retl,retr);
    }
    SS get(int pos){return dat.at(pos+siz);}
    SS rangeans(int l, int r){return findans(l,r);}
    SS allrange(){return dat.at(1);}
 
    //rightは) leftは[で 渡す&返す. 
    int maxright(const function<bool(SS)> f,int l = 0){
        //fを満たさない最小の箇所を返す なければn.
        l += siz; int r = n+siz;
        vector<int> ls,rs;
        while(l < r){
            if(l&1) ls.push_back(l++);
            if(r&1) rs.push_back(--r);
            l >>= 1; r >>= 1; 
        }
        SS okl = e();
        for(int i=0; i<ls.size(); i++){
            l = ls.at(i);
            SS now = op(okl,dat.at(l));
            if(!f(now)){
                while(l < siz){
                    l <<= 1;
                    now = op(okl,dat.at(l));
                    if(f(now)){okl = now; l++;}
                }
                return l-siz;
            } 
            okl = now;
        }
        for(int i=rs.size()-1; i>=0; i--){
            l = rs.at(i);
            SS now = op(okl,dat.at(l));
            if(!f(now)){
                while(l < siz){
                    l <<= 1;
                    now = op(okl,dat.at(l));
                    if(f(now)){okl = now; l++;}
                }
                return l-siz;
            } 
            okl = now;
        }
        return n;
    }
    int minleft(const function<bool(SS)> f,int r = -1){
        //fを満たす最小の箇所を返す なければ0.
        if(r == -1) r = n;
        int l = siz; r += siz;
        vector<int> ls,rs;
        while(l < r){
            if(l&1) ls.push_back(l++);
            if(r&1) rs.push_back(--r);
            l >>= 1; r >>= 1; 
        }
        SS okr = e();
        for(int i=0; i<rs.size(); i++){
            r = rs.at(i);
            SS now = op(dat.at(r),okr);
            if(!f(now)){
                while(r < siz){
                    r <<= 1; r++;
                    now = op(dat.at(r),okr);
                    if(f(now)){okr = now; r--;}
                }
                return r+1-siz;
            }
            okr = now;
        }
        for(int i=ls.size()-1; i>=0; i--){
            r = ls.at(i);
            SS now = op(dat.at(r),okr);
            if(!f(now)){
                while(r < siz){
                    r <<= 1; r++;
                    now = op(dat.at(r),okr);
                    if(f(now)){okr = now; r--;}
                }
                return r+1-siz;
            }
            okr = now;
        }
        return 0;
    }
};

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T; cin >> T;
    while(T--){
        long long N,K; cin >> N >> K;
        vector<int> A(N);
        for(auto &a : A) cin >> a,a--;
        auto S = SAIS(A);
        auto L = LCP(S,A);
        L.push_back(0);

        int border = -1;
        auto f = [&](SS x) -> bool {return x>=border;};
        stack<pair<int,int>> st; st.push({0,N+1000});
        SegmentTree Z(L);

        bool end = false;
        for(int i=1; i<=N; i++){
            int l = L.at(i),k;
            while(st.size()){
                auto [ok,p] = st.top();
                if(p < i) st.pop();
                else{k = ok; break;}
            }
            for(; k++,k<=l;){
                border = k;
                int r = Z.maxright(f,i);
                K -= r-i+1;
                if(K <= 0){
                    for(int p=S.at(i); p<S.at(i)+k; p++) cout << A.at(p)+1 << (p+1==S.at(i)+k?"\n":" ");
                    end = true; break;
                }
                st.push({k,r});
            }
            k--;
            if(end) break;
            int len = N-S.at(i);
            len -= k;
            if(K <= len){
                for(int p=S.at(i); p<S.at(i)+K+k; p++) cout << A.at(p)+1 << (p+1==S.at(i)+K+k?"\n":" ");
                break;
            }
            K -= len;
        }
    }   
}
0