Cod sursa(job #3190576)

Utilizator leelcheeseCiovnicu Denis leelcheese Data 7 ianuarie 2024 18:45:32
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;
#define ll long long 
#define ull unsigned long long 
#define nmax 30006
#define MOD 9901 
#define INF 2123456789
//#define fin cin 
//#define fout cout 
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx2")

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

int aib[nmax], a[nmax], cls[nmax], n;

void Update(int p, int y)
{
	while (p <= n)
	{
		aib[p] += y;
		p += (p & (-p));
	}
}

int Query(int p)
{
	int suma = 0;
	while (p > 0)
	{
		suma += aib[p];
		p -= (p & (-p));
	}
	return suma;
}
/// cauta binar cea mai din stanga pozitie p
/// in care a[1]+...+a[p] = x
/// daca p nu exista returnam -1
/// O(log^2 n)
int CautBin(int x)
{
	int st, dr, mij, p, q;
	st = 1; dr = n; p = 0;
	while (st <= dr)
	{
		mij = (st + dr) / 2;
		q = Query(mij);
		if (q == x)
		{
			p = mij;
			dr = mij - 1;
		}
		else if (q > x)
			dr = mij - 1;
		else
			st = mij + 1;
	}
	return p;
}

int main()
{
	int i, p;
	fin >> n;
	for (i = 1; i <= n; i++)
	{
		fin >> a[i];
		Update(i, 1);
	}
	for (i = n; i >= 1; i--)
	{
		p = CautBin(a[i]);
		cls[p] = i;
		Update(p, -1);
	}
	for (i = 1; i <= n; i++)
		fout << cls[i] << "\n";
	fin.close();
	fout.close();
	return 0;
}