Pagini recente » Istoria paginii runda/simulare_oji_hlo_avansati | Cod sursa (job #720543) | Cod sursa (job #822025) | Cod sursa (job #1070918) | Cod sursa (job #2486031)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("schi.in");
ofstream fout("schi.out");
/** 1 2 3 4 5 6 7 8
a= 2 3 5 1 4 2 7 3
aib[i]=suma elementelor din a[i-2 la k +1,i]
k=nr de biti de 0 de la sfarsitul lui i(reprezentat in baza 2)
(2,6)=(1,6)-(1,1)
**/
int n,aib[100001],m,cls[30005],a[30005];
void Update(int p,int x)
{
while(p<=n)
{
aib[p]+=x;
/**
aflu cati biti de 0 sunt la finalul lui p(2 la nr de biti)
int i=1;/// 2 la 0
while(p%(i*2)==0)
i=i*2;
p+=i;
*/
p+=(p&(-p));
}
}
///suma de la a[1] la a[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 CB(int p,int s)
{
int st,dr,poz,mij,suma;
st=1;dr=p;poz=-1;
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;
fin>>n;
for(i=1;i<=n;i++)
{
fin>>a[i];
Update(i,1);
}
for(i=n;i>0;i--)
{
x=a[i];
///caut cea mai din stanga pozitie poz cu suma(poz)=x
poz=CB(n,x);
Update(poz,-1);
cls[poz]=i;
}
for(i=1;i<=n;i++)
fout<<cls[i]<<"\n";
fout.close();
fin.close();
return 0;
}