Cod sursa(job #1941804)

Utilizator AlexandruRudiAlexandru Rudi AlexandruRudi Data 27 martie 2017 16:36:22
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.77 kb
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define dbg(x) cout << #x << '=' << x << '\n';
#define ll long long
#define pi pair<int,int>
#define pl pair<long long,long long>
#define rd(x) cin >> x;
#define rda(a,n) for(int i=1;i<=n;i++) cin >> a[i];
#define wr(x) cout << x << ' ';
#define wrl(x) cout << x << '\n';
#define wra(a,n) for(int i=1;i<=n;i++) cout << a[i] << ' '; cout << '\n';
#define lg length()
#define pb(x) push_back(x)
ifstream in("file.in");
ofstream out("file.out");
#define MAXN 100005
#define INF 1000000005
#define LINF 1000000000000000005
struct comp{
    bool operator()(int a, int b){
        return a>b;
    }
};

struct Treap{
    int v,p,h;
    Treap *L, *R;
    Treap(int v, int p, int h, Treap *L, Treap *R){
        this->v=v;
        this->p=p;
        this->h=h;
        this->L=L;
        this->R=R;
    }
} *T, *nil, *temp;

int n;

void RotR(Treap* &nod){
    Treap *t = nod->R;
    nod->h-=(1+t->R->h);
    t->h+=(1+nod->L->h);
    nod->R=t->L;
    t->L=nod;
    nod=t;
}

void RotL(Treap* &nod){
    Treap *t = nod->L;
    nod->h-=(1+t->L->h);
    t->h+=(1+nod->R->h);
    nod->L=t->R;
    t->R=nod;
    nod=t;
}

void Balance(Treap* &nod){
    if(nod->L->p > nod->p) RotL(nod);
    else if(nod->R->p > nod->p) RotR(nod);
}

void Insert(Treap* &nod, int v, int p){
    if(nod==nil){
        nod=new Treap(v,p,1,nil,nil);
        return;
    }
    nod->h++;
    if(nod->v>v) Insert(nod->L,v,p);
    else Insert(nod->R,v,p);
    Balance(nod);
}

void Erase(Treap* &nod, int v){
    if(nod==nil) return; //????????
    //WHy crash on equal elements?
    if(nod->v>v) Erase(nod->L,v),nod->h--;
    else if(nod->v<v) Erase(nod->R,v),nod->h--;
    else{
        if(nod->L==nil && nod->R==nil) delete nod,nod=nil;
        else{
            if(nod->L->p > nod->R->p)  RotL(nod);
            else RotR(nod);
            Erase(nod,v);
        }
    }
}

bool Search(Treap* &nod, int v){
    if(nod==nil) return 0;
    if(nod->v==v) return 1;
    else if(nod->v>v) return Search(nod->L,v);
    else return Search(nod->R,v);
}

Treap* Find(Treap* &nod, int k){
    if(nod->L->h==k-1) return nod;
    else if(nod->L->h>k-1) return Find(nod->L,k);
    else return Find(nod->R,k-nod->L->h-1);
}

int main(){
    ios_base :: sync_with_stdio(0);
    ifstream in("order.in");
    ofstream out("order.out");
    srand(unsigned(time(0)));
    nil=new Treap(0,0,0,NULL,NULL);
    T=new Treap(1,rand()+1,1,nil,nil);
    temp=nil;
    in >> n;
    for(int i=2;i<=n;i++) Insert(T,i,rand()+1);
    int p=2;
    for(int i=1;i<=n;i++){
        p+=(i-1); p%=(n-i+1); if(!p) p=n-i+1;
        temp=Find(T,p);
        out << temp->v << ' ';
        Erase(T,temp->v);
    }
}