Cod sursa(job #1180108)

Utilizator costyrazvyTudor Costin Razvan costyrazvy Data 29 aprilie 2014 22:34:28
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <cstdio>
#include <climits>

#define ub(x) (x&(-x))
#define NMAX 30001

using namespace std;

int A[NMAX],sol[NMAX];
int x,N,i,ind,P=2;

void add(int x,int val)
{
    int i=0;

    for(i=x;i<=N;i+=ub(i)) A[i]+=val;
}

int Sum(int x)
{
    int i=0,S=0;

    for(i=x;i>0;i-=ub(i)) S+=A[i];

    return S;
}

int binary_search(int x)
{
    int D=N,S=1,M=0,Sm=0,Minim=INT_MAX;

    while(S<=D)
    {
        M=(S+D)/2;
        Sm=Sum(M);

        if( Sm==x && M<Minim) Minim=M;
             else if (Sm>=x) D=M-1;
                  else S=M+1;
    }

    return Minim;
}

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) add(i,1);
    ind=N;

    for(i=1;i<=N;++i)
    {
        --ind;

        x=binary_search(P);
        add(x,-1);

        sol[i]=x;
        P+=i;

        if (ind!=0) P=mod(P,ind);
    }

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

    return 0;
}