Pagini recente » Cod sursa (job #543796) | Cod sursa (job #1374204) | Cod sursa (job #1042316) | Cod sursa (job #1514549) | Cod sursa (job #2101244)
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("schi.in");
ofstream fout("schi.out");
int v[30001], aib[30001], clasament[30001];
int n;
///tata[i] = i+=(i&-i)
///anterior[i] = i-(i&-i)
void update(int k)
{
int i;
for(i=k; i<=n; i+=(i&-i)) //se duce din tata in tata
aib[i]--;
}
int query(int k)
{
int ans=0, i;
for(i=k; i>=1; i-=(i&-i)) //se duce din fiu in fiu
ans += aib[i];
return ans;
}
int caut_bin (int st, int dr, int k)
{
int m;
//pt ca sigur o sa gaseasca nr de pozitii corespunzatoare
while(st <= dr)
{
m = ( st + dr ) / 2; //overflow: st+(dr-st)/2
int libere = query(m);
if(libere < k)
st = m+1;
else
dr = m-1;
}
update(dr+1);
return dr+1;
}
int main()
{
int i;
fin>>n;
for(i=1; i<=n; i++)
fin>>v[i];
for(i=1; i<=n; i++)
aib[i]=(i&-i);
//for(i=1; i<=n; i++)
//cout<<aib[i]<<" ";
for(i=n; i>=1; i--)
{
int poz = caut_bin(1, n, v[i]);
clasament[poz]=i;
/*if ( query( v[i] ) == v[i] )
{
update(v[i]);
clasament[i] = i;
}
else
{
int poz = caut_bin(v[i], n, v[i]);
clasament[poz] = i;
}*/
}
for(i=1; i<=n; i++)
fout<<clasament[i]<<'\n';
return 0;
}