Pagini recente » Cod sursa (job #2094983) | Cod sursa (job #2730586) | Cod sursa (job #1526602) | Cod sursa (job #108761) | Cod sursa (job #826791)
Cod sursa(job #826791)
#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);
}
int bit(int x)
{
return (x&(x-1))^x;
}
int query(int x)//pe intervalul 1 i tin nr de pozitii sterse
{
int i,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 left,right,mid,res,sol;
left = 1;
right = N;
while(left<=right)
{
mid = (left+right)/2;
res = mid - query(mid);//nr de 1 din (1,mid)
if(res == val)
sol = mid;
if(res>=val)
right = mid-1;
else
left = mid+1;
}
return sol;
}
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;
}