Cod sursa(job #1602322)

Utilizator T.C.11Tolan Cristian T.C.11 Data 16 februarie 2016 18:40:37
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <fstream>

using namespace std;

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

int nrC,nrR,i,n,f[200000],v[200000],nod,aux;

void update(int pos,int val, int st, int fn, int nod)
{
    if (st!=fn)
    {
        int mij = (st+fn)/2;
        if (pos <= mij)
            update (pos, val, st, mij, nod*2);
        else
            update (pos, val, mij+1, fn, nod*2+1);
    }
    else
        f[nod]=pos;
    v[nod]+=val;
}

int findNodToUpdate(int nr, int nod)
{
    if (nr == v[nod] && f[nod])
    {
        return nod;
    }
    else
    {
        if (nr <= v[nod*2])
            return findNodToUpdate(nr, nod*2);
        else
            return findNodToUpdate(nr-v[nod*2], nod*2+1);
    }
}

int main()
{
    fin>>n;
    for (i=1;i<=n;i++)
        update(i, 1, 1, n, 1);
    nrC = 1;
    i = 1;
    nrR = n;
    while (nrR > 0)
    {
        aux = (nrC+i)%nrR;
        if (aux == 0)
            aux = nrR;
        nod = findNodToUpdate(aux, 1);
        fout<<f[nod]<<" ";
        update(f[nod], -1, 1, n, 1);
        nrR--;
        i++;
        nrC = aux-1;
    }
    return 0;
}