Cod sursa(job #1099559)

Utilizator Al3ks1002Alex Cociorva Al3ks1002 Data 5 februarie 2014 22:25:12
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include<cstdio>
using namespace std;
const int NMAX = 30005;
int N,i,poz,len,aib[NMAX],lim,sol,a[NMAX];
void Update(int poz,int val)
{
    for(int i=poz;i<=N;i+=i&(-i)) aib[i]+=val;
}
int Query(int x)
{
    int step,sol=0;
    for(step=lim;step;step>>=1)
        if(sol+step<=N)
            if(aib[sol+step]<=x)
            {
                sol+=step; x-=aib[sol];
                if(!x) break;
            }
    while(!a[sol]) sol--;
    return sol;
}
int main()
{
    freopen("order.in","r",stdin);
    freopen("order.out","w",stdout);
    scanf("%d",&N);
    for(i=1;i<=N;i++) Update(i,1),a[i]=1;
    for(lim=1;lim<=N;lim<<=1);
    for(i=1,poz=2;i<=N;i++)
    {
        len=N-i+1;
        poz=(poz+i-1)%len;
        if(!poz) poz=len;
        sol=Query(poz);
        printf("%d ",sol);
        Update(sol,-1);
        a[sol]=0;
    }
    return 0;
}