Cod sursa(job #827897)

Utilizator R.A.RFMI Romila Remus Arthur R.A.R Data 2 decembrie 2012 19:47:45
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <fstream>
#define LS(p) (p<<1)
#define RS(p) ((p<<1)+1)
#define NMAX (1<<16)
using namespace std;

ifstream in("order.in");
ofstream out("order.out");

int V[NMAX],N,P;

void Update(int current_position,int start,int final,int pos,int value)
{
    if(start == final)
        V[current_position] = value;
    else
    {
        int med = (start + final) / 2;
        if(pos<=med)
             Update(LS(current_position),start,med,pos,value);
        else Update(RS(current_position),med+1,final,pos,value);
        V[current_position] = V[LS(current_position)] + V[RS(current_position)];
    }
}

void Query(int current_position,int start,int final,int value)
{
    if(start == final)
        P = start;
    else
    {
        int med = (start + final) / 2;
        if(V[LS(current_position)]>=value)
            Query(LS(current_position),start,med,value);
        else
            Query(RS(current_position),med+1,final,value - V[LS(current_position)]);
    }
}

int main()
{
    int i,next = 1;
    in>>N;
    for(i = 1;i<=N; i++)
        Update(1,1,N,i,1);
    for(i = 1;i<=N; i++,next--,out<<P<<' ')
    {
        next = (next + i+ V[1] )% V[1];
        if(!next) next = V[1];

        Query(1,1,N,next);
        Update(1,1,N,P,0);

    }
    return 0;
}