QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 256 MB Total points: 100

# 6229. 排列

统计

有一个 $n$ 阶排列 $p$,其前 $k$ 位 $p_1, p_2, \dots, p_k$ 已经确定了。

定义排列 $p$ 中,$[l, r]$ 是一个值域连续段当且仅当:

$$ \max(p_l, p_{l+1}, \dots, p_r) - \min(p_l, p_{l+1}, \dots, p_r) = r-l $$

$p$ 中值域连续段个数即所有 $1\le l\le r\le n$ 中值域连续段的总数。

请你求出:所有可能的排列 $p$ 中,值域连续段个数的最大值,以及任意一种方案。

输入格式

第一行两个整数 $n,k$,分别表示排列的阶数和以及确定的位数。

接下来一行由空格分隔的 $k$ 个正整数 $p_1, p_2, \dots, p_k$,表示排列已知的部分。($k=0$ 则此行为空)

输出格式

输出第一行一个整数表示值域连续段个数的最大值。

第二行 $n$ 个正整数表示任意一种方案。

样例数据

样例输入

4 1
2

样例输出

8
2 1 3 4

样例解释

最优解为 $2,1,3,4$,有 $8$ 个值域连续段($[1], [2], [3], [4], [1,2], [3,4], [1,3], [1,4]$)。$2, 3, 4, 1$ 为另一个最优解。

子任务

对于所有数据,$1\le n\le 2\times 10^5, 0\le k\le n$。

  • 对于 $10\%$ 的数据,$n\le 10$;
  • 对于另外 $20\%$ 的数据,$n\le 22$;
  • 对于另外 $10\%$ 的数据,$k\le 1$;
  • 对于另外 $20\%$ 的数据,$k = n$;
  • 对于余下 $40\%$ 的数据,无特殊限制。