Cod sursa(job #1146674)

Utilizator j.loves_rockJessica Joanne Patrascu j.loves_rock Data 19 martie 2014 10:45:53
Problema Order Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <cstdio>
#define bit(x) (x&(-x))

using namespace std;
int n,i,a[30010],t,sum[30010],x,z,m;
void update(int x)
{
    int i;
    for(i=x; i<=n; i+=bit(i))
        a[i]+=1;
}
void update2(int x)
{
    int i;
    for(i=x; i<=n; i+=bit(i))
        a[i]-=1;
}
int query(int x)
{
    int i,s;
    s=0;
    for (i=n; i>=1; i-=bit(i))
        s+=a[i];
    return s;
}
int cb(int x)
{
    int st,dr,m,s,Min=999999;
    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);
    for (i=1; i<=n; ++i)
        update(i);
    z=2;
    t=n-1;
    for (i=1; i<=n; ++i)
    {
        x=cb(z);
        update2(x);
        sum[++m]=x;
        z+=i;
        if (z>t && i!=n) z%=t;
        if (!z && i!=n) z=t;
        t--;
    }
    for (i=1; i<=n; ++i)
        printf("%d ",sum[i]);
    return 0;
}