Cod sursa(job #2239463)

Utilizator alexmisto342Turdean Alexandru alexmisto342 Data 10 septembrie 2018 20:49:30
Problema Order Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.16 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 nr,height;
    nod *st, *dr;
    nod(int info, nod *st, nod *dr)
    {
        this->dr = dr;
        this->st = st;
        this->info = info;
        nr = 0;
        height = -1;
    }
};
nod *T,*Ts,*Td,*nil;

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

void rotateright(nod *&n)
{
    nod *x = n->st;
    n->st = x->dr;
    upd(n);
    x->dr = n;
    n = x;
    upd(n);
}
int heavy(nod *&n)
{
    return n->st->height - n->dr->height;
}
void balance(nod *&n)
{
    upd(n);
    if(heavy(n) > 1)
    {
        if(heavy(n->st) < 0)
            rotateleft(n->st);
        rotateright(n);
    }
    else if(heavy(n) < -1)
    {
        if(heavy(n->dr) > 0)
            rotateright(n->dr);
        rotateleft(n);
    }
}

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

int find_min(nod *&n)
{
    int a;
    if(n->st == nil)
    {
        if(n->dr == nil)
        {
            a = n->info;
            delete n;
            n = nil;
        }
        else
        {
            nod *x = n;
            a = n->info;
            n = n->dr;
            delete x;
        }
    }
    else
    {
        a = find_min(n->st);
    }
    balance(n);
    return a;
}

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 != nil && n->dr != nil)
        {
            int a = find_min(n->st);
            n->info = a;
        }
        else if(n->st != nil)
        {
            nod *x = n;
            n = n->st;
            delete x;
        }
        else if(n->dr != nil)
        {
            nod *x = n;
            n = n->dr;
            delete x;
        }
        else
        {
            delete n, n = nil;
            return;
        }

    }
    balance(n);

}

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

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()
{
    T = nil = new nod(0,NULL,NULL);
    fin >> n;
    for(i = 1 ; i <= n; i++)
    {
        insert(T,i);
    }
    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;
}