Cod sursa(job #1811960)

Utilizator StefansebiStefan Sebastian Stefansebi Data 21 noiembrie 2016 18:54:50
Problema Farfurii Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.74 kb
#include<fstream>
using namespace std;
ifstream fin("farfurii.in");
ofstream fout("farfurii.out");

/*
we use segment tree to determine the i'th element in the list in log time
*/
long long arb[300009];


/*
updates a value
*/
void update(long long n, long long l, long long r, long long pos, long long val) {
	if (l == r) {
		arb[n] = val;
		return;
	}
	long long m = (l + r) / 2;
	if (pos <= m) {
		update(n * 2, l, m, pos, val);
	}
	else {
		update(n * 2 + 1, m + 1, r, pos, val);
	}
	arb[n] = arb[n * 2] + arb[n * 2 + 1];
}

/*
gets the position of the i'th element
*/
void position(long long n, long long l, long long r, long long i, long long& pos) {
	if (l == r) {
		pos = l;
		return;
	}
	long long m = (l + r) / 2;
	if (i <= arb[n * 2]) {
		position(n * 2, l, m, i, pos);
	}
	else {
		position(n * 2 + 1, m + 1, r, i - arb[n * 2], pos);
	}
}

/*
creates the inversion table
*/
void make_inversions(long long n, long long k, long long inversions[]) {
	long long idx = n - 1;
	long long amount = k; long long value = 1;
	while (amount != 0) {
		if (amount < value) {
			value = amount;
			amount = 0;
		} //stopping condition
		else {
			amount -= value;
		}
		inversions[idx] = value;
		idx--;
		value++;
	}
}

int main() {
	long long n, k;
	long long inversions[100009];
	long long farfurii[100009];
	fin >> n >> k;
	for (long long i = 1; i <= n; i++) {
		farfurii[i] = i;
		inversions[i] = 0;
		update(1, 1, n, i, 1);
	}

	make_inversions(n, k, inversions);

	for (long long i = 1; i <= n; i++) {
		long long init_pos = inversions[i] + 1;
		long long actual_pos = 0;
		position(1, 1, n, init_pos, actual_pos);
		fout << farfurii[actual_pos] << " ";
		update(1, 1, n, actual_pos, 0);
	}
}