Cod sursa(job #1038498)

Utilizator the@EyE@Postavaru Stefan the@EyE@ Data 21 noiembrie 2013 17:02:21
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
#include<stdio.h>
#define MAX 60001

int arb[2*MAX],n;

void changeV(int nod,int st,int dr,int poz,int val)
{
    arb[nod]+=val;
    if(st==dr)return;
    int m=(st+dr)>>1;
    if(poz<=m)changeV(nod*2,st,m,poz,val);
    else changeV(nod*2+1,m+1,dr,poz,val);
}

int querry(int nod,int st,int dr,int a,int b)
{
    if(b<st||a>dr)return 0;
    int ret=0;
    if(st>=a&&dr<=b)return arb[nod];
    int m=(st+dr)>>1;
    if(b>=m)ret+=querry(nod*2,st,m,a,m);else ret+=querry(nod*2,st,m,a,b);
    if(a<=m+1)ret+=querry(nod*2+1,m+1,dr,m+1,b);else ret+=querry(nod*2+1,m+1,dr,a,b);
    return ret;
}

int getPoz(int nod,int st,int dr,int nr)
{
    if(st==dr)return st;
    int m=(st+dr)>>1;
    if(arb[nod*2]<nr)return getPoz(nod*2+1,m+1,dr,nr-arb[nod*2]);
    else return getPoz(nod*2,st,m,nr);
}

int main()
{
    freopen("order.in","r",stdin);
    freopen("order.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;++i)changeV(1,1,n,i,1);

    int poz=1;
    for(int i=1;i<=n;++i)
    {
        int nr=i;
        if(poz==n)poz=0;
        int ram=querry(1,1,n,poz+1,n);
        if(ram<nr){nr-=ram;poz=0;}
        if(nr>arb[1])
        {
            if(nr%arb[1]==0)nr=arb[1];
            else nr%=arb[1];

        }
        nr+=querry(1,1,n,1,poz);
        poz=getPoz(1,1,n,nr);
        changeV(1,1,n,poz,-1);
        printf("%d ",poz);
    }

    return 0;
}