結果
| 問題 | No.3188 K-th Lexmin |
| コンテスト | |
| ユーザー |
 Blackjack
|
| 提出日時 | 2026-02-17 19:43:21 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 225 ms / 3,500 ms |
| コード長 | 11,619 bytes |
| 記録 | |
| コンパイル時間 | 5,704 ms |
| コンパイル使用メモリ | 361,476 KB |
| 実行使用メモリ | 14,028 KB |
| 最終ジャッジ日時 | 2026-02-17 19:43:41 |
| 合計ジャッジ時間 | 17,952 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 47 |
ソースコード
#define _USE_MATH_DEFINES
#include<bits/stdc++.h>
#define OVERLOAD_REP(v1, v2, v3, v4, NAME, ...) NAME
#define REP1(i, n) for (int i = 0; (i) < (n); ++(i))
#define REP2(i, l, r) for (int i = (l); (i) < (r); ++(i))
#define REP3(i, l, r, d) for (int i = (l); (i) < (r); (i)+=(d))
#define rep(...) OVERLOAD_REP(__VA_ARGS__, REP3, REP2, REP1)(__VA_ARGS__)
#define OVERLOAD_PRE(v1, v2, v3, v4, NAME, ...) NAME
#define PRE1(i, n) for (int i = (n)-1; (i) >= 0; --(i)) // [0,n)
#define PRE2(i, l, r) for (int i = (r)-1; (i) >= (l); --(i)) //[l,r)
#define PRE3(i, l, r, d) for (int i = (r)-1; (i) >= (l); (i)-=(d))
#define pre(...) OVERLOAD_PRE(__VA_ARGS__, PRE3, PRE2, PRE1)(__VA_ARGS__)
#define bg begin()
#define en end()
#define rbg rbegin()
#define ren rend()
#define all(x) x.bg,x.en
#define rall(x) x.rbg,x.ren
#define pf push_front
#define pb push_back
#define eb emplace_back
#define fir first
#define sec second
#define sz(x) ((int)(x).size())
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using sti = stack<int>;
using sei = set<int>;
using qi = queue<int>;
using qii = queue<pii>;
using dqi = deque<int>;
template<class t, class s> using umap = unordered_map<t,s>;
template<class t> using uset = unordered_set<t>;
template<class t> using mset = multiset<t>;
template<class t> using pq=priority_queue<t>;
template<class t> using pqg=priority_queue<t,vector<t>, greater<t>>;
template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;
template<class t> using vvvc=vc<vc<vc<t>>>;
using vi=vc<int>;
using vvi=vc<vc<int>>;
using vll=vc<ll>;
using vvll=vc<vc<ll>>;
using vd=vc<double>;
using vvd=vc<vc<double>>;
using vb=vc<bool>;
using vvb=vc<vc<bool>>;
using vch=vc<char>;
using vs=vc<string>;
const int inf = 1001001001;
const ll infl = 1LL << 60;
const ll mod = 998244353;
template<class t,class u> bool chmax(t&a,u b){if(a<b){a=b; return true;} return false;}
template<class t,class u> bool chmin(t&a,u b){if(a>b){a=b; return true;} return false;}
void yes(){ cout << "Yes" << '\n'; }
void no(){ cout << "No" << '\n'; }
// Suffix Arrayを返す
// (0,1,…,n−1)の順列であって、各i=0,1,⋯,n−2 について s[sa[i]..n) < s[sa[i+1]..n) を満たすもの。
vi sa_naive(const vi& s) {
int n = sz(s);
vi sa(n);
iota(all(sa), 0);
sort(all(sa), [&](int l, int r) {
if (l == r) return false;
while (l < n && r < n) {
if (s[l] != s[r]) return s[l] < s[r];
l++; r++;
}
return l == n;
});
return sa;
}
vi sa_doubling(const vi& s) {
int n = sz(s);
vi sa(n), rnk = s, tmp(n);
iota(all(sa), 0);
for (int k = 1; k < n; k *= 2) {
auto cmp = [&](int x, int y) {
if (rnk[x] != rnk[y]) return rnk[x] < rnk[y];
int rx = x + k < n ? rnk[x + k] : -1;
int ry = y + k < n ? rnk[y + k] : -1;
return rx < ry;
};
sort(all(sa), cmp);
tmp[sa[0]] = 0;
rep(i, 1, n) {
tmp[sa[i]] = tmp[sa[i - 1]] + (cmp(sa[i - 1], sa[i]) ? 1 : 0);
}
swap(tmp, rnk);
}
return sa;
}
// SA-IS, linear-time suffix array construction
// Reference:
// G. Nong, S. Zhang, and W. H. Chan,
// Two Efficient Algorithms for Linear Time Suffix Array Construction
template <int THRESHOLD_NAIVE = 10, int THRESHOLD_DOUBLING = 40>
vi sa_is(const vi& s, int upper) {
int n = sz(s);
if (n == 0) return {};
if (n == 1) return {0};
if (n == 2) {
if (s[0] < s[1]) return {0, 1};
else return {1, 0};
}
if (n < THRESHOLD_NAIVE) return sa_naive(s);
if (n < THRESHOLD_DOUBLING) return sa_doubling(s);
vi sa(n);
vb ls(n);
pre(i, n-1) ls[i] = (s[i] == s[i + 1]) ? ls[i + 1] : (s[i] < s[i + 1]);
vi sum_l(upper + 1), sum_s(upper + 1);
rep(i, n){
if (!ls[i]) sum_s[s[i]]++;
else sum_l[s[i] + 1]++;
}
rep(i, upper+1) {
sum_s[i] += sum_l[i];
if (i < upper) sum_l[i + 1] += sum_s[i];
}
auto induce = [&](const vi& lms) {
fill(all(sa), -1);
vi buf(upper + 1);
copy(all(sum_s), buf.bg);
for (auto d : lms) {
if (d == n) continue;
sa[buf[s[d]]++] = d;
}
copy(all(sum_l), buf.bg);
sa[buf[s[n - 1]]++] = n - 1;
rep(i, n){
int v = sa[i];
if (v >= 1 && !ls[v - 1]) sa[buf[s[v - 1]]++] = v - 1;
}
copy(all(sum_l), buf.bg);
pre(i, n){
int v = sa[i];
if (v >= 1 && ls[v - 1]) sa[--buf[s[v - 1] + 1]] = v - 1;
}
};
vi lms_map(n + 1, -1);
int m = 0;
rep(i, 1, n) if (!ls[i - 1] && ls[i]) lms_map[i] = m++;
vi lms;
lms.reserve(m);
rep(i, 1, n) if (!ls[i - 1] && ls[i]) lms.push_back(i);
induce(lms);
if (m) {
vi sorted_lms;
sorted_lms.reserve(m);
for (int v : sa) if (lms_map[v] != -1) sorted_lms.push_back(v);
vi rec_s(m);
int rec_upper = 0;
rec_s[lms_map[sorted_lms[0]]] = 0;
rep(i, 1, m){
int l = sorted_lms[i - 1], r = sorted_lms[i];
int end_l = (lms_map[l] + 1 < m) ? lms[lms_map[l] + 1] : n;
int end_r = (lms_map[r] + 1 < m) ? lms[lms_map[r] + 1] : n;
bool same = true;
if (end_l - l != end_r - r) same = false;
else {
while (l < end_l) {
if (s[l] != s[r]) break;
l++; r++;
}
if (l == n || s[l] != s[r]) same = false;
}
if (!same) rec_upper++;
rec_s[lms_map[sorted_lms[i]]] = rec_upper;
}
auto rec_sa = sa_is<THRESHOLD_NAIVE, THRESHOLD_DOUBLING>(rec_s, rec_upper);
rep(i,m) sorted_lms[i] = lms[rec_sa[i]];
induce(sorted_lms);
}
return sa;
}
// O(N+upper)
vi suffix_array(const vi& s, int upper) {
assert(0 <= upper);
for (int d : s) assert(0 <= d && d <= upper);
auto sa = sa_is(s, upper);
return sa;
}
// O(NlogN)
template <class T>
vi suffix_array(const vector<T>& s) {
int n = sz(s);
vi idx(n);
iota(all(idx), 0);
sort(all(idx), [&](int l, int r) { return s[l] < s[r]; });
vi s2(n);
int now = 0;
rep(i, n){
if (i && s[idx[i - 1]] != s[idx[i]]) now++;
s2[idx[i]] = now;
}
return sa_is(s2, now);
}
// O(N)
vi suffix_array(const string& s) {
int n = sz(s);
vi s2(n);
rep(i, n) s2[i] = s[i];
return sa_is(s2, 255);
}
// i番目の要素は s[sa[i]..n), s[sa[i+1]..n) の LCP(Longest Common Prefix) の長さ。
template <class T>
vi lcp_array(const vc<T>& s, const vi& sa) {
assert(sz(s) == sz(sa));
int n = sz(s);
assert(n >= 1);
vi rnk(n);
rep(i, n) {
assert(0 <= sa[i] && sa[i] < n);
rnk[sa[i]] = i;
}
vi lcp(n - 1);
int h = 0;
rep(i, n) {
if (h > 0) h--;
if (rnk[i] == 0) continue;
int j = sa[rnk[i] - 1];
for (; j + h < n && i + h < n; h++) {
if (s[j + h] != s[i + h]) break;
}
lcp[rnk[i] - 1] = h;
}
return lcp;
}
vi lcp_array(const string& s, const vi& sa) {
int n = sz(s);
vi s2(n);
rep(i, n) s2[i] = s[i];
return lcp_array(s2, sa);
}
template <class S, S (*op)(S, S), S (*e)()>
struct segtree {
int _n,size=1,log=0;
vc<S> d; //1-indexed
segtree(): segtree(0){}
segtree(int n): segtree(vc<S>(n,e())){}
segtree(const vc<S> &v): _n(sz(v)){
while(_n>size) size<<=1, log++;
d.assign(2*size,e());
rep(i,_n) d[size+i]=v[i];
pre(i,1,size) update(i);
}
void update(int k) { d[k]=op(d[2*k], d[2*k+1]); }
void set(int p, S x){
assert(0 <= p && p < _n);
p+=size;
d[p]=x;
rep(i,1,log+1) update(p>>i);
}
S get(int p) const {
assert(0 <= p && p < _n);
return d[p+size];
}
S prod(int l, int r) const {
assert(0 <= l && l <= r && r <= _n);
S sml=e(), smr=e();
l+=size; r+=size;
while(l<r){
if(l&1) sml=op(sml,d[l++]);
if(r&1) smr=op(d[--r],smr);
l>>=1; r>>=1;
}
return op(sml,smr);
}
S all_prod() const { return d[1]; }
template <bool (*f)(S)> int max_right(int l, int r) const {
return min(r, max_right(l, [](S x) { return f(x); }));
}
template <bool (*f)(S)> int max_right(int l) const {
return max_right(l, [](S x) { return f(x); });
}
template <class F> int max_right(int l, int r, F f) const {
return min(r, max_right<F>(l, f));
}
template <class F> int max_right(int l, F f) const {
assert(0 <= l && l <= _n);
assert(f(e()));
if (l == _n) return _n;
l += size;
S sm = e();
do {
while (l % 2 == 0) l >>= 1;
if (!f(op(sm, d[l]))) {
while (l < size) {
l = (2 * l);
if (f(op(sm, d[l]))) {
sm = op(sm, d[l]);
l++;
}
}
return l - size;
}
sm = op(sm, d[l]);
l++;
} while ((l & -l) != l);
return _n;
}
template <bool (*f)(S)> int min_left(int l, int r) const {
return max(l, min_left(r, [](S x) { return f(x); }));
}
template <bool (*f)(S)> int min_left(int r) const {
return min_left(r, [](S x) { return f(x); });
}
template <class F> int min_left(int l, int r, F f) const {
return max(l, min_left<F>(r, f));
}
template <class F> int min_left(int r, F f) const {
assert(0 <= r && r <= _n);
assert(f(e()));
if (r == 0) return 0;
r += size;
S sm = e();
do {
r--;
while (r > 1 && (r % 2)) r >>= 1;
if (!f(op(d[r], sm))) {
while (r < size) {
r = (2 * r + 1);
if (f(op(d[r], sm))) {
sm = op(d[r], sm);
r--;
}
}
return r + 1 - size;
}
sm = op(d[r], sm);
} while ((r & -r) != r);
return 0;
}
inline S operator[](int i) { return get(i); }
/* debug */
void print() {
cerr << "print: ";
rep(i,_n){
cerr << (*this)[i];
if(i!=_n) cerr << " ";
}
cerr << endl;
}
};
// 一点更新型のRMinQ
using S=pii;
S op(S a, S b) { return min(a, b); }
S e() { return {inf,inf}; }
void solve(){
int n; ll k; cin >> n >> k;
vi a(n);
rep(i,n) cin >> a[i];
vi sa=suffix_array(a,n);
vi lcp=lcp_array(a,sa);
vc<S> v(n-1);
rep(i,n-1) v[i]={lcp[i],i};
segtree<S,op,e> seg(v);
auto f=[&](auto f,int l,int r,int d)->bool{
if(l>=r) return false;
if(l+1==r){
if(k<=n-sa[l]-d){
rep(i,d+k) cout << a[sa[l]+i] << ' ';
cout << endl;
return true;
}else{
k-=n-sa[l]-d;
return false;
}
}
auto [m,ind]=seg.prod(l,r-1);
ll add=(ll)(m-d)*(r-l);
if(k<=add){
int x=(k+r-l-1)/(r-l);
rep(i,d+x) cout << a[sa[l]+i] << ' ';
cout << endl;
return true;
}
k-=add;
if(f(f,l,ind+1,m)) return true;
if(f(f,ind+1,r,m)) return true;
return false;
};
f(f,0,n,0);
}
//重複ありver
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t; cin >> t;
rep(i,t) solve();
return 0;
}