Cod sursa(job #1472833)

Utilizator Liviu98Dinca Liviu Liviu98 Data 17 august 2015 20:41:49
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <iostream>
#include <stdio.h>
#define NMax 30005
using namespace std;
int Arb[4*NMax],N;
int NextElim,position,remaining;

void Build(int nod,int st,int dr)
{
    if(st==dr)
    {
        Arb[nod]=1;
        return;
    }
    int mij=(st+dr)/2;
    Build(2*nod,st,mij);
    Build(2*nod+1,mij+1,dr);
    Arb[nod]=Arb[2*nod]+Arb[2*nod+1];
}

void Update(int nod,int st,int dr,int position)
{
    if(st==dr)
    {
        Arb[nod]=0;
        return;
    }
    int mij=(st+dr)/2;
    if(position<=Arb[2*nod])
        Update(2*nod,st,mij,position);
    else
        Update(2*nod+1,mij+1,dr,position-Arb[2*nod]);
    Arb[nod]=Arb[2*nod]+Arb[2*nod+1];
}

int Query(int nod,int st,int dr,int position)
{
    if(st==dr)
    {
        return st;
    }
    int mij=(st+dr)/2;
    if(position<=Arb[2*nod])
        return Query(2*nod,st,mij,position);
    else
        return Query(2*nod+1,mij+1,dr,position-Arb[2*nod]);
}

int main()
{
    freopen("order.in","r",stdin);
    freopen("order.out","w",stdout);
    scanf("%d",&N);
    NextElim=2;
    remaining=N;
    Build(1,1,N);

    for(int i=1;i<=N;i++)
    {
        NextElim=(NextElim+i-1)%remaining;
        if(NextElim==0)
            NextElim=remaining;

        position=Query(1,1,N,NextElim);
        printf("%d ",position);
        Update(1,1,N,NextElim);
        remaining--;
    }

}