Cod sursa(job #1146516)

Utilizator OnimushaLordTiberiu Copaciu OnimushaLord Data 19 martie 2014 08:15:36
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
# include <cstdio>
# define N 30010
# define INF (1<<30)
# define zero(x) (x&(-x))

using namespace std;

int a[N],s[N];
int x,i,n,poz,aux;

void update(int x, int y)
{
    int i;
    for(i=x; i<=n; i+=zero(i))
        a[i]+=y;
}
int query(int x)
{
    int i,s=0;
    for(i=x; i>=1; i-=zero(i))
        s+=a[i];
    return s;
}
int bs(int x)
{
    int st,dr,m,s,Min=INF;
    st=1; dr=n;
    while(st<=dr)
    {
        m=(st+dr)/2;
        s=query(m);
        if(s==x && m<Min) Min=m;
        else if(s==x) dr=m-1;
        else if(s>x) dr=m-1;
        else st=m+1;
    }
    return Min;
}
int main()
{
    freopen("order.in", "r", stdin);
    freopen("order.out", "w", stdout);
    scanf("%d\n", &n);
    for(i=1; i<=n; ++i)
        update(i,1);
    poz=2;
    aux=n-1;
    for(i=1; i<=n; i++)
    {
        x=bs(poz);
        update(x,-1);
        s[++s[0]]=x;
        poz+=i;
        if(poz>aux && i!=n) poz%=aux;
        if(!poz && i!=n) poz=aux;
        aux--;
    }
    for(i=1; i<=n; ++i)
        printf("%d ", s[i]);
}