Cod sursa(job #1522241)

Utilizator vladdy47Bucur Vlad Andrei vladdy47 Data 11 noiembrie 2015 14:09:58
Problema Order Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
# include <bits/stdc++.h>
# define ub(x) (x&(-x))

using namespace std;

const int Nmax = 30000 + 5;

int n, nrc, i, poz;
int aib[Nmax], sol[Nmax];


void add(int poz, int val)
{
    for (int i = poz; i <= n; i += ub(i)) aib[i] += val;
}

int sum (int poz)
{
    int s = 0;

    for (int i = poz; i >= 1; i -= ub(i)) s += aib[i];

    return s;
}

int cautbin (int x)
{
    int st = 1, dr = n, mij;

    while (st <= dr)
    {
        mij = (st + dr) / 2;
        if (sum(mij) == x) return mij;
        if (sum(mij) < x) st = mij + 1;
        else dr = mij - 1;
    }
    return INT_MAX;
}

void write()
{
    for (int i = 1; i <= n; ++i)
        printf("%d ",sol[i]);
}

int main ()
{
    freopen("order.in","r",stdin);
    freopen("order.out","w",stdout);

    scanf("%d\n", &n);

    for (i = 1; i <= n; ++i) add(i, 1);

    nrc = 2;
    ind = n;

    for (i = 1; i <= n; ++i)
    {   ind --;
        poz = cautbin(nrc);
        sol[i] = poz;

        add(poz, -1);

        nrc += i;

        if (ind) {
            if ( nrc % ind == 0) nrc = ind;
                else nrc = nrc % ind;
        }

    }

    write();

    return 0;
}