No.2771 Personal Space
タグ : / 解いたユーザー数 49
作問者 :
srjywrdnprkt
/ テスター :
👑 Problem Statement
$N$ chairs numbered $1, 2, \cdots ,N$ are arranged in this order in $1$ row from left to right. $N$ people numbered $1, 2, \cdots, N$ sit down on these chairs in this order.
Let $c_j$ be the number of the chair on which person $j$ has sat. Person $i~(i\geq 2)$ sits on the chair with the smallest number among the chairs $x$ that maximize the distance from others $\displaystyle \min_{1\leq j\leq i-1} |x-c_j|$.
Given that person $1$ sits on chair $M$, find the numbers of the people sitting on chairs $1, 2, \cdots, N$.
You are given $T$ test cases; find the answer for each of them.
Input
$T$ $\rm case_1$ $\vdots$ $\rm case_T$Here, $\rm case_i$ is the $i$-th test case. Each test case is given in the following format.
$N\ M$
All inputs are integers and satisfy the following constraints.
- $1\leq T$
- $2\leq N$
- $1 \leq M \leq N$
- For the test cases contained in $1$ input, the sum of their $N$ does not exceed $3\times 10^5$.
Output
For each test case, letting $p_i$ be the number of the person sitting on chair $i$, print $p_1, p_2, \cdots, p_N$ in this order on one line, separated by spaces.
Print $T$ lines; on the $i$-th line, print the answer for the $i$-th test case.
Sample
Sample 1
Input
4 5 3 5 1 2 1 10 3
Output
2 4 1 5 3 1 4 3 5 2 1 2 4 6 1 7 8 3 9 5 10 2
Consider test case number $1$.
First, person $1$ sits on chair $3$. Next, consider the number of the chair on which person $2$ sits.
At this point, the distances from others of chairs $1, 2, 4, 5$ are $2,1,1,2$, respectively. There are $2$ chairs that maximize the distance from others, $1$ and $5$, and person $2$ sits on chair $1$, which has the smaller number of these.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。