Cod sursa(job #1099260)

Utilizator mirceadinoMircea Popoveniuc mirceadino Data 5 februarie 2014 18:26:01
Problema Order Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include<cstdio>

using namespace std;

const int NMAX = 30000+5;
const int LMAX = 32768+5;

int N,K,L,R;
int AInt[2*LMAX];

void Build(int lo,int hi,int node)
{
    if(lo==hi)
    {
        AInt[node] = 1;
        return;
    }

    int mi = (lo + hi)/2;

    Build(lo,mi,2*node);
    Build(mi+1,hi,2*node+1);

    AInt[node] = AInt[2*node] + AInt[2*node+1];
}

int Query(int lo,int hi,int node,int x)
{
    if(lo==hi)
        return lo;

    int mi = (lo+hi)/2;

    if(x<=AInt[2*node]) return Query(lo,mi,2*node,x);
    return Query(mi+1,hi,2*node+1,x-AInt[2*node]);
}

void Update(int poz)
{
    AInt[K+poz] = 0;
    for(poz=(K+poz)/2; poz; poz/=2)
        AInt[poz] = AInt[2*poz] + AInt[2*poz+1];
}

int main()
{
    int i,k,m,x;

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

    scanf("%d",&N);

    for(K=1; K<N; K<<=1);
    K--;

    Build(1,K+1,1);

    for(i=1,k=2; i<=N; i++)
    {
        m = AInt[1];
        k = k + i-1;
        if(k>m) k-=m;
        x = Query(1,K+1,1,k);
        Update(x);
        printf("%d ",x);
    }
    return 0;
}