Cod sursa(job #981720)

Utilizator andrettiAndretti Naiden andretti Data 7 august 2013 19:28:56
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include<stdio.h>
#define maxn 30005
using namespace std;

int n,nr;
int aib[maxn];

void update(int k,int val)
{
    int i=0;
    while(k<=n)
    {
        aib[k]+=val;
        while( ((k>>i)&1)==0 ) i++;
        k+=(1<<i);
        i++;
    }
}

int query(int val)
{
    int sol;
    int i,step=1<<16,sum=0;
    for(i=0;step;step>>=1)
     if(i+step<=n )
     {
         if(aib[i+step]+sum==val) sol=i+step;
         else
          if(aib[i+step]+sum<val) i+=step,sum+=aib[i];
     }

    return sol;
}

void solve()
{
    int pos=1,sol; nr=n;
    for(int i=1;i<=n;i++) update(i,1);
    for(int i=1;i<=n;i++)
    {
        pos=(pos+i)%nr;
        if(pos==0) pos=nr;
        sol=query(pos);
        printf("%d ",sol);
        pos--;
        update(sol,-1); nr--;
    }
}

int main()
{
    freopen("order.in","r",stdin);
    freopen("order.out","w",stdout);

    scanf("%d",&n);
    solve();

    fclose(stdin);
    fclose(stdout);
    return 0;
}