Pagini recente » Cod sursa (job #2684506) | Cod sursa (job #2543913) | Cod sursa (job #2253884) | Cod sursa (job #1195199) | Cod sursa (job #3288387)
#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;
}