Cod sursa(job #983697)

Utilizator mitrutstrutMitrea Andrei Ionut mitrutstrut Data 12 august 2013 16:02:12
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 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;
}