Cod sursa(job #2133044)
| Utilizator | Data | 16 februarie 2018 15:00:19 | |
|---|---|---|---|
| Problema | Schi | Scor | 85 |
| Compilator | cpp | Status | done |
| Runda | Arhiva de probleme | Marime | 0.63 kb |
#include<cstdio>
int aib[30005],n,v[30005],rasp[30005];
int update(int poz){
int i;
for(i=poz;i<=n;i=i+(i&(-i)))
aib[i]++;}
int query(int poz){
int i,s=0;
for(i=poz;i>0;i=i-(i&(-i)))
s=s+aib[i];
return s;}
int main(){
freopen("schi.in","r",stdin);
freopen("schi.out","w",stdout);
int i,nr,st,dr,mij;
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&v[i]);
for(i=n;i>=1;i--){
st=1;
dr=n;
while(st<=dr){
mij=(st+dr)/2;
nr=query(mij);
if (mij-nr==v[i] && nr-query(mij-1)==0)
break;
if (mij-nr<v[i])
st=mij+1;
if (mij-nr>=v[i])
dr=mij-1;}
update(mij);
rasp[mij]=i;}
for(i=1;i<=n;i++)
printf("%d\n",rasp[i]);
return 0;}
