Pagini recente » Cod sursa (job #2518660) | Cod sursa (job #1095581) | Cod sursa (job #1491148) | Cod sursa (job #68392) | Cod sursa (job #3260539)
#include <bits/stdc++.h>
using namespace std;
/**
9
5 2 8 3 9 7 1 4 6
1 2 3 4 5 6 7 8 9
fr = 0 1 1 0 1 0 0 1 0
aib[i] = suma elementelor din fr[i-2^k+1,i] (de lungime 2^k)
unde k este numarul de biti de 0 cu care se termina i
in baza 2
i baza_2 intervalul suma
1 0001 [1,1] 0
2 0010 [1,2] 1
3 0011 [3,3] 1
4 0100 [1,4] 2
5 0101 [5,5] 1
6 0110 [5,6] 1
7 0111 [7,7] 0 [1,7] = [7,7]+[5,6]+[1,4]
8 1000 [1,8] 4
9 1001 [9,9] 0
*/
ifstream fin("schi.in");
ofstream fout("schi.out");
int aib[30002], n, sol[30002],a[30002];
/// ret. suma fr[1]+fr[2]+...+fr[p]
int Query(int p)
{
int suma = 0;
while (p > 0)
{
suma += aib[p];
/// scadem din p valoarea 2^k
p -= (p & (-p));
}
return suma;
}
/// aduna x la toate componentele aib[j] care-l contin pe p
void Update(int p, int x)
{
while (p <= n)
{
aib[p] += x;
p += (p & (-p));
}
}
/// cauta cea mai din stanga poz p in care Query(p) = x
int CautBin(int x)
{
int st,dr,mij,p,q;
p=-1;
st=1;
dr=n;
while(st<=dr)
{
mij=(st+dr)/2;
q=Query(mij);
if(q==x)
{
p=mij;
dr=mij-1;
}
else if(q<x)
st=mij+1;
else
dr=mij-1;
}
return p;
}
int main()
{
int i, x, p;
fin >> n;
for (i = 1; i <= n; i++)
{
fin >> a[i];
Update(i,1);
}
for(i=n;i>=1;i--)
{
x=a[i];
/// cautam al x-lea 1
p=CautBin(x);
sol[p]=i;
Update(p,-1);
}
for(i=1;i<=n;i++) fout<<sol[i]<<'\n';
return 0;
}