Pagini recente » Istoria paginii runda/ichc_preoji2010/clasament | Cod sursa (job #76045) | Cod sursa (job #474891) | Cod sursa (job #218196) | Cod sursa (job #2981629)
#include <fstream>
#include <iostream>
#include <vector>
std::ifstream fin("schi.in");
std::ofstream fout("schi.out");
class tree{
public:
int size;
std::vector<int> list;
tree(int n){
size = n;
list.resize(n+5);
}
void update(int pos, int diff);
int query(int pos);
int find(int value);
void print();
};
int main(){
int n;
fin >> n;
tree Tree(n);
std::vector<int> positions(n+1), sol(n+1);
for(int i = 1; i <= n; i++){
fin >> positions[i];
}
//build tree
for(int i = 1; i <= n; i++){
Tree.update(i, 1);
}
for(int i = n; i >= 1; i--){
//find the pos[i] free pos
int newPos = Tree.find(positions[i]);
sol[newPos] = i;
Tree.update(newPos, -1);
}
for(int i = 1; i <= n; i++){
fout << sol[i] << "\n";
}
}
void tree::update(int pos, int diff){
while(pos <= size){
list[pos] += diff;
pos += (pos & -pos);
}
}
int tree::query(int pos){
int sum = 0;
while(pos > 0){
sum += list[pos];
pos -= (pos & -pos);
}
return sum;
}
int tree::find(int value){
int left = 1, right = size;
while(left < right){
int mid = left + (right - left)/2;
int querymid = query(mid);
if(value <= querymid){
right = mid;
}
else {
left = mid + 1;
}
}
return right;
}
void tree::print(){
for(auto it : list){
std::cout << it << " ";
}
}