/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
(1,\dots,N) の順列 P=(P_1,P_2,\ldots,P_N) の嬉しさを以下で定義します。
- 長さ N-1 の数列 A=(A_1,A_2,\ldots,A_{N-1}) を、A_i = |P_i-P_{i+1}|(1\leq i \leq N-1) で定める。 A の最長狭義単調増加部分列の長さを P の嬉しさとする。
P_1 = X を満たす順列 P のうち、嬉しさが最大になるものを一つ出力してください。
制約
- 2 \leq N \leq 2\times 10^5
- 1 \leq X \leq N
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N X
出力
P_1 = X を満たす順列 P のうち、嬉しさが最大になるものを 1 つ以下の形式で出力せよ。
P_1 P_2 \ldots P_N
条件を満たす解が複数存在する場合、どれを出力しても正解とみなされる。
入力例 1
3 2
出力例 1
2 1 3
A=(1,2) となるので、P の嬉しさは 2 です。これが達成可能な嬉しさの最大であるため、出力は条件を満たします。
入力例 2
3 1
出力例 2
1 2 3
A=(1,1) となるので、P の嬉しさは 1 です。これが達成可能な嬉しさの最大であるため、出力は条件を満たします。
Score : 500 points
Problem Statement
The happiness of a permutation P=(P_1,P_2,\ldots,P_N) of (1,\dots,N) is defined as follows.
- Let A=(A_1,A_2,\ldots,A_{N-1}) be a sequence of length N-1 with A_i = |P_i-P_{i+1}|(1\leq i \leq N-1). The happiness of P is the length of a longest strictly increasing subsequence of A.
Print a permutation P such that P_1 = X with the greatest happiness.
Constraints
- 2 \leq N \leq 2\times 10^5
- 1 \leq X \leq N
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N X
Output
Print a permutation P such that P_1 = X with the greatest happiness, in the following format:
P_1 P_2 \ldots P_N
If there are multiple solutions, printing any of them will be accepted.
Sample Input 1
3 2
Sample Output 1
2 1 3
Since A=(1,2), the happiness of P is 2, which is the greatest happiness achievable, so the output meets the requirement.
Sample Input 2
3 1
Sample Output 2
1 2 3
Since A=(1,1), the happiness of P is 1, which is the greatest happiness achievable, so the output meets the requirement.