Cod sursa(job #961714)

Utilizator smaraldaSmaranda Dinu smaralda Data 12 iunie 2013 19:15:05
Problema Order Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 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 st, int dr, int val)
{
    int med,qmed,last;
    while(st<=dr)
        {
            med=(st+dr)/2;
            qmed=query(med);
            if(qmed==val)
                last=med,
                dr=med-1;
            if(qmed<val)
                st=med+1;
            if(qmed>val)
                dr=med-1;
        }
    return last;
}

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=1;
            if(caut<=qn-qi)
                poz=bs(poz,n,qi+caut);
            else
                poz=bs(1,poz,caut-qn+qi);
            update(poz,-1);
            printf(" %d",poz);
        }
    printf("\n");
    return 0;
}