Cod sursa(job #3268106)

Utilizator marap2011Paun Mara marap2011 Data 13 ianuarie 2025 17:30:14
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("schi.in") ;
ofstream fout ("schi.out") ;
int n , i , x ;
vector < int > a , v , f ;
void add ( int ind , int x )
{
    for ( int i = ind ; i <= n ; i += ( i & ( - i ) ) )
        a[i] += x ;
}
int sum ( int ind )
{
    int s = 0 ;
    for ( int i = ind ; i >= 1 ; i -= ( i & ( - i ) ) )
        s += a[i] ;
    return s ;
}
int cb ( int x )
{
    int st = 1 , dr = n , poz = -1 , mij , nr ;
    while ( st <= dr )
    {
        mij = ( st + dr ) / 2 ;
        nr = sum ( mij ) ;
        if ( x > nr )
            st = mij + 1 ;
        else if ( nr > x )
            dr = mij - 1 ;
        else
        {
            poz = mij ;
            dr = mij - 1 ;
        }
    }
    return poz ;
}
int main()
{
    fin >> n ;
    v.resize ( n + 1 ) ;
    a.resize ( n + 1 ) ;
    f.resize ( n + 1 ) ;
    for ( i = 1 ; i <= n ; i ++ )
    {
        fin >> v[i] ;
        add ( i , 1 ) ;
    }
    for ( i = n ; i >= 1 ; i -- )
    {
        x = cb ( v[i] ) ;
        f[x] = i ;
        cout << x ;
        add ( x , -1 ) ;
    }
    for ( i = 1 ; i <= n ; i ++ )
        fout << f[i] << '\n' ;


    return 0;
}