Pagini recente » Cod sursa (job #2218315) | Cod sursa (job #1633327) | Cod sursa (job #2200963) | Cod sursa (job #197152) | Cod sursa (job #2953997)
#include <bits/stdc++.h>
using namespace std;
ifstream f("schi.in");
ofstream g("schi.out");
const int NMAX=30005;
int n,pos,SumTree[4*NMAX];
vector<int>v,ans;
void update(int node,int left,int right)
{
if(left==right)///leaf
{
SumTree[node]=1;
return;
}
int middle=(left+right)/2;
if(pos<=middle)
update(2*node,left,middle);///update left son
else
update(2*node+1,middle+1,right);///update right son
SumTree[node]=SumTree[2*node]+SumTree[2*node+1];
}
int find_kth_zero(int k,int node,int left,int right)
{
if(left==right)///leaf
return left;///the answer
int middle=(left+right)/2,left_side_zeroes=(middle-left+1)-SumTree[2*node];///because SumTree represents the number of ones
if(k<=left_side_zeroes)
find_kth_zero(k,2*node,left,middle);///left son
else
find_kth_zero(k-left_side_zeroes,2*node+1,middle+1,right);///right son, we deduce the zeroes from the left son
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
f>>n;
v.resize(n+1);
ans.resize(n+1);
for(int i=1; i<=n; i++)
f>>v[i];
for(int i=n; i>=1; i--)///we take the positions in reverse order
{
pos=find_kth_zero(v[i],1,1,n);
update(1,1,n);
ans[pos]=i;
}
for(int i=1; i<=n; i++)
g<<ans[i]<<'\n';
return 0;
}