Cod sursa(job #1779808)

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

using namespace std;

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

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

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

long long Gaseste(const vector<long long> &aib, long long k)
{
	long long poz = 0;
	long long 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<long long> aib(n + 1, 0);
	for (long long i = 1; i <= n; ++i)
		Adauga(aib, i, 1);

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

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

	return 0;
}