Cod sursa(job #1425489)

Utilizator ccygnusMaygnus Pop ccygnus Data 27 aprilie 2015 16:05:39
Problema Order Scor 100
Compilator cpp Status done
Runda pregatire-lot-aib Marime 1 kb
#include<stdio.h>
int n,a[30005];
void update(int pos,int val)
{
    for(;pos<=n;pos=pos+(pos&-pos))
        a[pos]=a[pos]+val;
}
int query(int pos)
{
    int ans;
    for(ans=0;pos;pos=pos-(pos&-pos))
        ans=ans+a[pos];
    return ans;
}
int bsearch(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 && a[st+(1<<i)]<val)
            {
            st=st+(1<<i);
            val=val-a[st];
            }
    return st+1;
}
int main()
{
    freopen("order.in","r",stdin);
    freopen("order.out","w",stdout);
    int i,nq,pozq,poz,c;
    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++)
        {
        nq=query(n);
        pozq=query(poz-1);
        c=i%nq;
        if (!c)
            c=nq;
        if (c>nq-pozq)
            poz=bsearch(poz,c-nq+pozq);
        else
            poz=bsearch(n,pozq+c);
        update(poz,-1);
        printf(" %d",poz);
        }
return 0;
}