Cod sursa(job #2314305)

Utilizator lucianistratiIstrati Lucian lucianistrati Data 8 ianuarie 2019 12:17:13
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.17 kb
#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;
}