Cod sursa(job #1362654)

Utilizator cernat.catallinFMI Cernat Catalin Stefan cernat.catallin Data 26 februarie 2015 14:17:42
Problema Farfurii Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
/*
	Cautam o pozitie p pe care sa asezam o valoare x astfel incat daca asezam
	pe pozitiile [1, p - 1] valorile [1, p - 1], pe p x si pe [p + 1, n]
	result valorilor in ordine descrescatoare sa avem k inversiuni.
	Se poate vedea usor ca se poate asa ceva si nici o alta permutare cu k
	inversiuni nu este mai mica lexicografic.
*/
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

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

typedef long long int int64;

int64 n, k;

int main() {
	int64 p, x;
	in >> n >> k;

	for (p = n; p > 1 && k > n - p; --p)
		k -= (n - p);
	for (int i = 1; i < p; ++i)
		out << i << ' ';
	x = p + k;
	out << x << ' ';
	for (int i = n; i >= p; --i)
		if (i != x)
			out << i << ' ';

	return 0;
}