Pagini recente » Cod sursa (job #1847173) | Cod sursa (job #2421957) | Cod sursa (job #149911) | Cod sursa (job #3195455) | Cod sursa (job #3171155)
#include <bits/stdc++.h>
using namespace std;
ifstream in("schi.in");
ofstream out("schi.out");
const int NMAX = 30001;
int seg_tree[4*NMAX];
int sol[NMAX+1];
int v[NMAX+1];
int size_;
int baga( int st, int dr, int nod, int val ){
if( st == dr )
return st;
int mij = ( st + dr ) / 2;
if( val > seg_tree[nod*2] )
return baga( mij+1, dr, nod*2+1, val - seg_tree[nod*2] );
return baga( st, mij, nod*2, val );
}
/*void update( int poz ){
if( poz == 0 )
return;
seg_tree[poz]--;
cout << "in\n";
update(poz/2);
cout << "out\n";
}*/
void update(int poz) {
poz += size_ - 1;
while( poz ) {
seg_tree[poz]--;
poz /= 2;
}
}
void print() {
for (int i = 0; i < size_; i++) {
cout << seg_tree[i] << ' ';
}
cout << '\n';
for (int i = size_; i < size_ * 2; i++) {
cout << seg_tree[i] << ' ';
}
cout << '\n';
}
/*void update(int node_lf, int node_rg, int update_pos, int node = 1) {
if (node_lf == node_rg) {
seg_tree[node] = 0;
return;
}
int med = (node_lf + node_rg) / 2;
if (update_pos <= med) {
update(node_lf, med, update_pos, 2 * node);
} else {
update(med + 1, node_rg, update_pos, 2 * node + 1);
}
}*/
void build( int st, int dr, int nod ){
if( st == dr )
return;
int mij = ( st + dr ) / 2;
build(st, mij, nod*2);
build(mij+1, dr, nod*2+1);
seg_tree[nod] = seg_tree[nod*2] + seg_tree[nod*2+1];
}
int main()
{
int n;
in >> n;
int log2n = log2(n);
log2n += ((1 << log2n) < n);
size_ = 1 << log2n;
for( int i = 1; i <= n; i++ ){
in >> v[i];
seg_tree[i+ size_ - 1] = 1;
}
build(1, size_, 1);
// print();
for( int i = n; i > 0; i-- ){
int poz = baga(1, size_, 1, v[i] );
// cout << poz << ' ' << i << ' ' << v[i] << ": ";
update(poz);
// print();
sol[poz] = i;
}
for( int i = 1; i <= n; i++ )
out << sol[i] << "\n";
return 0;
}