Pagini recente » Cod sursa (job #2169110) | Cod sursa (job #383782) | Cod sursa (job #368800) | Cod sursa (job #2624926) | Cod sursa (job #2314305)
#include <iostream>
#include <fstream>
#define si(nr) (nr&(-nr)) //este calculat si logic
using namespace std;
int aib[30001],index[30001],v[30001],N,poz;
/*
aib-retine arborele indexat binar
index-retine clasamentul final pentru fiecare dintre cei N concurenti
v-vectorul care retine locul fiecarui concurent in clasamentul intermediar
*/
void update(int poz,int val)
{
int i;
for(i=poz;i<=N;i+=si(i)) //i este incrementat cu pasul si logic aplicat lui i
{
aib[i]+=val; //adaugarea lui val in arborelui indexat binar
}
}
int sum(int poz)
{
int s=0,i;
for(i=poz;i>=1;i-=si(i)) //este calculata suma de la pozitia poz pana la inceputul arborelui indexat binar
{
s+=aib[i]; //este calculat s
}
return s;
}
int cautare(int st,int dr,int k)
{
/*
subprogramul iterativ cautare
realizeaza o cautarea binara particularizata
in care cauta pozitia pe care se afla in vecorul v
pozitia concurentului i,instabilind o pozitie initiala k
*/
int val,poz,mij;
while(st<=dr)
{
mij=(st+dr)/2; // mij preia mijlocul secventei
val=sum(mij);//este calculata in val suma de la pozitia mij
// pana la inceputul arborelui indexat binar
if(val>=v[k])
{
poz=mij; //poz primeste mij
dr=mij-1;//dr ajunge la stanga mijlocului
}
else
{
st=mij+1;//st ajunge la dreapta mijlocului
}
}
return poz;
}
int main()
{
ifstream fin("schi.in");
ofstream fout("schi.out");
int i;
fin>>N; //se citeste N numarul de concurenti
for(i=1;i<=N;i++)
{
fin>>v[i]; //se citesc locurile pe care se afla fiecare concurent in clasamentul intermediar cu evolutia sa
update(i,1); // se update-aza la pozitia i
}
for(i=N;i>=1;i--)
{
poz=cautare(1,N,i); // se cauta apeland subprogramul cautare pe pozitia i
index[poz]=i; //se retine la pozitia poz clasamentul final al concurentului i
update(poz,-1);
}
for(i=1;i<=N;i++)
{
fout<<index[i]<<'\n'; //se afiseaza numarul de ordine pe care se afla concurentii in clasamentul final
}
fin.close();
fout.close();
return 0;
}