From 96254947699986c59f0dc63d69fd4b76bd3ed43e Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Mon, 6 Jul 2026 19:08:08 +0200 Subject: Initial commit --- .../inverse_inversions_2214.cpp | 22 ++++++++++++++++++++++ 1 file changed, 22 insertions(+) create mode 100644 14_construction_problems/inverse_inversions_2214.cpp (limited to '14_construction_problems/inverse_inversions_2214.cpp') diff --git a/14_construction_problems/inverse_inversions_2214.cpp b/14_construction_problems/inverse_inversions_2214.cpp new file mode 100644 index 0000000..7e7ae07 --- /dev/null +++ b/14_construction_problems/inverse_inversions_2214.cpp @@ -0,0 +1,22 @@ +#include +#include +#include + +// Observation: putting 1 at the n-th position (1-based) generates n-1 +// inversions; then, putting 2 at n-2 generates another n-2 inversions; +// and so on. +// The first step in our algorithm counts how many times we can do this, +// and leaves k pointing to the position where we should put the next +// element. All other elements are in increasing order. + +int main() { + long long n, k, p, l, m, j, i{0}; + std::cin >> n >> k; + std::vector a(n, 0); + + for (j = 1, p = 0; p < n-1 && k >= n-j; p++, j++) k -= n-j; + + for (m = p+1, l = p+2, i = 0; i < n; i++) + std::cout << ((n-i <= p || i == k) ? m-- : l++) << " "; + std::cout << "\n"; +} -- cgit v1.3