結果
| 問題 | No.3188 K-th Lexmin |
| コンテスト | |
| ユーザー |
 Blackjack
|
| 提出日時 | 2026-02-17 15:41:56 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 8,363 bytes |
| 記録 | |
| コンパイル時間 | 4,218 ms |
| コンパイル使用メモリ | 362,596 KB |
| 実行使用メモリ | 10,084 KB |
| 最終ジャッジ日時 | 2026-02-17 15:42:22 |
| 合計ジャッジ時間 | 24,411 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 46 TLE * 1 |
ソースコード
#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);
}
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);
vll sum(n+1);
rep(i,n) sum[i+1]=sum[i]+(n-sa[i]);
int l=0,r=n,d=0;
while(1){
int cur=l;
while(cur<r){
int next=cur;
while(next<r-1&&lcp[next]>d) next++;
next++;
ll cnt=sum[next]-sum[cur]-(ll)(next-cur)*d;
if(k<=cnt){
if(k<=next-cur){
int ind=sa[cur];
rep(i,d+1) cout << a[ind+i] << ' ';
cout << endl;
return;
}
k-=next-cur;
l=cur;
r=next;
d++;
break;
}else{
k-=cnt;
cur=next;
}
}
}
}
//重複ありver
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t; cin >> t;
rep(i,t) solve();
return 0;
}