Cod sursa(job #2507316)

Utilizator vladvlad00Vlad Teodorescu vladvlad00 Data 9 decembrie 2019 23:19:16
Problema Order Scor 95
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.2 kb
#include <fstream>
#include <random>

using namespace std;

ifstream fin("order.in");
ofstream fout("order.out");

typedef struct treap* arb;

mt19937 rnd((long long)(new char));

arb gol;

struct treap
{
    int val;
    int size;
    long long prio;
    treap *st, *dr;

    void updSize()
    {
        size = 1 + st->size + dr->size;
    }

    pair<arb,arb> split(int poz)
    {
        if (this == gol)
            return {gol,gol};
        if (st->size < poz)
        {
            auto rez = dr->split(poz-st->size-1);
            dr = rez.first;
            updSize();
            return {this, rez.second};
        }
        else
        {
            auto rez = st->split(poz);
            st = rez.second;
            updSize();
            return {rez.first,this};
        }
    }

    arb ins(int poz, int v);
    arb del(int poz);
    int access(int poz);

    treap(int v=0): val(v), size(1), prio(rnd()), st(gol), dr(gol) { }
};

arb join(arb x, arb y)
{
    if (x == gol)
        return y;
    if (y == gol)
        return x;
    if (x->prio < y->prio)
    {
        arb rez = join(x,y->st);
        y->st = rez;
        y->updSize();
        return y;
    }
    else
    {
        arb rez = join(x->dr,y);
        x->dr = rez;
        x->updSize();
        return x;
    }
}

int n;

int main()
{
    gol = new treap();
    gol->prio = 0;
    gol->size = 0;
    gol->st = gol->dr = gol;

    arb t = gol;
    fin >> n;
    for (int i=1;i<=n;i++)
        t = t->ins(i,i);
    int poz=1;
    int runde = n;
    int elim=0;
    for (int i=1;i<=runde;i++)
    {
        poz += i;
        poz %= n;
        if (poz == 0)
            poz = n;
        fout << t->access(poz) << ' ';
        t = t->del(poz);
        poz--;
        n--;
    }
    return 0;
}

arb treap::ins(int poz, int v)
{
    auto rez = split(poz-1);
    arb nod = new treap(v);
    rez.first = join(rez.first,nod);
    return join(rez.first,rez.second);
}

arb treap::del(int poz)
{
    auto rez = split(poz);
    auto aux = rez.first->split(poz-1);
    return join(aux.first,rez.second);
}

int treap::access(int poz)
{
    if (poz == st->size+1)
        return val;
    if (poz <= st->size)
        return st->access(poz);
    return dr->access(poz-st->size-1);
}