結果

問題 No.3188 K-th Lexmin
コンテスト
ユーザー miscalc
提出日時 2025-12-05 04:18:17
言語 C++23
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 347 ms / 3,500 ms
コード長 4,528 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 7,212 ms
コンパイル使用メモリ 309,244 KB
実行使用メモリ 60,448 KB
最終ジャッジ日時 2025-12-05 04:18:48
合計ジャッジ時間 23,076 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 47
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

using ll = long long;
using pll = pair<ll, ll>;
#define vc vector
using vl = vc<ll>;

#define ov(a, b, c, name, ...) name
#define rep2(i, a, b) for(ll i = (a); i < ll(b); i++)
#define rep1(i, n) rep2(i, 0, n)
#define rep(...) ov(__VA_ARGS__, rep2, rep1)(__VA_ARGS__)
#define fec(...) for(const auto& __VA_ARGS__)
#define per(i, a, b) for(ll i = ll(a) - 1; i >= ll(b); i--)

bool chmin(auto& a, auto b) { return a > b ? a = b, 1 : 0; }
bool chmax(auto& a, auto b) { return a < b ? a = b, 1 : 0; }
const ll INF = ll(4e18) + 100;

#define ALL(x) begin(x), end(x)
#define SZ(x) (ll) size(x)
#define LB(v, x) (lower_bound(ALL(v), x) - begin(v))
#define eb emplace_back

void printvec(const auto& v) {
    for(auto it = begin(v); it != end(v); it++) cout << *it << " ";
    cout << endl;
}

#ifdef LOCAL
#define local(...) __VA_ARGS__
#else
#define local(...)
#endif

// returns pair{sa, lcp}
// sa 長さ n : s[sa[0]:] < s[sa[1]:] < … < s[sa[n-1]:]
// lcp 長さ n-1 : lcp[i] = LCP(s[sa[i]:], s[sa[i+1]:])
// s が数列のとき: 要素は非負で 10^6 程度 (必要なら座圧)
auto SA(const auto &s) {
    ll n = s.size() + 1;
    ll lim = s.empty() ? 0 : ranges::max(s) + 2;
    vl sa(n), lcp(n), x(n), y(n), ws(max(n, lim)), rk(n);
    rep(i, s.size()) x[i] = s[i] + 1;
    iota(ALL(sa), 0);
    for(ll j = 0, p = 0; p < n; j = max(1LL, j * 2), lim = p) {
        p = j, iota(ALL(y), n - j);
        rep(i, n) if(sa[i] >= j) y[p++] = sa[i] - j;
        fill(ALL(ws), 0);
        rep(i, n) ws[x[i]]++;
        rep(i, 1, lim) ws[i] += ws[i - 1];
        for(ll i = n; i--;) sa[--ws[x[y[i]]]] = y[i];
        swap(x, y), p = 1, x[sa[0]] = 0;
        rep(i, 1, n) {
            ll a = sa[i - 1], b = sa[i], c = a + j, d = b + j;
            x[b] = (y[a] == y[b] && y[c] == y[d]) ? p - 1 : p++;
        }
    }
    rep(i, 1, n) rk[sa[i]] = i;
    for(ll i = 0, k = 0; i < n - 1; lcp[rk[i++]] = k) {
        if(k) k--;
        ll j = sa[rk[i] - 1];
        while(i + k < n - 1 && j + k < n - 1 && s[i + k] == s[j + k]) k++;
    }
    sa.erase(begin(sa)), lcp.erase(begin(lcp));
    return pair{sa, lcp};
}

// depends on suffix-array
// ノード v からノード nv に行くことは
// pos[nv] + len[v] から len[nv] - len[v] 文字を追加すること
auto suffix_tree(const auto& s, const auto& sa, const auto& lcp) {
    vl len{0}, pos{-1}, par{-1}, st{0};
    rep(i, s.size()) {
        int h = lcp[i], u = -1;
        while(len[st.back()] > h) u = st.back(), st.pop_back();
        if(len[st.back()] < h) {
            int v = len.size();
            len.eb(h), pos.eb(pos[u]), par.eb(st.back());
            par[u] = v, st.eb(v);
        }
        len.eb(SZ(s) - sa[i]), pos.eb(sa[i]), par.eb(st.back());
        st.eb(SZ(len) - 1);
    }
    vc<vc<int>> chi(len.size());
    rep(i, 1, len.size()) chi[par[i]].eb(i);
    rep(i, len.size()) {
        auto proj = [&](int c) { return s[pos[c] + len[i]]; };
        ranges::sort(chi[i], {}, proj);
    }
    return tuple{len, pos, par, chi};
}

void main2()
{
    ll N, K;
    cin >> N >> K;
    vl A(N);
    rep(i, N) cin >> A.at(i);

    auto [sa, lcp] = SA(A);
    auto [len, pos, par, chi] = suffix_tree(A, sa, lcp);

    vl siz(SZ(len));
    {
        auto dfs = [&](auto dfs, ll v) -> void
        {
            if (pos.at(v) + len.at(v) == N) siz.at(v)++;
            fec(nv : chi.at(v))
            {
                dfs(dfs, nv);
                siz.at(v) += siz.at(nv);
            }
        };
        dfs(dfs, 0);
    }
    local(cout << "len ", printvec(len));
    local(cout << "pos ", printvec(pos));
    local(cout << "siz ", printvec(siz));

    bool finish = false;
    auto dfs = [&](auto dfs, ll v) -> void
    {
        if (finish) return;
        fec(nv : chi.at(v))
        {
            if (finish) break;
            ll cnt = siz.at(nv) * (len.at(nv) - len.at(v));
            local(cout << "v=" << v << " nv=" << nv << " cnt=" << cnt << endl);
            if (K - cnt > 0) K -= cnt;
            else
            {
                ll d = (K - 1) / siz.at(nv) + 1;
                vl ans = {A.begin() + pos.at(nv), A.begin() + pos.at(nv) + len.at(v) + d};
                printvec(ans);
                finish = true;
                return;
            }
            dfs(dfs, nv);
        }
    };
    dfs(dfs, 0);
}

int main() {
#ifndef LOCAL
    cin.tie(0)->sync_with_stdio(0), cout.tie(0);
#endif

    local(while(true)) {
        ll t = 1;
        cin >> t;
        while(t--) main2();
    }
}
0