Cod sursa(job #2329880)

Utilizator BogdanAlexandruBogdan-Alexandru Dig BogdanAlexandru Data 27 ianuarie 2019 17:02:13
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.59 kb
#include <stdio.h>

using namespace std;
FILE *f,*g;
int arbint[4*30001],N,P,v[30002],S[30002],Value,NOD;
void CreateFirstTree(int Nod,int Left,int Right)///formez arborele de intervale în care fiecare Nod va reține numărul de poziții libere din fiecare interval
{
    int Middle=(Right+Left)/2;
    if(Right==Left)
    {
        arbint[Nod]=1;return;
    }
    if(P<=Middle)CreateFirstTree(Nod*2,Left,Middle);
    else
        CreateFirstTree(Nod*2+1,Middle+1,Right);
    arbint[Nod]=arbint[2*Nod]+arbint[2*Nod+1];

}
int M;
void Read()
{
    int i;
    M=N;
    for(i=1;i<=N;i++)
        fscanf(f,"%d",&v[i]),P=i,CreateFirstTree(1,1,N);
}
void DeletePozX(int Nod,int Left,int Right,int PP)
{
    int Middle=(Left+Right)/2;
    if(Left==Right)
    {
        S[Left]=NOD;arbint[Nod]=0;///Am gasit pozitia corespunzatoare intervalului
        return;
    }
    if(PP<=arbint[2*Nod])///daca mai am pozitii ramase in Fiul Stang
        DeletePozX(2*Nod,Left,Middle,PP);///Ma deplasez in el
    else///Altfel, o iau în drepta actualizând numărul de poziții
        DeletePozX(2*Nod+1,Middle+1,Right,PP-arbint[2*Nod]);
    arbint[Nod]=arbint[2*Nod]+arbint[2*Nod+1];///calculze numarul de pozitii libere din fiecare nod
}
void Displaying()
{
    int i=1;
    while(M)
    {
        fprintf(g,"%d\n",S[i]);M--;i++;
    }
}
int main()
{
    f=fopen("schi.in","r");g=fopen("schi.out","w");
    fscanf(f,"%d",&N);
    Read();
    while(N)
    {
        NOD=N;
        DeletePozX(1,1,M,v[N]);
        N--;
    }
    Displaying();
    fclose(f);fclose(g);
    return 0;
}