Cod sursa(job #1425134)

Utilizator tac1234Tran Bach Nguyen tac1234 Data 26 aprilie 2015 19:08:03
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <cstdio>
using namespace std;
int aib[60005],n,m;
inline void adauga(int val,int l)
{
    for ( ; l<=(n<<1); l+=l^(l-1)&l)
        aib[l]+=val;
}
inline int query(int l)
{
    int s=0;
    for ( ; l>=1; l-=l^(l-1)&l)
        s+=aib[l];
    return s;
}
inline int find(int val)
{
    int i,p=m;
    for (i=0; p; p>>=1)
        if (i+p<=(n<<1))
            if (aib[i+p]<val)
            {
                i+=p;
                val-=aib[i];
            }
    return i;
}
int main()
{
    freopen("order.in","r",stdin);
    freopen("order.out","w",stdout);
    int pas,val,y;
    scanf("%d",&n);
    for (register int i=1; i<=(n<<1); ++i)
        adauga(1,i);
    for (m=1; m<(n<<1); m<<=1);
    for (pas=1,y=1; pas<=n; ++pas)
    {
        if ((query(y)+pas)%query(n)==0)
            val=query(n);
        else
            val=(query(y)+pas)%query(n);
        y=find(val)+1;
        if (y>n)
            y%=n;
        adauga(-1,y);
        adauga(-1,y+n);
        printf("%d ",y);
    }
    printf("\n");
    return 0;
}