Cod sursa(job #1763359)

Utilizator preda.andreiPreda Andrei preda.andrei Data 24 septembrie 2016 13:16:03
Problema Schi Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>

using namespace std;

inline int PutereZerouri(int n)
{
	return (n ^ (n - 1)) & n;
}

void Adauga(vector<int> &aib, int poz, int val)
{
	while (poz < aib.size()) {
		aib[poz] += val;
		poz += PutereZerouri(poz);
	}
}

int AflaValoare(const vector<int> &aib, int poz)
{
	int suma = 0;
	while (poz > 0) {
		suma += aib[poz];
		poz -= PutereZerouri(poz);
	}
	return suma;
}

int GasesteLoc(vector<int> &aib, int poz)
{
	int st = 1, dr = aib.size() - 1;
	int loc = 0;

	while (st <= dr && !loc) {
		int mij = st + (dr - st) / 2;
		int val = AflaValoare(aib, mij);
		if (val == poz)
			loc = mij;
		else if (val > poz)
			dr = mij - 1;
		else st = mij + 1;
	}

	Adauga(aib, loc, -1);
	return loc;
}

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

	int n;
	fin >> n;

	vector<int> aib(n + 1);
	vector<int> pozitii(n + 1);
	vector<pair<int, int>> rezultate;

	for (int i = 1; i <= n; ++i)
		Adauga(aib, i, 1);

	for (int i = 1; i <= n; ++i)
		fin >> pozitii[i];

	for (int i = n; i >= 1; --i) {
		int loc = GasesteLoc(aib, pozitii[i]);
		rezultate.push_back({ loc, i });
	}

	sort(rezultate.begin(), rezultate.end());
	for (auto r : rezultate)
		fout << r.second << "\n";

	return 0;
}