Pagini recente » Cod sursa (job #3213209) | Cod sursa (job #2569577) | Cod sursa (job #3275662) | Cod sursa (job #1439817) | Cod sursa (job #3259910)
#include <bits/stdc++.h>
using namespace std;
string nume="schi";
ifstream in(nume+".in");
ofstream out(nume+".out");
#define cin in
#define cout out
const int MN=3e5+5;
int arb[MN*4];
int n;
//classic segment tree of the sum
void update(int nod,int st, int dr,int poz, int x)
{
if(st==dr){
arb[nod]+=x;
return;
}
nod*=2;
int mid=(st+dr)/2;
if(poz<=mid)update(nod,st,mid,poz,x);
else update(nod+1, mid+1,dr,poz,x);
arb[nod>>1]=arb[nod]+arb[nod+1];
}
/*
Query returns an available index.
query returns between all available positions which
val'th position will be. For ex if available indexes are
1, 4, 6, 7, 8 and val=3, then query will return 6.
Because 6 is 3rd available slot.
*/
int query(int nod, int st, int dr,int val)
{
if(st==dr) return st;
int mid=(st+dr)/2;
nod*=2;
//If not enough available slots are on the left then we must search on the RIGHT
if(arb[nod]<val) return query(nod+1,mid+1,dr,val-arb[nod]);
//if searched val is enough on the left then go LEFT
return query(nod,st,mid,val);
}
int v[MN];
int ans[MN];
int main()
{
cin>>n;
for(int i=1;i<=n;i++){
cin>>v[i];
update(1,1,n,i,1);
}
//start from the end because it will be computed for sure
for(int i=n;i>=1;i--){
//get the available slot for v[i]
int poz=query(1,1,n,v[i]);
//mark available slot at poz as ZERO
//so that position cannot be taken afterward by other players
update(1,1,n,poz, -1);
//mark poz as i because i'th player is at rank poz
ans[poz]=i;
}
for(int i=1;i<=n;i++)
cout<<ans[i]<<'\n';
return 0;
}