Cod sursa(job #3311819)

Utilizator CosminaneBoac Mihai Cosmin Cosminane Data 24 septembrie 2025 14:19:42
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.45 kb
/**
Luam numerele in ordine inversa.

Pe masura ce determinam pozitiile corecte ale fiecarui
element, le setam cu 1 intr-un vector.

Pozitia corecta a unui element a carui valoare din input
este x va fii al x-ulea 0 din vector.
*/

#include <fstream>
#include <iostream>
using namespace std;
int v[30005], nr[30005], r[30005], n;
void modif( int poz ){ /// Punem 1 pe pozitia poz
    for( ; poz <= n; poz += ( poz & -poz ) ){
        v[poz]++;
    }
}
int sum( int poz ){ /// Suma de la 1 la poz
    int sum;
    sum = 0;
    for( ; poz > 0; poz -= ( poz & -poz ) ){
        sum += v[poz];
    }
    return sum;
}
int main(){
    int i, st, dr, mij;
    ifstream fin("schi.in");
    ofstream fout("schi.out");
    fin >> n;
    for( i = 0; i < n; i++ ){
        fin >> nr[i];
    }
    for( i = n - 1; i >= 0; i-- ){
        st = 0;
        dr = n;
        while( dr - st > 1 ){ /// Cautam binar al nr[i]-lea 0.
            mij = ( st + dr ) / 2;
            if( mij - sum( mij ) < nr[i] ){ /// Pentru un candidat mij,
                                            /// vedem cate 0-uri sunt
                                            /// de la 1 la mij.
                st = mij;
            }
            else{
                dr = mij;
            }
        }
        r[dr] = i + 1;
        modif( dr ); /// Setam 1 la pozitia gasita.
    }
    for( i = 1; i <= n; i++ ){
        fout << r[i] << '\n';
    }
    return 0;
}