#line 1 "Main.cpp" #include #include #include #include #include #line 2 "nachia\\misc\\sorting.hpp" #line 4 "nachia\\misc\\sorting.hpp" #include #line 6 "nachia\\misc\\sorting.hpp" namespace nachia{ template void EnsurePermutation(Iterator first, Iterator last){ int n = std::distance(first, last); std::vector vis(n, 0); for(Iterator i=first; i!=last; i++){ assert(0 <= *i); assert(*i < n); assert(vis[*i] == 0); vis[*i] = 1; } } template std::vector Permute( const std::vector& src, const std::vector& perm ){ const bool DEBUG = true; int n = src.size(); if constexpr (DEBUG){ assert(perm.size() == src.size()); EnsurePermutation(perm.begin(), perm.end()); } std::vector res; res.reserve(n); for(int i=0; i std::vector& PermuteInPlace( std::vector& src, std::vector perm ){ const bool DEBUG = true; int n = src.size(); if constexpr (DEBUG){ assert(perm.size() == src.size()); EnsurePermutation(perm.begin(), perm.end()); } for(int s=0; s BucketSortPermutation( std::vector::const_iterator first, std::vector::const_iterator last, int maxVal ){ const bool DEBUG = true; int n = last - first; if constexpr (DEBUG){ for(auto itr = first; itr != last; itr++){ assert(0 <= *itr); assert(*itr <= maxVal); } } std::vector cnt(maxVal+2); std::vector res(n); for(int i=0; i std::vector BucketSortPermutation( typename std::vector::const_iterator first, typename std::vector::const_iterator last, const Mapping& f, int maxVal ){ std::vector buf(last - first); auto bufitr = buf.begin(); for(auto itr = first; itr != last; itr++, bufitr++) *bufitr = f(*itr); return BucketSortPermutation(buf.begin(), buf.end(), maxVal); } // stable sort template std::vector BucketSort( std::vector src, const Mapping& f, int maxVal ){ return PermuteInPlace(src, BucketSortPermutation(src.begin(), src.end(), f, maxVal)); } // stable sort template std::vector BucketSortPermutation( Iter first, Iter last, const Mapping& f, int maxVal ){ std::vector buf(std::distance(first, last)); auto bufitr = buf.begin(); for(auto itr = first; itr != last; itr++, bufitr++) *bufitr = f(*itr); return BucketSortPermutation(buf.begin(), buf.end(), maxVal); } template void PermuteInPlace( Iter srcFirst, Iter srcLast, std::vector perm ){ const bool DEBUG = true; int n = std::distance(srcFirst, srcLast); if constexpr (DEBUG){ assert(perm.size() == (size_t)n); EnsurePermutation(perm.begin(), perm.end()); } for(int s=0; s void BucketSort( Iter destFirst, Iter destLast, const Mapping& f, int maxVal ){ PermuteInPlace(destFirst, destLast, BucketSortPermutation(destFirst, destLast, f, maxVal)); } } #line 2 "nachia\\array\\csr-array.hpp" #include #line 5 "nachia\\array\\csr-array.hpp" namespace nachia{ template class CsrArray{ public: struct ListRange{ using iterator = typename std::vector::iterator; iterator begi, endi; iterator begin() const { return begi; } iterator end() const { return endi; } int size() const { return (int)std::distance(begi, endi); } Elem& operator[](int i) const { return begi[i]; } }; struct ConstListRange{ using iterator = typename std::vector::const_iterator; iterator begi, endi; iterator begin() const { return begi; } iterator end() const { return endi; } int size() const { return (int)std::distance(begi, endi); } const Elem& operator[](int i) const { return begi[i]; } }; private: int m_n; std::vector m_list; std::vector m_pos; public: CsrArray() : m_n(0), m_list(), m_pos() {} static CsrArray Construct(int n, std::vector> items){ CsrArray res; res.m_n = n; std::vector buf(n+1, 0); for(auto& [u,v] : items){ ++buf[u]; } for(int i=1; i<=n; i++) buf[i] += buf[i-1]; res.m_list.resize(buf[n]); for(int i=(int)items.size()-1; i>=0; i--){ res.m_list[--buf[items[i].first]] = std::move(items[i].second); } res.m_pos = std::move(buf); return res; } static CsrArray FromRaw(std::vector list, std::vector pos){ CsrArray res; res.m_n = pos.size() - 1; res.m_list = std::move(list); res.m_pos = std::move(pos); return res; } ListRange operator[](int u) { return ListRange{ m_list.begin() + m_pos[u], m_list.begin() + m_pos[u+1] }; } ConstListRange operator[](int u) const { return ConstListRange{ m_list.begin() + m_pos[u], m_list.begin() + m_pos[u+1] }; } int size() const { return m_n; } int fullSize() const { return (int)m_list.size(); } }; } // namespace nachia #line 8 "nachia\\array\\point-update-lex-sort.hpp" namespace nachia { template struct PointUpdateLexSort{ public: using MyType = PointUpdateLexSort; private: int k = 0; std::vector valbuf; std::vector mutpos; std::vector sPos; int xsPos = 0; struct DfsNode{ std::vector TBuf, TList, TPos, VBuf; PointUpdateLexSort *p; static void ToInt(std::vector::iterator dest, std::vector> pairs, int z1, int z2){ int n = pairs.size(); std::vector I = nachia::BucketSortPermutation(pairs.begin(), pairs.end(), [&](std::pair& x){ return x.second; }, z2-1); I = nachia::BucketSort(std::move(I), [&](int i){ return pairs[i].first; }, z1-1); dest[I[0]] = 0; for(int i=1; ivalbuf.size(); TBuf.resize(n); TList.resize(n); TPos.resize(p->k + 2, 1); VBuf.resize(n); TPos[0] = TPos[1] = 0; for(auto& m : p->mutpos) TPos[m+2]++; for(int i=0; i<=p->k; i++) TPos[i+1] += TPos[i]; for(int i=0; ik; i++) TList[TPos[i+1]++] = i; for(int i=p->k; imutpos[i-p->k]+1]++] = i; } void dfs(int l, int r){ if(l+1 == r){ auto I = TBuf.begin(); int sz = TPos[r] - TPos[l]; for(int i=0; ivalbuf[TList[l]] < p->valbuf[TList[r]]; }); int sp = VBuf[I[0]] = 0; for(int i=1; ivalbuf[TList[I[i-1]]] < p->valbuf[TList[I[i]]] ? 1 : 0); } return; } int m = (l+r)/2; dfs(l, m); dfs(m, r); int pql = TPos[l], pqr = TPos[m]; int pqlz = TPos[l+1], pqrz = TPos[m+1]; int bufi = TPos[l]; std::vector> tmp; TBuf[bufi++] = TList[pqr]; tmp.emplace_back(VBuf[pql++], VBuf[pqr++]); while(pql < pqlz || pqr < pqrz){ bool choosel = true; if(pql == pqlz) choosel = false; else if(pqr == pqrz) choosel = true; else choosel = TList[pql] < TList[pqr]; if(choosel){ TBuf[bufi] = TList[pql]; tmp.emplace_back(VBuf[pql], tmp.back().second); pql++; } else{ TBuf[bufi] = TList[pqr]; tmp.emplace_back(tmp.back().first, VBuf[pqr]); pqr++; } bufi++; } ToInt(VBuf.begin() + TPos[l], std::move(tmp), pqlz-TPos[l], pqrz-TPos[m]); TPos[l+1] = bufi; for(int i=TPos[l]; isPos[i]; } }; PointUpdateLexSort(){} PointUpdateLexSort(std::vector A){ k = A.size(); valbuf = std::move(A); } Iter mutate(int pos, T val){ assert(0 <= pos); assert(pos < k); valbuf.push_back(std::move(val)); mutpos.emplace_back(pos); return Iter{ this, (int)mutpos.size() }; } int count() const { return (int)mutpos.size() + 1; } int maxSortedPos() const { return xsPos; } Iter last() const { return Iter{ this, count()-1 }; } void proc(){ auto v = DfsNode(); v.MakeTBuf(this); v.dfs(0, k); v.VBuf.resize(count()); sPos = std::move(v.VBuf); xsPos = *std::max_element(sPos.begin(), sPos.end()); } }; } // namespace nachia #line 7 "Main.cpp" using namespace std; using i32 = int; using u32 = unsigned int; using i64 = long long; using u64 = unsigned long long; #define rep(i,n) for(int i=0; i<(int)(n); i++) const i64 INF = 1001001001001001001; using Modint = atcoder::static_modint<998244353>; int main(){ int N, K; cin >> N >> K; vector A(N); rep(i,N) cin >> A[i]; nachia::PointUpdateLexSort ds(vector(A.begin()+1, A.end())); vector::Iter> Q; Q.push_back(ds.last()); rep(i,N-1){ ds.mutate(i, A[i]); Q.push_back(ds.last()); } ds.proc(); vector B(N); rep(i,N) B[i] = i; sort(B.begin(), B.end(), [&](int l, int r){ return *Q[l] < *Q[r]; }); int k = B[K-1]; vector C; rep(i,N) if(i != k) C.push_back(A[i]); rep(i,N-1){ if(i) cout << ' '; cout << C[i]; } cout << endl; return 0; } struct ios_do_not_sync{ ios_do_not_sync(){ ios::sync_with_stdio(false); cin.tie(nullptr); } } ios_do_not_sync_instance;