Cod sursa(job #1425667)

Utilizator vladdy47Bucur Vlad Andrei vladdy47 Data 27 aprilie 2015 21:14:24
Problema Order Scor 100
Compilator cpp Status done
Runda pregatire-lot-aib Marime 1.13 kb
#include <cstdio>
#define ub(x) (x&(-x))

using namespace std;

int aib[30005],sol[30005];

int x,N,i,ind,P=2,n,ctr;

void update(int x,int nr)
{
    int i;
    for(i = x; i <= n; i+=ub(i)) aib[i] += nr;
}
int suma(int x)
{
    int s = 0;
    for(i = x; i > 0; i -= ub(i)) s += aib[i];
    return s;
}
int cautbin(int x)
{
    int dr = n ,st = 1, mij = 0, sum = 0, Min = 999999999;
    while(st <= dr)
    {
        mij = (st + dr) / 2;

        if( suma(mij) == x && mij < Min) Min = mij;
        else {if (suma(mij) < x) st = mij + 1;
        else dr = mij - 1; }
    }
    return Min;
}
int mod(int x,int MOD)
{
    if (!(x%MOD)) return MOD;
    return x%MOD;
}
int main()
{
    freopen("order.in","r",stdin);
    freopen("order.out","w",stdout);
    scanf("%d",&n);
    for(i = 1; i <= n; i++) update(i,1);
    ind = n;
    ctr = 2;
    for(int i = 1; i <= n; i++)
    {
         ind--;
        x=cautbin(ctr);
        update(x,-1);
        sol[i] = x;
        ctr = ctr + i;
        if (ind!=0) ctr = mod(ctr,ind);

    }

    for(i = 1; i <= n; i++) printf("%d ",sol[i]);

    return 0;
}