inverse_inversions_2214.cpp (703B)
1 #include <iostream> 2 #include <utility> 3 #include <vector> 4 5 // Observation: putting 1 at the n-th position (1-based) generates n-1 6 // inversions; then, putting 2 at n-2 generates another n-2 inversions; 7 // and so on. 8 // The first step in our algorithm counts how many times we can do this, 9 // and leaves k pointing to the position where we should put the next 10 // element. All other elements are in increasing order. 11 12 int main() { 13 long long n, k, p, l, m, j, i{0}; 14 std::cin >> n >> k; 15 std::vector<long long> a(n, 0); 16 17 for (j = 1, p = 0; p < n-1 && k >= n-j; p++, j++) k -= n-j; 18 19 for (m = p+1, l = p+2, i = 0; i < n; i++) 20 std::cout << ((n-i <= p || i == k) ? m-- : l++) << " "; 21 std::cout << "\n"; 22 }