Cod sursa(job #2239394)

Utilizator alexmisto342Turdean Alexandru alexmisto342 Data 10 septembrie 2018 17:56:44
Problema Order Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.61 kb
#include <bits/stdc++.h>
#define inf 2000000000
using namespace std;
ifstream fin("order.in");
ofstream fout("order.out");
int i,j,n,m;
struct nod{
    int info;
    int pri,nr;
    nod *st, *dr;
    nod(int info, int pri, nod *st, nod *dr)
    {
        this->dr = dr;
        this->st = st;
        this->info = info;
        this->pri = pri;
        nr = 1;
    }
};
nod *T,*Ts,*Td,*nil;

void upd(nod *&n)
{
    n->nr = n->st->nr + n->dr->nr + 1;
}
void rotateleft(nod *&n)
{
    nod *x = n->dr;
    n->dr = x->st;
    x->st = n;
    n = x;
}

void rotateright(nod *&n)
{
    nod *x = n->st;
    n->st = x->dr;
    x->dr = n;
    n = x;
}

void balance(nod *&n)
{
    if(n->pri < max(n->dr->pri, n->st->pri))
    {
        if(n->dr->pri > n->st->pri)
            rotateleft(n);
        else
            rotateright(n);
    }
    upd(n);
}

void insert(nod *&n, int info, int prioritate)
{
    if(n == nil)
    {
        n = new nod(info, prioritate, nil, nil);
        return;
    }
    if(info > n->info)
        insert(n->dr, info, prioritate);
    else
        insert(n->st, info, prioritate);
    balance(n);
}

void del(nod *&n,int info)
{
    if(n == nil)
        return;

    if(info > n->info)
        del(n->dr, info);
    else if(info < n->info)
        del(n->st, info);
    else
    {
        if(n->st == n->dr)
        {
            delete n;
            n = nil;
            return;
        }
        if(n->st->pri > n->dr->pri)
            rotateright(n), del(n->dr, info);
        else
            rotateleft(n), del(n->st, info);
    }
    balance(n);
}

void afiseaza(nod *n)
{
    if(n == nil)
        return;
    afiseaza(n->st);
    fout << n->info << " ";
    afiseaza(n->dr);
}

void split(nod *&T, nod *&Ts, nod *&Td, int info)
{
   insert(T, info, inf + 100);
   Ts = T->st;
   Td = T->dr;
   delete T, T = nil;
}

void join(nod *&T, nod *&Ts, nod *&Td)
{
    T = new nod(0 ,0, Ts, Td);
    del(T, T->info);
}
int find(nod *&n,int k)
{
    if(n->st->nr < k)
    {
        k-=n->st->nr;
        if(k == 1)
            return n->info;
        return find(n->dr, k - 1);
    }
    return find(n->st, k);
}
int main()
{
    srand(time(0));
    T = nil = new nod(0,0,NULL,NULL);
    fin >> n;
    for(i = 1 ; i <= n; i++)
    {
        insert(T,i,rand()%inf + 1);
    }
    int k = 1;
    for(i = 1; i <= n; i++)
    {
        k += i;
        k = k %(n - i + 1);
        if(k == 0)
            k = n-i+1;
        j = find(T,k);
        fout<<j<<" ";
        del(T,j);
        k--;
    }
    return 0;
}