Problem:


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 ... 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

5 50
10 20 30 40 50

Sample Output 3

Possible
1
2
3
4

Another example of a possible solution is 3, 4, 1, 2.



Sample input:
3 50
30 20 10


Sample output:
Possible
2
1

Submission status: Accepted

Solution code:
N,L=list(map(int,input().split()))
A=list(map(int,input().split()))


def find():
    for i in range(N-1):
        if A[i]+A[i+1] >=L:
            return i
    return False

n=find()
if n is False:
    print('Impossible')
    exit(0)

n+=1
print('Possible')
for i in range(1,n):
    print(i)
for i in range(N-1,n,-1):
    print(i)
print(n)

Submission status: Runtime Error

Solution code:
import sys
K=10**10
N,L=map(int,input().split())
T=list(map(int,input().split()))
for i in range(N-1):
  if T[i]+T[i+1]>=L:
    K=i
    print("Possible")
    break
if K==10**10:
  print("Impossible")
K=K+1
R=list(range(1,K))
R.extend(list(range(K+1,N)))
R.append(K)
R=list(map(str,R))
for i in range(N-1):
  print(R[i])

Submission status: Runtime Error

Solution code:
N,L=map(int,input().split())
T=list(map(int,input().split()))
for i in range(N-1):
  if T[i]+T[i+1]>=L:
    K=i
    break
K=K+1
R=list(range(1,K))
R.extend(list(range(K+1,N)))
R.append(K)
R=list(map(str,R))
print(" ".join(R))

Submission status: Runtime Error

Solution code:
n,l = map(int,input().split())
A = list(map(int,input().split()))
x = -1
for i in range(n-1):
  if a[i]+a[i+1] >= l:
    x = i
    break
if x == -1:
  print('Impossible')
else:
  print('Possible')
  for i in range(x-1):
    print(i+1)
  for i in range(n-1,x,-1):
    print(i)
  print(x)

Submission status: Runtime Error

Solution code:
import numpy as np
n,l=map(int,input().split())
a=list(map(int,input().split()))
flag=False;idx=0
for i in range(n-1):
  if a[i]+a[i+1]>=l:
    flag=True
    idx=i
if not Flag:
  print("Impossible")
  exit(0)
print("Possible")
for x in range(idx):
  print(x+1)
for x in reversed(range(idx+1)):
  print(x+1)

Submission status: Runtime Error

Solution code:
n,l=map(int,input().split())
a=list(map(int, input().split()))
for i in range(n-1):
  if a[i]+a[i+1]>=L:
    print("Possible")
    for j in range(i):print(j+1)
    for j in range(n-1,i,-1):print(i)
    exit()
print("Impossible")

Submission status: Runtime Error

Solution code:
N, L = map(int, input().split())
A = list(map(int, input().split()))
b = [0] * (N - 1)
c = N - 1
pos = 1
for i in range(N - 1):
    l = A[i] + A[i + 1]
    if l >= L:
        j = i
        b[j] = c
        c -= 1
        break
else:
    pos = 0
    print('Impossible')
if pos:
    for i in range(j - 1, -1, -1):
        b[i] = c
        c -= 1
    for i in range(N, j, -1):
        b[i] = c
        c -= 1
    print('Possible')
    for ans in b:
        print(ans)

Submission status: Runtime Error

Solution code:
N, L = map(int, input().split())
A = list(map(int, input().split()))
b = [0] * (N - 1)
c = N - 1
pos = 1
for i in range(N - 1):
    l = A[i] + A[i + 1]
    if l >= L:
        j = i
        b[j] = c
        c -= 1
        break
else:
    pos = 0
    print('Impossible')
if pos:
    for i in range(j - 1, -1, -1):
        b[i] = c
        c -= 1
    for i in range(N - 1, j + 1, -1):
        b[i] = c
        c -= 1
    print('Possible')
    for ans in b:
        print(ans)

Submission status: Runtime Error

