Pagini recente » Cod sursa (job #2885395) | Cod sursa (job #879264) | Cod sursa (job #1636308) | Cod sursa (job #1790230) | Cod sursa (job #3311819)
/**
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;
}