Cod sursa(job #1035417)

Utilizator george_stelianChichirim George george_stelian Data 18 noiembrie 2013 15:54:49
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <cstdio>
#define putere(a) (a^(a-1))&a

using namespace std;

int v[30010],i,n,k,sol;

void schimba(int x,int val)
{
    int i;
    for(i=x;i<=n;i+=putere(i))
    {
        v[i]+=val;
    }
}

int cauta(int x)
{
    int i,j,sol,sum=0;
    for(i=1;i<=n;i=i<<1);
    for(j=0;i;i=i>>1)
        if(j+i<=n)
        {
            if(v[j+i]+sum==x) sol=j+i;
            else if(v[j+i]+sum<x)
                {
                    j+=i;
                    sum+=v[j];
                }
        }
    return sol;
}

int main()
{
    freopen("order.in", "r", stdin);
    freopen("order.out", "w", stdout);
    scanf("%d",&n);
    for(i=1;i<=n;i++) schimba(i,1);
    k=2;
    for(i=1;i<=n;i++)
    {
        k=(k+i-1)%(n-i+1);
        if(k==0) k=n-i+1;
        sol=cauta(k);
        printf("%d ",sol);
        schimba(sol,-1);
    }
    return 0;
}