Solution code:
n,l=map(int,input().split())
A=list(map(int,input().split()))
A=list([i+1,A[i]] for i in range(n))
cnt,cnt_list=0,[]
ans=[]
for x,y in A:
    cnt +=y
    cnt_list.append(x)
    if x==n:cnt_list.pop()
    if cnt>=l:
        ans.append(cnt_list.pop())
        for i in cnt_list:
            ans.append(i)
        cnt=0
        cnt_list=[]

if len(ans)==n-1:
    print("Possible")
    for i in ans:print(i)
else:print("Impossible")

Submission status: Runtime Error

Solution code:
from collections import deque
N, L = map(int, input().split())
c = list(map(int, input().split()))
for i in range(len(c)-1):
  if c[i] + c[i+1] >= L:
    pos = i + 1
    break
else:
  print("Impossible")
  
for i in range(1,pos):
  print(i)
for i in range(len(c) -1, pos, -1):
  print(i)

Submission status: Runtime Error

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n,l=LI()
  a=LI()

  sm=sum(a)
  
  ans=[]
  _i=0
  f=False
  for i,x in enumerate(a[:-2]):
    if sm-x<l:
      _i=i
      f=True
      break
    ans.append(i+1)
    sm-=x
  # print(sm,_i)
  # print(a[_i:][::-1])

  if f:
    for i,x in enumerate(a[_i:][::-1][:-2]):
      # print(sm,x,l)
      if sm-x<l:
        print('Impossible')
        exit()
      ans.append(n-(i+1))
      sm-=x

  if sm<l:
    print('Impossible')
    exit()
  if f:
    ans.append(ans[-1]-1)
  else:
    ans.append(ans[-1]+1)

  print('Possible')
  for x in ans:
    print(x)

main()
# print(main())

Submission status: Runtime Error

Solution code:
N, L = map(int, input().split())

A = list(map(int, input().split()))

ans_index = -1
for i in range(N-1):
    if A[i] + A[i+1] >= L:
        ans_index = i
        break

if ans_index == -1:
    print('Impossible')
    exit()
print('Possible')

ans_index += 1
for i in range(1, ans_index):
    print(i)
for i in range(N-1, n, -1):
    print(i)

print(ans_index)

Submission status: Runtime Error

Solution code:
N, L = map(int, input().split())

A = list(map(int, input().split()))

ans_index = -1
for i in range(N-1):
    if A[i] + A[i+1] >= L:
        ans_index = i
        break

ans = list(range(1, i)).extend(list(i+1, N-1)).append(ans_index)

if ans_index == -1:
    print('Impossible')
else:
    for i in range(len(ans)):
        print('Possible')
        print(ans[i])

Submission status: Runtime Error

Solution code:
from collections import Counter,defaultdict
import sys,heapq,bisect,math,itertools,string,queue
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,l = inpl()
a = inpl()
aa = []
for i in range(1,n):
    aa.append([i,a[i-1] + a[i]])
# print(aa)
if n == 2: 
    if a[0] + a[1] < l:
        print('Impossible')
    else:
        print('Possible')
        print(1)
elif n == 3:
    if aa[0][1] < l and aa[1][1] < l:
            print('Impossible')
    else:
        aa.sort(key=lambda x:x[1])
        print('Possible')
        for i in range(n-1):
            print(aa[i][0])
else:
    for i in range(1,n-1):
        if aa[i-1][1] < l and aa[i][1] < l and aa[i+1][1] < l:
            print('Impossible')
            break
    else:
        aa.sort(key=lambda x:x[1])
        print('Possible')
        for i in range(n-1):
            print(aa[i][0])

Submission status: Runtime Error

Solution code:
def resolve():
    n, l = map(int, input().split())
    a = list(map(int, input().split()))
    for i in range(n):
        if a[i] + a[i + 1] >= l:
            last = i
            print("Possible")
            for j in range(last):
                print(i)
            for j in range(last + 1, n):
                print(i)
            print(last)
            return 0
    print("Impossible")
    return 0


