Pagini recente » Cod sursa (job #1397169) | Cod sursa (job #1318919) | Cod sursa (job #811095) | Cod sursa (job #821710) | Cod sursa (job #329930)
Cod sursa(job #329930)
#include <algorithm>
#define DIM 30005
using namespace std;
struct schi {int loc,ind;} a[DIM];
int aib[DIM],v[DIM];
int n;
void read ()
{
int i;
scanf ("%d",&n);
for (i=1; i<=n; ++i)
scanf ("%d",&v[i]);
}
int lsb (int x)
{
return x&(x-1)^x;
}
void update (int poz,int val)
{
for ( ; poz<=n; poz+=lsb (poz))
aib[poz]+=val;
}
void prec ()
{
int i;
for (i=1; i<=n; ++i)
{
update (i,1);
a[i].ind=i;
}
}
int query (int poz)
{
int sum;
for (sum=0; poz; poz-=lsb (poz))
sum+=aib[poz];
return sum;
}
int cbin (int val)
{
int st,dr,mij,nr,sol;
for (st=1, dr=n; st<=dr; )
{
mij=(st+dr)/2;
nr=query (mij);
if (nr==val)
sol=mij;
if (nr<val)
st=mij+1;
else
dr=mij-1;
}
return sol;
}
void solve ()
{
int i;
for (i=n; i; --i)
{
a[i].loc=cbin (v[i]);
update (a[i].loc,-1);
}
}
int cmp (schi a,schi b)
{
return a.loc<b.loc;
}
void print ()
{
int i;
for (i=1; i<=n; ++i)
printf ("%d\n",a[i].ind);
}
int main ()
{
freopen ("schi.in","r",stdin);
freopen ("schi.out","w",stdout);
read ();
prec ();
solve ();
sort (a+1,a+n+1,cmp);
print ();
return 0;
}