Pagini recente » Cod sursa (job #789544) | DeehoroEjkoli | Cod sursa (job #1987514) | Cod sursa (job #746692) | Cod sursa (job #3177777)
#include <bits/stdc++.h>
using namespace std;
ifstream f("schi.in");
ofstream g("schi.out");
int n,pos;
vector<int>v,ranking,aib;
void update(int node,int value)
{
for(; node<=n; node+=node&(-node))
aib[node]+=value;
}
int query(int node)
{
int ans=0;
for(; node>0; node-=node&(-node))
ans+=aib[node];
return ans;
}
int magical_binary_search(int value)
{
int ans=0,curr_sum=0;
for(int step=(1<<30); step>0; step>>=1) ///we search for the last position with the sum strictly smaller than value
if(ans+step<=n && curr_sum+aib[ans+step]<value)
{
ans+=step;
curr_sum+=aib[ans];
}
if(ans+1>n || query(ans+1)!=value) ///if the sum for the next position isn't equal to value we return -1
return -1; ///not gonna happen in this problem
return ans+1;
}
int main()
{
f>>n;
v.resize(n+1);
ranking.resize(n+1);
aib.resize(n+1);
///later we want to find the v[i] 1,
///so its easier to start with all elements being 1
for(int i=1; i<=n; i++)
update(i,1);
for(int i=1; i<=n; i++)
f>>v[i];
for(int i=n; i>=1; i--)
{
pos=magical_binary_search(v[i]); ///returns the position of the v[i] 1
update(pos,-1); /// we update that position with 0 because it can't be used anymore
ranking[pos]=i;
}
for(int i=1; i<=n; i++)
g<<ranking[i]<<'\n';
return 0;
}