Cod sursa(job #2231757)

Utilizator DRLDRLRaul Ronald Galea DRLDRL Data 15 august 2018 20:43:44
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.98 kb
#pragma once


#include<fstream>
#include<iostream>

using namespace std;

#define ARBDIM 120000
#define ElemDim 30001

ifstream fin("schi.in");
ofstream fout("schi.out");


int arbint[ARBDIM], v[ElemDim], locuriFinale[ElemDim];

void build(int nod, int st, int dr) {
	if (st == dr) {
		arbint[nod] = 1;
		return;
	}
	int mid = st + (dr - st) / 2;
	build(2 * nod, st, mid);
	build(2 * nod + 1, mid + 1, dr);

	arbint[nod] = arbint[2 * nod] + arbint[2 * nod + 1];
}

void update(int nod, int st, int dr, int poz) {
	if (st == dr) {
		arbint[nod] = 0; // marcarea cu 0 a unui loc inseamna ca acel loc a fost ocupat in mod final de un concurent, iar toti cei ce au concurat intainte si au ocupat locuri >= vor fi nevoiti sa se mute o pozitie in dreapta
		return;
	}
	int mid = st + (dr - st) / 2;

	if (poz <= mid)
		update(2 * nod, st, mid, poz);
	else
		update(2 * nod + 1, mid + 1, dr, poz);

	arbint[nod] = arbint[2 * nod] + arbint[2 * nod + 1];
}

int queryPozitieFinala(int nod, int st, int dr, int locConcurs) {
	if (st == dr) {
		return st;
	}
	int mid = st + (dr - st) / 2;

	if (arbint[2 * nod] >= locConcurs) {   // pentru ocuparea locului x, sunt necesare x-1 locuri inainte, iar cele y marcate cu 0, concurenti ce au obtinut locurile dupa cel actual, au efectul de a muta spre dreapta
		return queryPozitieFinala(2 * nod, st, mid, locConcurs);
	}
	else {
		return queryPozitieFinala(2 * nod + 1, mid + 1, dr, locConcurs - arbint[2 * nod]); // se iau in considerare locurile din stanga
	}
}





int main() {
	int nr,locFinal;
	fin >> nr;
	for (int i = 1; i <= nr; i++)
		fin >> v[i];
	build(1, 1, nr);

	for (int i = nr; i >= 1; i--) {
		locFinal = queryPozitieFinala(1, 1, nr, v[i]);
		locuriFinale[locFinal] = i; // pe locul locFinal este concurentul cu numarul i
		update(1, 1, nr, locFinal); // locFinal e ocupat, restul merg pe locurile ocupat + 1
	}

	for (int i = 1; i <= nr; i++)
		fout << locuriFinale[i] << "\n";
	return 0;
}