Cod sursa(job #1361831)

Utilizator cernat.catallinFMI Cernat Catalin Stefan cernat.catallin Data 26 februarie 2015 00:04:04
Problema Farfurii Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
#include <fstream>
#include <algorithm>
using namespace std;

ifstream in("farfurii.in");
ofstream out("farfurii.out");

const int Nmax = 100005;
const int tree_size = 262144;


int n, k;
int tree[tree_size];
int taken[Nmax];
int position, value, result, a, b;

void update(int node, int l, int r) {
	if (l == r)
		tree[node] = value;
	else {
		int m = (l + r) >> 1;
		if (position <= m) update(node << 1, l, m);
		else update((node << 1) + 1, m + 1, r);
		tree[node] = tree[node << 1] + tree[(node << 1) + 1];
	}
}

void query(int node, int l, int r) {
	if (a <= l && r <= b)
		result += tree[node];
	else {
		int m = (l + r) >> 1;
		if (a <= m) query(node << 1, l, m);
		if (b > m) query((node << 1) + 1, m + 1, r);
	}
}

int main() {
	int p, q;

	in >> n >> k;
	p = q = 1;
	for (int i = 1; i <= n; ++i) {
		int nr = (n - i) * (n - i - 1) / 2;
		int need = k - nr;
		if (need < 0) need = 0;

		if (!need) {
			while (taken[p]) ++p;
			out << p << ' ';
			position = p;
			value = 1;
			update(1, 1, n);
			taken[p] = 1;
			++p;
		}
		else {
			q = p - 1;

			do {
				++q;
				while (taken[q]) ++q;
				a = 1;
				b = q - 1;
				result = 0;
				query(1, 1, n);
			} while ((q - 1 - result) < need);

			taken[q] = 1;
			position = q;
			value = 1;
			update(1, 1, n);
			out << q << ' ';
			k -= need;

			if (p == q) ++p;
		}

	}

	return 0;
}