Pagini recente » Cod sursa (job #2407747) | Cod sursa (job #912412) | Cod sursa (job #3264637) | Cod sursa (job #229511) | Cod sursa (job #826813)
Cod sursa(job #826813)
#include <fstream>
#define Nmax 30001
using namespace std;
short int N,v[Nmax],q,sol[Nmax],AIB[Nmax];
void read_data()
{
ifstream f("schi.in");
f>>N;
int i;
for(i=1;i<=N;++i)
f>>v[i];
f.close();
}
void write_data()
{
ofstream g("schi.out");
for(int i=1;i<=N;++i)
g<<sol[i]<<"\n";
g.close();
}
int bit(int x)
{
return (x&(x-1))^x;
}
short int query(int x)//pe intervalul 1 i tin nr de pozitii sterse
{
int i;
short 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];
}
short 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;
}