Cod sursa(job #2905484)

Utilizator KarinaDKarina Dumitrescu KarinaD Data 22 mai 2022 03:42:56
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream fin ( "schi.in" );
ofstream fout ( "schi.out" );

const int N = 30001;
int v[N], poz[N], aib[N];

int main () {
    
    int n, i, s, x;
    
    fin >> n;
    
    for ( i = 1; i <= n; i++ ) {
        
        fin >> v[i];
    
        x = i;
        
        while ( x <= n ){
            aib[x] = aib[x] + 1;
            x = x + ( x & (-x) );
        }
    }
    
    for ( i = n; i > 0; i-- ) {
        
        int st = 0, dr = n + 1, mij;
        
        while ( dr - st > 1 ) {
            
            mij = ( st + dr ) / 2;
            
            s = 0;
            x = mij;

            while ( x > 0 ){
                s = s + aib[x];
                x = x - ( x & (-x) );
            }
            
            if ( s < v[i] )
                st = mij;
            else
                dr = mij;
            
        }
        
        st++;
        poz[st] = i;
        
        while ( st <= n ){
            aib[st] = aib[st] - 1;
            st = st + ( st & (-st) );
        }
    }
    
    for ( i = 1; i <= n; i++ )
        fout << poz[i] << "\n";
    
    return 0;
}