Cod sursa(job #1551760)

Utilizator ipus1Stefan Enescu ipus1 Data 16 decembrie 2015 16:30:40
Problema Order Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include<cstdio>
int v[30001],n;
int lsb(int x)
    {return (x&(-x));
    }
void update(int x, int k)
    {int i;
    for(i=x;i<=n;i+=lsb(i))
        v[i]+=k;
    }
int query(int x)
    {int i,k;
    k=0;
    for(i=x;i>=1;i-=lsb(i))
        k+=v[i];
    return k;
    }
int loc(int x)
    {int st,dr,l,min,p;
    st=1;
    dr=n;
    min=30001;
    while(st<=dr)
        {l=(st+dr)/2;
        p=query(l);
        if(p==x)
            if(l<min)
                min=l;
        if(p>=x)
            dr=l-1;
        else
            st=l+1;
        }
    return min;
    }
int main ()
{freopen ("order.in","r",stdin);
freopen ("order.out","w",stdout);
int i,x,poz,k;
scanf("%d",&n);
for(i=1;i<=n;i++)
    update(i,1);
poz=1;
k=n;
for(i=1;i<=n;i++)
    {poz+=i;
    poz=poz%k;
    if(poz==0)
        poz=k;
    x=loc(poz);
    update(x,-1);
    printf("%d ",x);
    k--;
    }
return 0;
}