if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionimit(200000)
n,l=map(int,input().split())
r=list(map(int,input().split()))
last=0;tiepoint=0
for i in range(n-1):
  if r[i]+r[i+1]>last:
    last=r[i]+r[i+1]
    tiepoint=i
if last>=l:
  print("Possible")
  for i in range(tiepoint-1):
    print(i+1)
  for i in range(tiepoint+1,n)[::-1]:
      print(i+1)
  print(tiepoint+1)
else:print("Impossible")

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionimit(200000)
n,l=map(int,input().split())
r=list(map(int,input().split()))
last=0;tiepoint=0
for i in range(n-1):
  if r[i]+r[i+1]>last:
    last=r[i]+r[i+1]
    tiepoint=i
if last>=l:
  print("Possible")
  for i in range(n-1):
    if i==tiepoint:continue
    print(i+1)
  print(tiepoint+1)
else:print("Impossible")

Submission status: Runtime Error

Solution code:
n,l=map(int,input().split())
r=list(map(int,input().split()))
last=0;tiepoint=0
for i in range(n-1):
  if r[i]+r[i+1]>last:
    last=r[i]+r[i+1]
    tiepoint=i
if last>=l:print("Possible")
  for i in range(n):
    if i==tiepoint:continue
    print(i)
else:print("Impossible")

Submission status: Runtime Error

Solution code:
N, L, *A = map(int, open(0).read().split())

k = -1
for i in range(N - 1):
    if A[i] + A[i + 1] >= L:
        k = i + 1
        break

if k == -1:
    print("Impossible")
else:
    print("Possible", *range(1, k), *range(N - 1, k, -1), k, sep="\n")

Submission status: Runtime Error

Solution code:
N,L = map(int,input().split())
*A, = map(int,input().split())

S = [0]*(N+1)
for i,a in enumerate(A): S[i+1] = S[i] + a
ans = []
i=0
j=N-1
while i<j:
    if S[j+1]-S[i] < L:
        1/0
        print("Impossible")
        break
    if A[i] <= A[j]:
        ans.append(i+1)
        i+=1
    else:
        ans.append(j)
        j-=1
else:
    print("Possible")
    for a in ans: print(a)

Submission status: Runtime Error

Solution code:
n,l=map(int,input().split())
arr=list(map(int,input().split()))
pos=0
tmp=0
for i in range(n-1):
  if (arr[i]+arr[i+1])>tmp:
    pos=i
    tmp=(arr[i]+arr[i+1])
if tmp<l:
  print('Impossible')
else:
  print('Possible')
  ans=[]
  for i in range(pos):
    ans.append(i+1)
  for i in range(n,pos+1):
    ans.append(i)
  ans.append(pos+1)
  for i in range(n-1):
    print(ans[i])

Submission status: Runtime Error

Solution code:
import sys
from collections import deque
import copy
import math
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline


def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, L] = [int(input_raw[0]), int(input_raw[1])]
    input_raw = read_func().strip().split()
    A = [int(input_raw[i]) for i in range(N)]
    B = deque([A[i] + A[i + 1] for i in range(N - 1)])
    sumA = sum(A)
    s_idx = 1
    t_idx = len(B)
    seq = []
    for i in range(N - 1):
        if sumA < L:
            print "Impossible"
            return
        if B[len(B) - 1] < L:
            B.pop()
            sumA -= A[t_idx]
            seq.append(t_idx)
            t_idx += 1

        else :
            B.popleft()
            sumA -= A[s_idx - 1]
            seq.append(s_idx)
            s_idx += 1
        if len(seq) == N - 1:
            break

    print "Possible"
    for i in range(len(seq)):
        print seq[i]





if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N, L = (int(i) for i in input().split())
a = [int(i) for i in input().split()]
P = "Possible"
for i in range(N-1):
  if a[i] + a[i+1] >= L:
    start = i
    break  
