Pagini recente » Cod sursa (job #1935135) | Cod sursa (job #703710) | Cod sursa (job #1541013) | Cod sursa (job #1841916) | Cod sursa (job #2231757)
#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;
}