#838494 (C++17) No.2210 equence Squence Seuence

提出ソース

結果

問題	No.2210 equence Squence Seuence
ユーザー	👑 Nachia
提出日時	2023-02-10 21:24:32
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	239 ms / 2,000 ms
コード長	11,113 bytes
コンパイル時間	1,415 ms
コンパイル使用メモリ	101,032 KB
実行使用メモリ	20,408 KB
最終ジャッジ日時	2023-09-21 22:25:17
合計ジャッジ時間	8,347 ms
ジャッジサーバーID （参考情報）	judge14 / judge15

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 4,376 KB
testcase_01	AC	1 ms 4,376 KB
testcase_02	AC	1 ms 4,380 KB
testcase_03	AC	47 ms 6,464 KB
testcase_04	AC	53 ms 7,244 KB
testcase_05	AC	84 ms 8,980 KB
testcase_06	AC	71 ms 8,488 KB
testcase_07	AC	188 ms 17,180 KB
testcase_08	AC	2 ms 4,376 KB
testcase_09	AC	1 ms 4,376 KB
testcase_10	AC	2 ms 4,376 KB
testcase_11	AC	2 ms 4,376 KB
testcase_12	AC	2 ms 4,380 KB
testcase_13	AC	239 ms 20,152 KB
testcase_14	AC	235 ms 20,124 KB
testcase_15	AC	235 ms 20,072 KB
testcase_16	AC	234 ms 19,984 KB
testcase_17	AC	232 ms 20,408 KB
testcase_18	AC	2 ms 4,376 KB
testcase_19	AC	1 ms 4,376 KB
testcase_20	AC	1 ms 4,380 KB
testcase_21	AC	2 ms 4,380 KB
testcase_22	AC	1 ms 4,376 KB
testcase_23	AC	163 ms 16,980 KB
testcase_24	AC	120 ms 12,980 KB
testcase_25	AC	143 ms 15,480 KB
testcase_26	AC	193 ms 19,340 KB
testcase_27	AC	52 ms 7,392 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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;

yukicoder

結果

テストケース

ソースコード