Cod sursa(job #854373)

Utilizator R.A.RFMI Romila Remus Arthur R.A.R Data 13 ianuarie 2013 15:02:33
Problema Schi Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.69 kb
#include <fstream>
#define LS (current_position<<1)
#define RS (current_position<<1)+1
#define  INF 30004
#define NMAX 31000
using namespace std;

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

short int N,begin,end,value;

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

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

        if(V[LS][1]+V[LS][2]<V[RS][1]+V[RS][2])
             V[current_position][0] = V[LS][0],V[current_position][1] = V[LS][1]+V[LS][2];
        else V[current_position][0] = V[RS][0],V[current_position][1] = V[RS][1]+V[RS][2];
    }
}

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

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