English · Original
Chinese · Translation
Formal · Original
Merge sort is a well-known sorting algorithm. The main function that sorts the elements of array _a_ with indices from \[_l_, _r_) can be implemented as follows:
1. If the segment \[_l_, _r_) is already sorted in non-descending order (that is, for any _i_ such that _l_ ≤ _i_ < _r_ - 1 _a_\[_i_\] ≤ _a_\[_i_ + 1\]), then end the function call;
2. Let ;
3. Call _mergesort_(_a_, _l_, _mid_);
4. Call _mergesort_(_a_, _mid_, _r_);
5. Merge segments \[_l_, _mid_) and \[_mid_, _r_), making the segment \[_l_, _r_) sorted in non-descending order. The merge algorithm doesn't call any other functions.
The array in this problem is 0\-indexed, so to sort the whole array, you need to call _mergesort_(_a_, 0, _n_).
The number of calls of function _mergesort_ is very important, so Ivan has decided to calculate it while sorting the array. For example, if _a_ = {1, 2, 3, 4}, then there will be 1 call of _mergesort_ — _mergesort_(0, 4), which will check that the array is sorted and then end. If _a_ = {2, 1, 3}, then the number of calls is 3: first of all, you call _mergesort_(0, 3), which then sets _mid_ = 1 and calls _mergesort_(0, 1) and _mergesort_(1, 3), which do not perform any recursive calls because segments (0, 1) and (1, 3) are sorted.
Ivan has implemented the program that counts the number of _mergesort_ calls, but now he needs to test it. To do this, he needs to find an array _a_ such that _a_ is a permutation of size _n_ (that is, the number of elements in _a_ is _n_, and every integer number from \[1, _n_\] can be found in this array), and the number of _mergesort_ calls when sorting the array is exactly _k_.
Help Ivan to find an array he wants!
## Input
The first line contains two numbers _n_ and _k_ (1 ≤ _n_ ≤ 100000, 1 ≤ _k_ ≤ 200000) — the size of a desired permutation and the number of _mergesort_ calls required to sort it.
## Output
If a permutation of size _n_ such that there will be exactly _k_ calls of _mergesort_ while sorting it doesn't exist, output - 1. Otherwise output _n_ integer numbers _a_\[0\], _a_\[1\], ..., _a_\[_n_ - 1\] — the elements of a permutation that would meet the required conditions. If there are multiple answers, print any of them.
[samples]
归并排序是一种著名的排序算法。用于对数组 #cf_span[a] 中下标在 #cf_span[[l, r) 范围内的元素进行排序的主函数可以如下实现：
本题中的数组是 #cf_span[0]-索引的，因此要对整个数组排序，你需要调用 #cf_span[mergesort(a, 0, n)]。
函数 #cf_span[mergesort] 的调用次数非常重要，因此 Ivan 决定在排序过程中统计该次数。例如，如果 #cf_span[a = {1, 2, 3, 4}]，则只会发生 #cf_span[1] 次 #cf_span[mergesort] 调用——即 #cf_span[mergesort(0, 4)]，它会检查数组是否已排序，然后结束。如果 #cf_span[a = {2, 1, 3}]，则调用次数为 #cf_span[3]：首先调用 #cf_span[mergesort(0, 3)]，它将设置 #cf_span[mid = 1] 并调用 #cf_span[mergesort(0, 1)] 和 #cf_span[mergesort(1, 3)]，而这两个调用不会进行任何递归调用，因为区间 #cf_span[(0, 1)] 和 #cf_span[(1, 3)] 已经有序。
Ivan 实现了一个统计 #cf_span[mergesort] 调用次数的程序，但现在他需要测试它。为此，他需要找到一个数组 #cf_span[a]，使得 #cf_span[a] 是一个大小为 #cf_span[n] 的排列（即，#cf_span[a] 中的元素个数为 #cf_span[n]，且区间 #cf_span[[1, n]] 中的每个整数都恰好出现一次），并且在对该数组进行排序时，#cf_span[mergesort] 的调用次数恰好为 #cf_span[k]。
请帮助 Ivan 找到他想要的数组！
第一行包含两个数 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ n ≤ 100000]，#cf_span[1 ≤ k ≤ 200000]）——所需排列的大小和排序时所需的 #cf_span[mergesort] 调用次数。
如果不存在一个大小为 #cf_span[n] 的排列，使得排序时恰好发生 #cf_span[k] 次 #cf_span[mergesort] 调用，则输出 #cf_span[ - 1]。否则，请输出 #cf_span[n] 个整数 #cf_span[a[0], a[1], ..., a[n - 1]]——满足条件的排列的元素。如果有多个答案，输出任意一个即可。
## Input
第一行包含两个数 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ n ≤ 100000]，#cf_span[1 ≤ k ≤ 200000]）——所需排列的大小和排序时所需的 #cf_span[mergesort] 调用次数。
## Output
如果不存在一个大小为 #cf_span[n] 的排列，使得排序时恰好发生 #cf_span[k] 次 #cf_span[mergesort] 调用，则输出 #cf_span[ - 1]。否则，请输出 #cf_span[n] 个整数 #cf_span[a[0], a[1], ..., a[n - 1]]——满足条件的排列的元素。如果有多个答案，输出任意一个即可。
[samples]
**Definitions**
Let $ n, k \in \mathbb{Z}^+ $ with $ 1 \leq n \leq 100000 $, $ 1 \leq k \leq 200000 $.
Let $ a = (a_0, a_1, \dots, a_{n-1}) $ be a permutation of $ \{1, 2, \dots, n\} $.
**Constraints**
The number of calls to `mergesort(l, r)` during the execution of `mergesort(a, 0, n)` must equal $ k $.
Each call `mergesort(l, r)` with $ r - l > 1 $ triggers two recursive calls: `mergesort(l, mid)` and `mergesort(mid, r)`, where $ \text{mid} = \lfloor (l + r)/2 \rfloor $.
A call `mergesort(l, r)` is counted if $ r - l \geq 1 $.
The total number of calls equals the number of nodes in the recursion tree rooted at $ (0, n) $, where each internal node (with $ r - l > 1 $) has two children, and leaves correspond to intervals of length $ \leq 1 $.
**Objective**
Find a permutation $ a $ of $ \{1, 2, \dots, n\} $ such that the recursion tree of `mergesort(a, 0, n)` has exactly $ k $ nodes.
If no such permutation exists, output $ -1 $.
API Response (JSON)
{
"problem": {
"name": "D. Merge Sort",
"description": {
"content": "Merge sort is a well-known sorting algorithm. The main function that sorts the elements of array _a_ with indices from \\[_l_, _r_) can be implemented as follows: 1. If the segment \\[_l_, _r_) is alr",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF873D"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Merge sort is a well-known sorting algorithm. The main function that sorts the elements of array _a_ with indices from \\[_l_, _r_) can be implemented as follows:\n\n1. If the segment \\[_l_, _r_) is alr...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "归并排序是一种著名的排序算法。用于对数组 #cf_span[a] 中下标在 #cf_span[[l, r) 范围内的元素进行排序的主函数可以如下实现：\n\n本题中的数组是 #cf_span[0]-索引的，因此要对整个数组排序，你需要调用 #cf_span[mergesort(a, 0, n)]。\n\n函数 #cf_span[mergesort] 的调用次数非常重要，因此 Ivan 决定在排序过程中统计...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n, k \\in \\mathbb{Z}^+ $ with $ 1 \\leq n \\leq 100000 $, $ 1 \\leq k \\leq 200000 $. \nLet $ a = (a_0, a_1, \\dots, a_{n-1}) $ be a permutation of $ \\{1, 2, \\dots, n\\} $. \n\n**Const...",
"is_translate": false,
"language": "Formal"
}
]
}