#681758 (C++17) No.1619 Coccinellidae

• 問題: No.1619 Coccinellidae
• ユーザー: mugen_1337
• 提出日時: 2021-07-22 22:10:14
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: WA
• 実行時間: -
• コード長: 5,564 bytes
• コンパイル時間: 2,455 ms
• コンパイル使用メモリ: 223,832 KB
• 最終ジャッジ日時: 2025-01-23 06:49:15
• ジャッジサーバーID （参考情報）: judge4 / judge2

ファイルパターン	結果
sample	AC * 1
other	AC * 3 WA * 13

ソースコード

#include<bits/stdc++.h>
using namespace std;
#define ALL(x) begin(x),end(x)
#define rep(i,n) for(int i=0;i<(n);i++)
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl;
#define mod 1000000007
using ll=long long;
const int INF=1000000000;
const ll LINF=1001002003004005006ll;
int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
// ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;}

struct IOSetup{
    IOSetup(){
        cin.tie(0);
        ios::sync_with_stdio(0);
        cout<<fixed<<setprecision(12);
    }
} iosetup;

template<typename T>
ostream &operator<<(ostream &os,const vector<T>&v){
    for(int i=0;i<(int)v.size();i++) os<<v[i]<<(i+1==(int)v.size()?"":" ");
    return os;
}
template<typename T>
istream &operator>>(istream &is,vector<T>&v){
    for(T &x:v)is>>x;
    return is;
}

template<typename T>
struct Treap{

private:

    inline int xorshift() const {
        static int x=122312555;
        static int y=336261662;
        static int z=558127122;
        static int w=917277772;
        int t;
        t=x^(x<<11);
        x=y;y=z;z=w;
        return w=(w^(w>>19))^(t^(t>>8));
    }

    struct Node;
    using Ptr=unique_ptr<Node>;

    struct Node{
        Ptr l,r;
        int sz,pri;// priority
        T val;
        bool rev;
        Node()=default;
        Node(const T &val,int pri):
        l(nullptr),r(nullptr),sz(1),pri(pri),val(val),rev(false){}
    };
    Ptr root;

    explicit Treap(Ptr root):root(move(root)){}
    int size(Ptr &t)const{return (t?t->sz:0);}
    Ptr merge(Ptr l,Ptr r){
        if(!l) return move(r);
        if(!r) return move(l);
        push(l);push(r);
        if(l->pri>r->pri){
            l->r=merge(move(l->r),move(r));
            l->sz=size(l->l)+1+size(l->r);
            return move(l);
        }else{
            r->l=merge(move(l),move(r->l));
            r->sz=size(r->l)+1+size(r->r);
            return move(r);
        }
    }
    pair<Ptr,Ptr> split(Ptr t,int k){
        if(!t) return {nullptr,nullptr};
        push(t);
        if(k<=size(t->l)){
            auto x=split(move(t->l),k);
            t->l=move(x.second);
            t->sz=size(t->l)+1+size(t->r);
            return {move(x.first),move(t)};
        }else{
            auto x=split(move(t->r),k-size(t->l)-1);
            t->r=move(x.first);
            t->sz=size(t->l)+1+size(t->r);
            return {move(t),move(x.second)};
        }
    }
    T &access(Ptr &cur,int k){
        assert(cur);
        push(cur);
        if(k==size(cur->l)) return cur->val;
        if(k<size(cur->l))  return access(cur->l,k);
        else                return access(cur->r,k-1-size(cur->l));
    }
    void push(Ptr &t){
        if(t->rev){
            swap(t->l,t->r);
            if(t->l) t->l->rev^=true;
            if(t->r) t->r->rev^=true;
            t->rev=false;
        }
    }

public:

    Treap():root(nullptr){}

    void insert(int k,const T &x){
        auto s=split(move(root),k);
        Ptr i(new Node(x,xorshift()));
        root=merge(merge(move(s.first),move(i)),move(s.second));
    }

    void erase(int k){
        auto l=split(move(root),k);
        auto r=split(move(l.second),1);
        root=merge(move(l.first),move(r.second));
    }

    T &operator[](int k){ return access(root,k); }

    int size(){ return size(root); }

    void push_back(T x){
        Ptr b(new Node(x,xorshift()));
        root=merge(move(root),move(b));
    }
    void push_front(T x){
        Ptr f(new Node(x,xorshift()));
        root=merge(move(f),move(root));
    }
    void pop_back(){ root=split(move(root),1).second; }
    void pop_front(){ root=split(move(root),size()-1).second; }

    void reverse(int l,int r){
        auto x=split(move(root),l);
        auto y=split(move(x.second),r-l);
        y.first->rev^=true;
        root=merge(merge(move(x.first),move(y.first)),move(y.second));
    }

    void rotate(int l,int m,int r){
        reverse(l,r);
        reverse(l,l+r-m);
        reverse(l+r-m,r);
    }
    // [0, k) and [k, size)
    // cant use this after split
    pair<Treap<T>,Treap<T>> split(int k){
        auto x=split(move(root),k);
        return {Treap<T>(move(x.first)),Treap<T>(move(x.second))};
    }  
    // usage : auto new=l.merge(l, r);
    // cant use l and r after merge
    Treap<T> merge(Treap<T> &l,Treap<T> &r){
        return Treap<T>(merge(move(l.root),move(r.root)));
    }
};

template<typename T>
long long InversionNumber(vector<T> v){
    vector<T> ord=v;
    sort(begin(ord),end(ord));
    ord.erase(unique(begin(ord),end(ord)),end(ord));
    vector<long long> bit(ord.size()+1,0);
    long long ret=0;
    for(int i=0;i<(int)v.size();i++){
        int p=lower_bound(begin(ord),end(ord),v[i])-begin(ord)+1;
        for(int j=p;j;j-=(j&-j)) ret-=bit[j];
        for(int j=p;j<=(int)ord.size();j+=(j&-j)) bit[j]+=1;
        ret+=i;
    } 
    return ret;
}

signed main(){
    ll N,M,K;cin>>N>>M>>K;

    ll memk=K;

    Treap<int> V;
    V.insert(0,1);

    for(int i=2;i<=N;i++){
        int p=i-1;
        if(K>=p){
            K-=p;
            V.insert(0,i);
        }else{
            int sz=i-1;
            V.insert(sz-K,i);
            K=0;
        }
    }

    {
        vector<ll> w(N);
        rep(i,N) w[i]=V[i];

        assert(memk==InversionNumber(w));
    }

    ll S=0;
    rep(i,N) S+=V[i];
    rep(i,N){
        if(V[i]==N) V[i]+=M-S;
    }

    rep(i,N) cout<<V[i]<<endl;
    return 0;
}