Pagini recente » Cod sursa (job #2870381) | Cod sursa (job #1695851) | Cod sursa (job #2643694) | Cod sursa (job #869608) | Cod sursa (job #999526)
Cod sursa(job #999526)
#include <fstream>
using namespace std;
ifstream fi("schi.in");
ofstream fo("schi.out");
int N,i,poz;
int A[30001];
int LOC[30001];
int REZ[30001];
// pe pozitia p se adauga valoarea v, cu consemnare in AIB
void g(int p, int v)
{
while (p<=N)
{
A[p]+=v;
p=p+((p^(p-1))&p);
}
}
// calculeaza suma din sir de la pozitia 1 pana la pozitia p, cu ajutorul AIB-ului
int f(int p)
{
int s;
s=0;
while (p>0)
{
s=s+A[p];
p=p-((p^(p-1))&p);
}
return s;
}
int bs(int st, int dr, int nr)
{
int m;
if (st==dr)
return st;
m=(st+dr)/2;
if (nr<=f(m))
return bs(st,m,nr);
else
return bs(m+1,dr,nr);
}
int main()
{
fi>>N;
for (i=1;i<=N;i++)
fi>>LOC[i];
for (i=1;i<=N;i++)
g(i,1);
for (i=N;i>=1;i--)
{
// prin cautare binara se determina
// pe ce pozitie este gasit cel de-al LOC[i] numar 1
poz=bs(1,N,LOC[i]);
g(poz,-1);
REZ[poz]=i;
}
for (i=1;i<=N;i++)
fo<<REZ[i]<<"\n";
fi.close();
fo.close();
return 0;
}