Cod sursa(job #1779787)

Utilizator preda.andreiPreda Andrei preda.andrei Data 15 octombrie 2016 16:48:34
Problema Farfurii Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <fstream>
#include <vector>

using namespace std;

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

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

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

int Gaseste(const vector<int> &aib, int k)
{
	unsigned poz = 0;
	unsigned put = (1 << 20);

	while (put > 0) {
		if (poz + put < aib.size() && AflaSuma(aib, poz + put) < k)
			poz += put;
		put >>= 1;
	}
	return poz + 1;
}

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

	long long n, k;
	fin >> n >> k;

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

	int len = n - 1;
	for (int i = 1; i <= n; ++i) {
		long long ordin = max(1LL, k - len * (len - 1) / 2 + 1);
		k -= (ordin - 1);

		int poz = Gaseste(aib, ordin);
		Adauga(aib, poz, -1);
		fout << poz << " ";
		--len;
	}

	return 0;
}