Pagini recente » Cod sursa (job #3239521) | Cod sursa (job #2966452) | Cod sursa (job #2762478) | Cod sursa (job #3205723) | Cod sursa (job #2509319)
/*Pentru a rezolva problema vom reține, într-un arbore indexat binar numărul de poziții libere în clasamentul final.
Astfel, elementul AIB[x] va reține câte poziții libere există între [x-2k+1,..,x]. Se va parcurge invers șirul din
fișierul de intrare, și pentru fiecare valoare X[i], se va determina cea mai mica poziție x pentru care suma
elementelor din AIB pe intervalul [1..x] este egală cu X[i].
Poziția x este poziția din clasamentul final a concurentului cu mumărul de ordine i.
*/
#include <bits/stdc++.h>
#define NMAX 30005
#define op(i) (i & (-i) )
using namespace std;
int N , x , y ;
int v[NMAX] , aib[NMAX] , sol[NMAX];
void Update (int poz ,int val)
{
int i ;
for (int i = poz ; i <= N ; i += op(i))
aib[i] += val;
return ;
}
int suma (int poz)
{
int i ;
int sum = 0 ;
for (int i = poz ; i >= 1 ; i -= op(i))
sum += aib[i] ;
return sum ;
}
int BinarySearch (int st , int dr , int val)
{
int Min = N + 1;
while (st <= dr)
{
int mij = (st + (dr - st) / 2) ;
int Sum = suma(mij);
if (val == Sum && mij < Min) Min = mij;
else if (val <= Sum) dr = mij - 1 ;
else st = mij + 1 ;
}
return Min ;
}
int main()
{
freopen("schi.in" , "r" , stdin) ;
freopen("schi.out" , "w" , stdout) ;
scanf ("%d" , &N) ;
for (int i = 1 ; i <= N ; ++i)
{
scanf("%d" , &v[i]) ;
aib[i] = op(i); //
}
for (int i = N ; i >= 1 ; --i)
{
int conc = BinarySearch(1,N,v[i]) ;
Update(conc,-1) ;
sol[conc] = i ; // Concurentul 'conc' se afla pe poz 'i'
}
for (int i = 1 ; i <= N ; ++i) printf("%d ", sol[i]) ;
return 0 ;
}