Cod sursa(job #1259189)

Utilizator ccygnusMaygnus Pop ccygnus Data 9 noiembrie 2014 19:54:58
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include<stdio.h>
int n,aib[30001];
void update(int pos,int val)
{
    for(;pos<=n;pos=pos+(pos&-pos))
        aib[pos]=aib[pos]+val;
}
int query(int pos)
{
    int ans;
    for(ans=0;pos;pos=pos-(pos&-pos))
        ans=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=st+(1<<i);
            val=val-aib[st];
            }
    return st+1;
}
int main()
{
    freopen("order.in","r",stdin);
    freopen("order.out","w",stdout);
    int i,qn,qi,poz,caut;
    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);
    }
return 0;
}