Cod sursa(job #2239477)

Utilizator SqueekDanielTodasca Daniel SqueekDaniel Data 10 septembrie 2018 21:15:00
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <bits/stdc++.h>

#define MaxN 30005

std::ifstream InFile("schi.in");
std::ofstream OutFile("schi.out");

int N;
int Tree[MaxN]; // Arbore de sume, imagindu-ne ca lucram cu elemente ce compun un vector de frecventa
int Loc[MaxN];  // Ce am citit pentru cel cu nr de ordine i
int Ans[MaxN];

int Sum(int Index) {    // Returneaza cate elemente sunt nealese la momentul apelarii
    int S = 0;
    while (Index) {
        S += Tree[Index];
        Index -= Index&(-Index);
    }   return S;
}

void Add(int Index, int Value) {    // Adauga la arbore pe pozitia Index o valoare si Updateaza restul elementelor
    while (Index<=N) {
        Tree[Index] += Value;
        Index += Index&(-Index);
    }
}

int Query(int Index) {  // Da pozitia pe care s-ar afla cel cu numarul de ordine Index
    int Rez;
    int Left = 1, Right = N, Middle;
    while (Left <= Right) {
        Middle = (Left+Right)/2;
        if(Loc[Index] <= Sum(Middle)) {
            Right = Middle-1;
            Rez = Middle;
        }
        else Left = Middle+1;
    }   return Rez;
}

void Citire() {
    InFile >> N;
    for (int i=0; i<N; i++)
        InFile >> Loc[i+1],
        Add(i+1, 1);
}
void Rezolvare() {
    for (int i=N; i>0; i--) {
        int Index = Query(i);
        Ans[Index] = i;
        Add(Index, -1);
    }

    for (int i=0; i<N; i++)
        OutFile << Ans[i+1] << '\n';
}

int main()
{
    Citire();
    Rezolvare();

    return 0;
}