結果

問題 No.1619 Coccinellidae
ユーザー mugen_1337mugen_1337
提出日時 2021-07-22 22:16:54
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 197 ms / 2,000 ms
コード長 5,573 bytes
コンパイル時間 2,606 ms
コンパイル使用メモリ 222,976 KB
実行使用メモリ 8,316 KB
最終ジャッジ日時 2023-09-24 17:23:52
合計ジャッジ時間 5,646 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 152 ms
6,996 KB
testcase_02 AC 193 ms
8,316 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 AC 197 ms
8,084 KB
testcase_05 AC 111 ms
6,148 KB
testcase_06 AC 2 ms
4,384 KB
testcase_07 AC 116 ms
6,220 KB
testcase_08 AC 110 ms
6,160 KB
testcase_09 AC 2 ms
4,376 KB
testcase_10 AC 99 ms
5,808 KB
testcase_11 AC 137 ms
6,916 KB
testcase_12 AC 1 ms
4,380 KB
testcase_13 AC 189 ms
7,876 KB
testcase_14 AC 193 ms
8,072 KB
testcase_15 AC 2 ms
4,376 KB
testcase_16 AC 1 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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<ll> V;
    V.insert(0,0);

    for(ll i=1;i<N;i++){
        ll p=i;
        if(K>=p){
            K-=p;
            V.insert(0,i);
        }else{
            ll sz=i;
            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-1) V[i]+=M-S;
    }

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