Cod sursa(job #1425385)

Utilizator tac1234Tran Bach Nguyen tac1234 Data 27 aprilie 2015 13:20:12
Problema Order Scor 100
Compilator cpp Status done
Runda pregatire-lot-aib Marime 1.01 kb
#include <cstdio>
using namespace std;
const int NMAX=30000;
int aib[(NMAX<<1)+5],n;
inline void update(int val,int l)
{
    for ( ; l<=(n<<1); l+=l&-l)
        aib[l]+=val;
}
inline int query(int l)
{
    int s=0;
    for ( ; l>=1; l-=l&-l)
        s+=aib[l];
    return s;
}
inline int find(int val,int m)
{
    int i;
    for (i=0; m; m>>=1)
        if (i+m<=(n<<1))
            if (aib[i+m]<val)
            {
                i+=m;
                val-=aib[i];
            }
    return i;
}
int main()
{
    freopen("order.in","r",stdin);
    freopen("order.out","w",stdout);
    int j,val,y,m;
    scanf("%d",&n);
    for(register int i=1; i<=(n<<1); ++i)
        update(1,i);
    for(m=1; m<(n<<1); m<<=1);
    for(j=1,y=1; j<=n; ++j)
    {
        if ((query(y)+j)%query(n)==0)
            val=query(n);
        else
            val=(query(y)+j)%query(n);
        y=find(val,m)+1;
        if (y>n)
            y%=n;
        printf("%d ",y);
        update(-1,y);
        update(-1,y+n);
    }
    printf("\n");
    return 0;
}