『AGC 002C』Knot Puzzle

Problem

Time limit : 2sec / Memory limit : 256MB

Problem Statement

We have $N$ pieces of ropes, numbered 1 through $N$. The length of piece $i$ is $a_i$.

At first, for each $i(1≤i≤N−1)$, piece $i$ and piece $i+1$ are tied at the ends, forming one long rope with $N-1$ knots. Snuke will try to untie all of the knots by performing the following operation repeatedly:

• Choose a (connected) rope with a total length of at least $L$, then untie one of its knots.

Is it possible to untie all of the $N−1$ knots by properly applying this operation? If the answer is positive, find one possible order to untie the knots.

Constraints

• $2≤N≤10^5$
• $1≤L≤10^9$
• $1≤a_i≤10^9$
• All input values are integers.

---

Input

The input is given from Standard Input in the following format:

$N\ L$
$a_1\ a_2\ \dots\ a_n$

Output

If it is not possible to untie all of the $N−1$ knots, print Impossible.

If it is possible to untie all of the knots, print Possible, then print another $N−1​$ lines that describe a possible order to untie the knots. The $j​$-th of those $N−1​$ lines should contain the index of the knot that is untied in the $j​$-th operation. Here, the index of the knot connecting piece $i​$ and piece $i+1​$ is $i​$.

If there is more than one solution, output any.

Sample Input 1

3 50 30 20 10

Sample Output 1

Possible 2 1

If the knot 1 is untied first, the knot 2 will become impossible to untie.

Sample Input 2

2 21 10 10

Sample Output 2

Impossible

Sample Input 3

Possible 5 50 10 20 30 40 50

Sample Output 3

Possible 1 2 3 4

Solution

这题的充分必要条件就是有两段绳子的长度$\geq L$

必要性证明：不断删绳子总归会删到只有一个结的情况，如果没有两段相邻的绳子的长度$\geq L$那么肯定删不下去

充分性证明：一旦出现了满足题意的两段相邻的绳子，我们可以从左边和右边分别从头删，这样肯定长度不会小于$L$

Code:

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
inline void _read(int &x)
{
	x = 0;
	char t = getchar();
	while (!isdigit(t)) t = getchar();
	while (isdigit(t))
	{
		x = x * 10 + t - '0';
		t = getchar();
	}
}
int N, L, lstlength = 0;
int main(int argc, char **Argv)
{
	_read(N), _read(L);
	for (register int i = 0, x; i < N; ++i)
	{
		_read(x);
		if (i == 0)
		{
			lstlength = x;
			continue;
		}
		if (x + lstlength >= L)
		{
			puts("Possible");
			for (register int j = 0; j < i - 1; ++j)
				printf("%d", j + 1), puts("");
			for (register int j = N - 2; j > i - 1; --j)
				printf("%d", j + 1), puts("");
			return 0;
		}
		lstlength = x;
	}
	puts("Impossible");
	return 0;
}