Cod sursa(job #2509319)

Utilizator Vlad_NituNitu Vlad-Petru Vlad_Nitu Data 14 decembrie 2019 09:47:02
Problema Schi Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.77 kb
/*Pentru a rezolva problema vom reține, într-un arbore indexat binar numărul de poziții libere în clasamentul final.
Astfel, elementul AIB[x] va reține câte poziții libere există între [x-2k+1,..,x]. Se va parcurge invers șirul din
fișierul de intrare, și pentru fiecare valoare X[i], se va determina cea mai mica poziție x pentru care suma
elementelor din AIB pe intervalul [1..x] este egală cu X[i].
Poziția x este poziția din clasamentul final a concurentului cu mumărul de ordine i.
*/


#include <bits/stdc++.h>
#define NMAX 30005
#define op(i) (i & (-i) )
 using namespace std;
int N , x , y ;
int v[NMAX] , aib[NMAX] , sol[NMAX];
void Update (int poz ,int val)
{
    int i ;
     for (int i = poz ; i <= N  ; i += op(i))
        aib[i] += val;
     return ;
}
int suma (int poz)
{
    int i ;
    int sum = 0 ;
    for (int i = poz ; i >= 1 ; i -= op(i))
        sum += aib[i] ;

    return sum ;
}
int BinarySearch (int st , int dr , int val)
{
    int Min = N + 1;
    while (st <= dr)
    {
        int mij = (st + (dr - st) / 2) ;
        int Sum = suma(mij);
        if (val == Sum && mij < Min) Min = mij;
        else if (val <= Sum) dr = mij - 1 ;
        else st = mij  + 1 ;
    }

    return Min ;
}
int main()
{
    freopen("schi.in" , "r" , stdin) ;
    freopen("schi.out" , "w" , stdout) ;
    scanf ("%d" , &N) ;
    for (int i = 1 ; i <= N ; ++i)
    {
        scanf("%d" , &v[i]) ;
        aib[i]  = op(i); //
    }

        for (int i = N ; i >= 1 ; --i)
        {
            int conc = BinarySearch(1,N,v[i]) ;
            Update(conc,-1) ;

            sol[conc] = i ; // Concurentul 'conc' se afla pe poz 'i'
        }
    for (int i = 1 ; i  <= N ; ++i) printf("%d ", sol[i]) ;
    return 0 ;
}