Cod sursa(job #3267890)

Utilizator octavurlurleteanu alexandru octavian octavurl Data 12 ianuarie 2025 19:45:35
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda cex_6 Marime 1.11 kb
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
ifstream fin("schi.in");
ofstream fout("schi.out");
class
{
	vector<int>aib , v,finall;
	int n;
	void add(int x, int val)
	{
		for (int i = x; i <= n; i += i & (-i))
			aib[i] += val;
	}
	int query(int x)
	{
		int suma = 0; 
		for (int i = x; i >= 1; i -= i & (-i))
			suma += aib[i];
		return suma;
	}
	int cautare_binara(int x)
	{
		int st = 1, dr = n;
		int p = -1;
		while (st <= dr)
		{
			int mij = (st + dr) / 2;
			int suma = query(mij);
			if (x > suma)
				st = mij + 1;
			else if (x < suma)
				dr = mij - 1;
			else
			{
				p = mij;
				dr = mij - 1;
			}
		}
		return p; 
	}
	void citire()
	{
	fin >> n;
	v.resize(n + 1);
	aib.resize(n + 1);
	finall.resize(n + 1);
	for (int i = 1; i <= n; ++i)
	{
		fin >> v[i];
		add(i, 1);
	}
	for (int i = n; i >= 1; --i)
	{
		int x = cautare_binara(v[i]);
		finall[x] = i;
		add(x, -1);
	}
	for (int i = 1; i <= n; ++i)
		fout << finall[i] << '\n';
	}
public:
	void problema()
	{
		citire();
	}
}l;
int main()
{
	l.problema();
}