201402: [AtCoder]ARC140 C - ABS Permutation (LIS ver.)

Memory Limit:1024 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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.

Input

题意翻译

给定 $m,n$,希望一个长度为 $m$ 并且以 $n$ 开头的排列 $a$ 满足以下条件:令其差分数组的绝对值数列是 $b$(即 $b_i=|a_{i+1}-a_i|$),希望最大化 $b$ 的最长严格上升子序列的长度。如果有多个 $a$ 符合条件,输出一个即可。

加入题单

上一题 下一题 算法标签: