Cod sursa(job #826909)
#include <stdio.h>
#define Nmax 30001
using namespace std;
int N,v[Nmax],q,sol[Nmax],AIB[Nmax];
void read_data()
{
FILE*f = fopen("schi.in","r");
fscanf(f,"%d",&N);
int i;
for(i=1;i<=N;++i)
fscanf(f,"%d",&v[i]);
fclose(f);
}
void write_data()
{
FILE*g = fopen("schi.out","w");
for(int i=1;i<=N;++i)
fprintf(g,"%d\n",sol[i]);
fclose(g);
}
inline int bit(int x)
{
return (x&(-x));
}
int query(int x)//pe intervalul 1 i tin nr de pozitii sterse
{
int i;
int s;
for(i=x,s=0;i>=1;i-=bit(i))
s+=AIB[i];
return s;
}
void update(int x)
{
int i;
for(i=x;i<=N;i+=bit(i))
++AIB[i];
}
int check(int val)
{
int step,i;
for(step=1;step<N;step <<=1 );
for(i = N;step;step >>= 1)
if(i-step >= 1)
if((i - step) - query(i-step) >= val)
i-=step;
return i;
}
int main()
{
read_data();
int i;
for(i=N;i>=1;--i)
{
q = check(v[i]);//a v[i]-a pozitie libera
sol[q] = i;//este ocupata de concurentul i
update(q);
}
write_data();
return 0;
}