Cod sursa(job #2904410)

Utilizator larisa-ioana.virtejanuLarisa Ioana Virtejanu larisa-ioana.virtejanu Data 17 mai 2022 23:33:09
Problema Farfurii Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.37 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 poz, val, rez, a, b;
 
void update(int node, int l, int r) {
	if (l == r)
		tree[node] = val;
	else {
		int m = (l + r) >> 1;
		if (poz <= 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)
		rez += 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 << ' ';
			poz = p;
			val = 1;
			update(1, 1, n);
			taken[p] = 1;
			++p;
		}
		else {
			q = p - 1;
 
			do {
				++q;
				while (taken[q]) ++q;
				a = 1;
				b = q - 1;
				rez = 0;
				query(1, 1, n);
			} while ((q - 1 - rez) < need);
 
			taken[q] = 1;
			poz = q;
			val = 1;
			update(1, 1, n);
			out << q << ' ';
			k -= need;
 
			if (p == q) ++p;
		}
 
	}
 
	return 0;
}