AT_agc002_c [AGC002C] Knot Puzzle

题目描述

你有 $N$ 根绳子,编号为 $1$ 到 $N$。第 $i$ 根绳子的长度是 $a_i$。 初始时,所有绳子都依次连在一起($1$ 连 $2$,$2$ 连 $3$……)。共有 $N-1$ 个绳结。连接第 $i$ 根绳子和第 $i+1$ 根绳子的结编号为 $i$。 Snuke 想要解开所有的结,他会重复以下操作: - 选择一根总长度至少为 $L$ 的(连在一起的)绳子,然后解开其中的一个结。 是否能通过合理操作解开所有 $N-1$ 个结?如果可以输出 `Possible` 并给出构造方案,否则输出 `Impossible` 表示无解。

输入格式

输入的第一行包含两个正整数 $N$ 和 $L$。 输入的第二行包含 $N$ 个正整数 $a_1,a_2,\dots,a_n$。分别表示各个绳子的长度。

输出格式

第一行输出 `Possible` 或 `Impossibe` 表示是否有解或无解。 若有解,则再输出另外 $N-1$ 行,第 $j$ 行表示第 $j$ 次操作中解开的结的编号。注意连接第 $i$ 根绳子和第 $i+1$ 根绳子的结编号为 $i$。

说明/提示

## 数据范围 - $2\le N \le10^5$ - $1 \le L \le10^9$ - $1 \le a_i \le 10^9$ - 所有输入均为整数。 ## 重要提示 本题没有 Special Judge,可能正确的构造在测评姬上会显示 WA。具体如何通过本题数据见题解。 由 [wjyppm1403](https://www.luogu.com.cn/user/578829) 翻译。