Cod sursa(job #1361924)

Utilizator cernat.catallinFMI Cernat Catalin Stefan cernat.catallin Data 26 februarie 2015 01:46:40
Problema Farfurii Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.59 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;

typedef long long int64;


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

void update(int node, int l, int r) {
	if (l == r)
		tree[node] = 0;
	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);
	}
}

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

int search(int count) {
	int pos = 0;
	int step = 1 << 17;
	while (step >>= 1) {
		if (pos + step <= n) {
			a = 1;
			b = pos + step;
			result = 0;
			query(1, 1, n);
			if (result < count)
				pos += step;
		}
	}
	return pos + 1;
}

int main() {
	int64 answer = 0;
	int64 count = 0;

	in >> n >> k;
	construct(1, 1, n);
	for (int i = 1; i <= n; ++i) {
		count = k - 1LL * (n - i) * (n - i - 1) / 2;
		if (count < 0)
			position = search(1);
		else {
			position = search(count + 1);
			k -= count;
		}
		update(1, 1, n);
		out << position << ' ';
	}

	return 0;
}