Cod sursa(job #445001)

Utilizator eudanipEugenie Daniel Posdarascu eudanip Data 22 aprilie 2010 13:57:05
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include<stdio.h>

int arb[70000],n;

void update (int n,int l,int r,int poz,int val)
{
    if(l==r)
    {
        arb[n] += val;
        return ;
    }

    int m=(l+r)/2;
    if(poz<=m)
        update(2*n,l,m,poz,val);
    else
        update(2*n+1,m+1,r,poz,val);
    arb[n]=arb[2*n]+arb[2*n+1];
}

int query(int n,int l,int r,int a,int b)
{
    if(a>b)
        return 0;
    if(a<=l && r<=b)
        return arb[n];
        
    int m=(l+r)/2;

    int i1=0, i2=0;
    if(a <= m)
        i1=query(2*n, l, m, a, b);
    if(b > m)
        i2=query(2*n+1, m+1, r, a, b);
    return i1+i2;
}

int find(int n,int l,int r,int poz)
{
    if (l == r)
        return l;

    int m=(l+r)/2;
    if(arb[2*n] < poz)
        return find(2*n+1,m+1,r,poz-arb[2*n]);
    return find(2*n,l,m,poz);
}

int main ()
{
    int i,poz,c;
    freopen("order.in","r",stdin);
    freopen("order.out","w",stdout);
    scanf("%d",&n);

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

    update(1,1,n,2,-1);
    printf("2 ");
    poz = 2;
    
    for(i=2;i<=n;i++)
    {
        c=query(1,1,n,1,poz-1);
        c = (c+i)%arb[1];
        if (c==0) c=arb[1];
        poz=find(1,1,n,c);
        printf("%d ", poz);
        update(1,1,n,poz,-1);
    }
    printf("\n");

    return 0;
}