Cod sursa(job #932718)

Utilizator dicu_dariaDaria Dicu dicu_daria Data 29 martie 2013 10:22:53
Problema Order Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <fstream>

using namespace std;

int i, k, x, poz, n, nr, arb[800010];

void Query(int nod, int l, int r)
{
    if(x < l and arb[nod] + k == nr and l == r)
    {
        k += arb[nod];
        poz = l;
        return;
    }
    if(x < l and arb[nod] + k < nr)
    {
        k += arb[nod];
        return;
    }
    int m = (l+r)/2;
    if(x < m) Query(2*nod, l, m);
    if(k < nr) Query(2*nod+1, m+1, r);
}

void Update(int nod, int l, int r)
{
    if(l == r)
    {
        arb[nod] = 0;
        return;
    }
    int m = (l+r)/2;
    if(poz <= m) Update(2*nod, l, m);
    if(poz > m) Update(2*nod+1, m+1, r);
    arb[nod] = arb[2*nod] + arb[2*nod+1];
}

void Build(int nod, int l, int r)
{
    if(l == r)
    {
        arb[nod] = 1;
        return;
    }
    int m = (l+r)/2;
    Build(2*nod, l, m);
    Build(2*nod+1, m+1, r);
    arb[nod] = arb[2*nod] + arb[2*nod+1];
}

int main()
{
    ifstream fi("order.in");
    ofstream fo("order.out");
    fi >> n;
    Build(1, 1, 2*n);
    for(i = 1, x = 1; i <= n; i++)
    {
        if(i == n)
        i = n;
        k = 0;
        nr = i % (n - i + 1);
        if(nr == 0) nr += n - i + 1;
        Query(1, 1, 2*n);
        if(poz <= n) poz += n;
        Update(1, 1, 2*n);
        poz -= n;
        Update(1, 1, 2*n);
        x = poz;
        fo << x << "\n";
    }
    return 0;
}