Pagini recente » Cod sursa (job #190227) | Cod sursa (job #1046242) | Cod sursa (job #451581) | Cod sursa (job #977724) | Cod sursa (job #2924193)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream cin("schi.in");
ofstream cout("schi.out");
class Fenwick {
private:
int n;
vector<int> bit;
void update(int node,int val) {
int ix=node;
while(ix<=n) {
bit[ix]+=val;
ix+=(ix & (~ix+1));
}
}
int query(int node) {
int ix=node,sum=0;
while(ix>0) {
sum+=bit[ix];
ix-=(ix & (~ix+1));
}
return sum;
}
public:
void resize(int n) {
this->n=n;
bit.resize(n+1);
}
void update(int l,int r,int val) {
update(l,val);
update(r+1,-val);
}
int query(int l,int r) {
return query(r)-query(l-1);
}
};
int n;
vector<int> v;
Fenwick aib;
void read() {
cin>>n;
v.resize(n+1);
for(int i=1;i<=n;i++) {
cin>>v[i];
}
}
int bs(int val) {
int l=1,r=n,mid,res=-1;
while(l<=r) {
mid=l+(r-l)/2;
int nr=aib.query(1,mid);
if(nr==val) {
res=mid;
r=mid-1;
}
else if(nr>val) {
r=mid-1;
}
else {
l=mid+1;
}
}
return res;
}
void solve() {
aib.resize(n);
for(int i=1;i<=n;i++) {
aib.update(i,n,1);
}
// cout<<bs(1)<<"\n";
// for(int i=1;i<=n;i++) {
// cout<<aib.query(1,i)<<" ";
// }
// cout<<"\n";
int pos;
vector<int> res(n+1);
for(int i=n;i>0;i--) {
pos=bs(v[i]);
if(pos>-1) {
res[pos]=i;
aib.update(pos,n,-1);
}
}
for(int i=1;i<=n;i++) {
cout<<res[i]<<"\n";
}
}
int main() {
read();
solve();
return 0;
}