Cod sursa(job #2904361)

Utilizator bianca.andreiAndrei Bianca bianca.andrei Data 17 mai 2022 23:23:35
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <bits/stdc++.h>

using namespace std;


ifstream f("order.in");
ofstream g("order.out");

int arb[400001];

void creare(int nod, int l, int r)
{
    int m = (l + r)>>1;
    if (l == r)
    {
        arb[nod] = 1;
        return;
    }


    creare(2 * nod, l, m);

    creare(2 * nod + 1, m + 1, r);

    arb[nod] = arb[2 * nod] + arb[2 * nod + 1];
}

int f1(int nod, int l, int r, int index)
{
    int m = (l + r)>>1;

    if (l == r)
        return r;

    if (index <= arb[nod*2])
       return f1(2 * nod, l, m, index);
    else
       return f1(2 * nod + 1, m + 1, r, index - arb[2 * nod]);
}

void f2(int nod, int l, int r, int x)
{
    if (l == r)
    {
        arb[nod] = 0;
        return;
    }

    int m = (l + r)>>1;
    if (x <= m)
        f2(2 * nod, l, m, x);
    else
        f2(2 * nod + 1, m + 1, r, x);

    arb[nod] = arb[2 * nod] + arb[2 * nod + 1];
}


int main()
{
    int i, n, x, index;

    index = 2;

    f >> n;

    creare(1, 1, n);

    for ( i = 1; i <= n; i++)
    {
        index += i;
        index -= 1;

        while (index > arb[1])
            index -= arb[1];

        x = f1(1, 1, n, index);

        f2(1, 1, n, x);

        g<<x<<" ";
    }

    return 0;

}