Cod sursa(job #961763)

Utilizator smaraldaSmaranda Dinu smaralda Data 12 iunie 2013 20:13:45
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include<stdio.h>
#define NMAX 30000
int n,aib[NMAX+10];
void update (int pos, int val)
{
    for(;pos<=n;pos=pos+(pos&-pos))
        aib[pos]+=val;
}

int query (int pos)
{
    int ans;
    for(ans=0; pos; pos=pos-(pos&-pos))
        ans+=aib[pos];
    return ans;
}

int bs (int dr, int val)
{
    int i,st=0,p;
    for(p=0;(1<<p)<=dr;p++);
    for(i=p-1;i>=0;i--)
        if(st+(1<<i)<dr && aib[st+(1<<i)]<val)
            {
                st+=1<<i;
                val-=aib[st];
            }
    return st+1;
}

int main()
{
    freopen("order.in","r",stdin);
    freopen("order.out","w",stdout);
    int i,qn,qi,poz,caut,ramas;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        update(i,1);
    printf("2");
    update(2,-1);
    poz=2;
    for(i=2;i<=n;i++)
        {
            qn=query(n);
            qi=query(poz-1);
            caut=i%qn;
            if(!caut) caut=qn;
            if(caut<=qn-qi)
                poz=bs(n,qi+caut);
            else
                poz=bs(poz,caut-qn+qi);
            update(poz,-1);
            printf(" %d",poz);
        }
    printf("\n");
    return 0;
}