else:
  P = "Impossible"

ans = [start]
if start > 0:
  ans += list(range(start))
if start != N-2:
  ans += reversed(list(range(start+1, N-1)))

ans.reverse()
print(P)
if P == "Possible":
  for a in ans:
    print(a+1)

Submission status: Runtime Error

Solution code:
n,l = map(int,input().split())
a = map(int,input().split())
a.sort()
if a[n - 1] + a[n - 2] >= l:
  print("Possible")
else:
  print("Impossible")

Submission status: Runtime Error

Solution code:
N, L = map(int, input().split())
a = list(map(int, input().split()))
end = 0
for i in range(N - 1):
    if a[i] + a[i + 1] >= L:
        end = i + 1
        break
else:
    print('Impossible')
    exit()

print('Possible')
print(*range(1, end), *reversed(range(end, N)), sep='\n')

Submission status: Runtime Error

Solution code:
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
[n,l]=i2()
a=i2()
s=[a[0]]
b=[]
d=[]
for i in range(1,n):
 s.append(s[-1]+a[i])
 if a[i-1]+a[i]<l:
    b.append(i)
 else:
    d.append(i)
c=0
if not n-1 in b:
  if s[-1]-s[b[-1]-1]>=l:
       c+=1

if s[b[0]-1]>=l:
       c+=1

for i in range(len(b)-1):
    if s[b[i+1]-1]-s[b[i]-1]>=l:
       c+=1
if len(b)>c:
 print("Impossible")
else:
 print("Possible")
 for i in b:
   print(i)
 for i in d:
   print(i)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;

int n, l;
vector<int> a;

int length(int x, int y)
{
    return a[y] - (x > 0 ? a[x - 1] : 0);
}

int dp[10001][10001] = {};
int search(int x, int y)
{
    if (x == y) {
        return -1;
    }

    if (dp[x][y] == 0) {
        if (length(x, y) < l) {
            dp[x][y] = -2;
        } else {
            for (int cut = x; cut < y; ++cut) {
                if (search(x, cut) != -2 && search(cut + 1, y) != -2) {
                    dp[x][y] = cut + 1;
                }
            }
        }
    }

    return dp[x][y];
}

int main()
{
    cin >> n >> l;

    for (int i = 0, t, acc = 0; i < n; ++i) {
        cin >> t;
        acc += t;
        a.push_back(acc);
    }

    if (search(0, n - 1) == -2) {
        cout << "Impossible" << endl;
    } else {
        cout << "Possible" << endl;

        queue<pair<int, int> > q;
        q.push(make_pair(0, n - 1));
        while (!q.empty()) {
            pair<int, int> xy = q.front();
            q.pop();
            if (xy.first != xy.second) {
                int cut = search(xy.first, xy.second);
                cout << cut << endl;
                q.push(make_pair(xy.first, cut - 1));
                q.push(make_pair(cut, xy.second));
            }
        }
    }

    return 0;
}

Submission status: Runtime Error

Solution code:
N, L = map(int, input().split())
a = [map(int, input().split())]
b = 0
c = 0
for i in range(N-1):
	if a[i] + a[i+1] >= L:
		print("Possible")
		b = 1
		c = i
		break
else:
	print("Impossible")
if b = 1:
	for i in range(c+1):
		print(i+1)
	for i in range(N, c+1, -1):
		print(i+1)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
x = []
y = []
for i in range(1,M+1):
	z = list(map(int,input().split()))
	x.append(z[0])
	y.append(z[1])
a = [0]
b = [1]*N
for i in range(M):
	b[x[i]-1] -= 1
	b[y[i]-1] += 1
	if x[i]-1 in a:
		a.append(y[i]-1)
		if b[x[i]-1] == 0:
			a.remove(x[i]-1)
c = 0
for i in range(len(a)):
	if b[a[i]] != 0:
		c += 1
print(c)