Cod sursa(job #3288387)

Utilizator octavurlurleteanu alexandru octavian octavurl Data 21 martie 2025 20:53:26
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.64 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <climits>
using namespace std;
ifstream fin ( "schi.in" ) ;
ofstream fout ( "schi.out" ) ; 
class Arbore_indexat_binar
{
private:

    vector<int>aib;
    int n;
    int ub( int x )
    {return x & (-x);}
public:
    Arbore_indexat_binar(int o)
    {
        aib.resize(o+1,0);
        n = o ;
    }
    void update(int x,int val)
    {
        for ( int i = x ; i <= n ; i += ub(i) )
            aib[i] += val;
    }
    int query(int x)
    {
        int suma =0 ;
        for ( int i = x ; i >= 1 ; i -= ub(i) )
            suma += aib[i];
        return suma;
    }
    int cautare(int a )
    {
        aib[0]=0;
        int st = 1 , dr = n ;
        int rez = -1 ;
        while(st<=dr)
        {
            int mij = ( st + dr ) / 2;
            int suma = query(mij);
            if ( suma < a )
                st = mij + 1 ;
            else if ( suma > a )
                dr = mij - 1 ;
            else if ( suma == a )
            {
                rez = mij;
                dr = mij - 1 ;
            }
        }
        return rez;
    }
};
int main()
{
    int n ;
    fin >> n ;
    vector<int>v(n);
    Arbore_indexat_binar aib(n);
    for ( int i = 0 ; i < n ; ++ i )
    {
        fin >> v [ i ] ;
        aib.update(i+1,1);
    }

    vector<int>res(n);
    for ( int i = n - 1 ; i >= 0 ; --i )
    {
        int pos =  aib.cautare(v[i]);
        aib.update(pos,-1);
        res[pos-1]=i+1;
    }
    for ( auto it: res )
        fout << it << '\n' ;
    return 0;

}