結果
| 問題 |
No.2210 equence Squence Seuence
|
| コンテスト | |
| ユーザー |
 Nachia
|
| 提出日時 | 2023-02-10 21:24:32 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 261 ms / 2,000 ms |
| コード長 | 11,113 bytes |
| コンパイル時間 | 1,719 ms |
| コンパイル使用メモリ | 98,656 KB |
| 最終ジャッジ日時 | 2025-02-10 12:08:55 |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 25 |
ソースコード
#line 1 "Main.cpp"
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <atcoder/modint>
#line 2 "nachia\\misc\\sorting.hpp"
#line 4 "nachia\\misc\\sorting.hpp"
#include <cassert>
#line 6 "nachia\\misc\\sorting.hpp"
namespace nachia{
template<class Iterator>
void EnsurePermutation(Iterator first, Iterator last){
int n = std::distance(first, last);
std::vector<int> vis(n, 0);
for(Iterator i=first; i!=last; i++){
assert(0 <= *i);
assert(*i < n);
assert(vis[*i] == 0);
vis[*i] = 1;
}
}
template<class T> std::vector<T> Permute(
const std::vector<T>& src,
const std::vector<int>& perm
){
const bool DEBUG = true;
int n = src.size();
if constexpr (DEBUG){
assert(perm.size() == src.size());
EnsurePermutation(perm.begin(), perm.end());
}
std::vector<T> res;
res.reserve(n);
for(int i=0; i<n; i++) res.push_back(src[perm[i]]);
return res;
}
template<class T> std::vector<T>& PermuteInPlace(
std::vector<T>& src,
std::vector<int> 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<n; s++){
int p = s;
while(perm[p] != s){
std::swap(src[p], src[perm[p]]);
std::swap(p, perm[p]);
}
perm[p] = p;
}
return src;
}
// stable sort
std::vector<int> BucketSortPermutation(
std::vector<int>::const_iterator first,
std::vector<int>::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<int> cnt(maxVal+2);
std::vector<int> res(n);
for(int i=0; i<n; i++) cnt[first[i]+1]++;
for(int i=0; i<maxVal; i++) cnt[i+1] += cnt[i];
for(int i=0; i<n; i++) res[cnt[first[i]]++] = i;
return res;
}
// stable sort
template<class T, class Mapping>
std::vector<int> BucketSortPermutation(
typename std::vector<T>::const_iterator first,
typename std::vector<T>::const_iterator last,
const Mapping& f,
int maxVal
){
std::vector<int> 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<class T, class Mapping>
std::vector<T> BucketSort(
std::vector<T> src,
const Mapping& f,
int maxVal
){
return PermuteInPlace(src, BucketSortPermutation<T>(src.begin(), src.end(), f, maxVal));
}
// stable sort
template<class Iter, class Mapping>
std::vector<int> BucketSortPermutation(
Iter first,
Iter last,
const Mapping& f,
int maxVal
){
std::vector<int> 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<class Iter> void PermuteInPlace(
Iter srcFirst,
Iter srcLast,
std::vector<int> 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<n; s++){
int p = s;
while(perm[p] != s){
std::swap(srcFirst[p], srcFirst[perm[p]]);
std::swap(p, perm[p]);
}
perm[p] = p;
}
}
// stable sort
template<class Iter, class Mapping>
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 <utility>
#line 5 "nachia\\array\\csr-array.hpp"
namespace nachia{
template<class Elem>
class CsrArray{
public:
struct ListRange{
using iterator = typename std::vector<Elem>::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<Elem>::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<Elem> m_list;
std::vector<int> m_pos;
public:
CsrArray() : m_n(0), m_list(), m_pos() {}
static CsrArray Construct(int n, std::vector<std::pair<int, Elem>> items){
CsrArray res;
res.m_n = n;
std::vector<int> 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<Elem> list, std::vector<int> 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<class T>
struct PointUpdateLexSort{
public:
using MyType = PointUpdateLexSort;
private:
int k = 0;
std::vector<T> valbuf;
std::vector<int> mutpos;
std::vector<int> sPos;
int xsPos = 0;
struct DfsNode{
std::vector<int> TBuf, TList, TPos, VBuf;
PointUpdateLexSort *p;
static void ToInt(std::vector<int>::iterator dest, std::vector<std::pair<int,int>> pairs, int z1, int z2){
int n = pairs.size();
std::vector<int> I = nachia::BucketSortPermutation(pairs.begin(), pairs.end(), [&](std::pair<int,int>& 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; i<n; i++) dest[I[i]] = dest[I[i-1]] + (pairs[I[i-1]] < pairs[I[i]] ? 1 : 0);
}
void MakeTBuf(PointUpdateLexSort* pc){
p = pc;
int n = p->valbuf.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; i<p->k; i++) TList[TPos[i+1]++] = i;
for(int i=p->k; i<n; i++) TList[TPos[p->mutpos[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; i<sz; i++) I[i] = i + TPos[l];
std::sort(I, I + sz, [&](int l, int r){ return p->valbuf[TList[l]] < p->valbuf[TList[r]]; });
int sp = VBuf[I[0]] = 0;
for(int i=1; i<sz; i++){
VBuf[I[i]] = sp += (p->valbuf[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<std::pair<int, int>> 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]; i<bufi; i++) TList[i] = TBuf[i];
}
};
public:
struct Iter {
const MyType *p;
int i;
int operator*() const { return p->sPos[i]; }
};
PointUpdateLexSort(){}
PointUpdateLexSort(std::vector<T> 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<int> A(N); rep(i,N) cin >> A[i];
nachia::PointUpdateLexSort<int> ds(vector<int>(A.begin()+1, A.end()));
vector<nachia::PointUpdateLexSort<int>::Iter> Q;
Q.push_back(ds.last());
rep(i,N-1){
ds.mutate(i, A[i]);
Q.push_back(ds.last());
}
ds.proc();
vector<int> 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<int> 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;