Cod sursa(job #1834105)

Utilizator smatei16Matei Staicu smatei16 Data 23 decembrie 2016 21:33:15
Problema Schi Scor 85
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <cstdio>
#define zeros(x)(x&(-x))
using namespace std;
int n,aib[30003],a[30003],b[30003];
void add(int x){
for(int i=x;i<=n;i+=zeros(i))
aib[i]++;
}
int sum(int x){
int sum=0;
for(int i=x;i>0;i-=zeros(i))
sum+=aib[i];
return sum;
}
int caut(int x,int i){
int st,dr,mij;
st=1;dr=n;mij=(st+dr)/2;
if(b[st]==0 && st-sum(st)==x){
b[st]=i;
add(st);
}
else if(b[dr]==0 && dr-sum(dr)==x){
b[dr]=i;
add(dr);
}
else{
while(st<=dr){
if(b[mij]==0 && (mij-sum(mij))==x){
b[mij]=i;
add(mij);
break;
}
if(mij-sum(mij)<x)st=mij;
else dr=mij;
mij=(st+dr)/2;
}
}}
int i;
int main()
{freopen("schi.in","r",stdin);
freopen("schi.out","w",stdout);
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
for(i=n;i>=1;i--){
caut(a[i],i);
}
for(i=1;i<=n;i++)printf("%d\n",b[i]);

    return 0;
}