Cod sursa(job #961751)

Utilizator smaraldaSmaranda Dinu smaralda Data 12 iunie 2013 19:58:20
Problema Order Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 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 p=0,k,st=0;
    for(k=0;(1<<k)<dr;k++);
    while(st<dr && val && p>=0)
        {
            for(p=k-1;p>=0 && val;p--)
                if(st+(1<<p)<=dr && aib[st+(1<<p)]<val)
                    {
                        st+=1<<p;
                        val-=aib[st];
                        break;
                    }
        }
    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;
}