Cod sursa(job #674656)

Utilizator MKLOLDragos Ristache MKLOL Data 6 februarie 2012 16:36:35
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include<stdio.h>

int aib[101010],N,M;
int tip,x,y;

int zero(int x)
{
    return (x^(x-1))&x;
}
int add(int poz,int x)
{
    for(int i=poz;i<=N;i+=zero(i))
        aib[i]+=x;
}
int querry(int poz)
{
    int S=0;
    for(int i=poz;i>=1;i-=zero(i))
        S+=aib[i];
        return S;

}
int search(int val)
{
    int st=1,dr=N,mij,rez=0;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        x=querry(mij);
        if(x==val)
        {
            rez=mij;
            dr=mij-1;
        }
        else if(x>val)
        {
            dr=mij-1;
        }
        else st=mij+1;
    }
    return rez;
}


int main()
{
freopen("order.in","r",stdin);
freopen("order.out","w",stdout);
 scanf("%d",&N);
// printf("!");
        for(int i=1;i<=N;++i)
        {
           // scanf("%d",&x);
            add(i,1);
        }
        int q,nr=N,aux=1;
        for(int i=1;i<=N;++i)
        {
        aux+=i;
        aux%=nr;
        if(aux==0)
            aux=nr;
            q=search(aux);
        printf("%d ",q);
        add(q,-1);
        --nr;
        --aux;
        if(aux==0)
            aux=nr;

        }
}