Cod sursa(job #829176)

Utilizator R.A.RFMI Romila Remus Arthur R.A.R Data 4 decembrie 2012 21:57:22
Problema Schi Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.67 kb
#include <fstream>
#define LS (current_position<<1)
#define RS (current_position<<1)+1
#define  INF (1<<20)
#define NMAX 65000
using namespace std;

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

struct my_struct{int pozitie,add,nr;}V[NMAX];

int N,begin,end,value;

void Update(int current_position,int start,int final)
{
    if(start>=begin && final <=end)
        V[current_position].add +=value;
    else
    {
        int med = (start + final) / 2;
        if(begin<=med)
            Update(LS,start,med);
        if(med+1<=end)
            Update(RS,med+1,final);

        if(V[LS].pozitie+V[LS].add<V[RS].pozitie+V[RS].add)
             V[current_position].nr = V[LS].nr,V[current_position].pozitie = V[LS].pozitie+V[LS].add;
        else V[current_position].nr = V[RS].nr,V[current_position].pozitie = V[RS].pozitie+V[RS].add;
    }
}

void Refresh(int current_position,int start,int final)
{
    if(start<final)
    {
        int med = (start + final) / 2;
        Refresh(LS,start,med);
        Refresh(RS,med+1,final);
        if(V[LS].pozitie+V[LS].add<V[RS].pozitie+V[RS].add)
             V[current_position].nr = V[LS].nr,V[current_position].pozitie = V[LS].pozitie+V[LS].add;
        else V[current_position].nr = V[RS].nr,V[current_position].pozitie = V[RS].pozitie+V[RS].add;
    }
}

int main()
{
    int i,x;
    in>>N;
    for(i=1;i<=N;i++)
        in>>x,V[N+i-1].nr = i,V[N+i-1].pozitie = x;
    Refresh(1,1,N);
    for(i=1;i<=N;i++)
    {
        out<<(x = V[1].nr)<<'\n';
        begin = x,end = x,value = INF;
        Update(1,1,N);
        begin = 1,end = x,value = 1;
        Update(1,1,N);
    }
    return 0;
}