Pagini recente » Borderou de evaluare (job #2388799) | Cod sursa (job #2486035)
#include <fstream>
using namespace std;
int n,aib[30005],cls[30005],a[30005];
ifstream in("schi.in");
ofstream out("schi.out");
void Update(int p, int x)
{
while(p<=n)
{
aib[p]+=x;
///aflu cati biti de 0 sunt la finalul lui p(2 la put. nr biti)
int i=1;
while(p%(i*2)==0)
i*=2;
p+=i;
///sau fara while folosind p+=(p&(-p)); sau -p=p-1;
}
}
/// suma ap[1..p]
int Suma(int p)
{
int S=0;
while(p>0)
{
S+=aib[p];
p-=(p&(-p));
}
return S;
}
/// cauta cea mai din stanga pozitie poz cu suma a[1]+..a[poz]=s
int CautBin(int p,int s)
{
int st,dr,poz,mij;
st=1;dr=p;poz=-1;
int suma;
while(st<=dr)
{
mij=(st+dr)/2;
suma=Suma(mij);
if(suma==s)
{
poz=mij;
dr=mij-1;
}
else if(suma>s) dr=mij-1;
else st=mij+1;
}
return poz;
}
int main()
{
int i,x,poz;
in>>n;
for(i=1;i<=n;i++)
{
in>>a[i];
Update(i,1);/// adaugi 1 peste tot
}
for(i=n;i>=1;i--)
{
x=a[i];
/// caut cea mai din stanga pozitie poz
/// cu suma(poz)=x;
poz=CautBin(n,x);
Update(poz,-1);
cls[poz]=i;
}
for(i=1;i<=n;i++)
out<<cls[i]<<"\n";
return 0;
}