Problem:


Score : 400 points

Problem Statement

Snuke has an empty sequence a.

He will perform N operations on this sequence.

In the i-th operation, he chooses an integer j satisfying 1 \leq j \leq i, and insert j at position j in a (the beginning is position 1).

You are given a sequence b of length N. Determine if it is possible that a is equal to b after N operations. If it is, show one possible sequence of operations that achieves it.

Constraints

All values in input are integers.

1 \leq N \leq 100

1 \leq b_i \leq N

Input

Input is given from Standard Input in the following format:

N
b_1 \dots b_N

Output

If there is no sequence of N operations after which a would be equal to b, print -1.
If there is, print N lines. In the i-th line, the integer chosen in the i-th operation should be printed. If there are multiple solutions, any of them is accepted.

Sample Input 1

3
1 2 1

Sample Output 1

1
1
2

In this sequence of operations, the sequence a changes as follows:

After the first operation: (1)

After the second operation: (1,1)

After the third operation: (1,2,1)

Sample Input 2

2
2 2

Sample Output 2

-1

2 cannot be inserted at the beginning of the sequence, so this is impossible.

Sample Input 3

9
1 1 1 2 2 1 2 3 2

Sample Output 3

1
2
2
3
1
2
2
1
1



Sample input:
3
1 2 1


Sample output:
1
1
2

Submission status: Runtime Error

Solution code:
from collections import deque
def main():
    n = int(input())
    b = np.array(list(map(int, input().split())))
    s = set()
    q = deque()

    q.append([tuple(b), [0]*n, 0])
    ans = None
    while q:
        now, history, depth = q.popleft()
        if now in s:
            continue
        s.add(now)
        if len(now) == 0:
            ans = history
            break
        for i, j in enumerate(now):
            if i+1 == j:
                tmp = history[::]
                tmp[depth] = i+1
                q.appendleft([tuple(now[:i] + now[i+1:]), tmp, depth+1])
    if ans is None:
        print(-1)
    else:
        for i in ans[::-1]:
            if i == 0:
                break
            print(i)
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
n=int(input())
b=list(map(int,input().split()))
s_b=sorted(list(set(b)),reverse=True)
ans=[]
for itr in range(n):
  for j in s_b:
    if len(b)>=j:
      if b[j-1]==j:
        b=b[:j-1]+b[j:]
        ans.append(j)
        break
    if j==1:
      print(-1)
      exit()
for i in range(n):
  print(ans[i])

Submission status: Runtime Error

Solution code:
n = int(input())

b = [int(item) for item in input().split()]

def dfs(b_sub, ans):
  if len(b_sub) == 0:
    for a in ans[::-1]:
      print(a)
    return 0
  takeable = []
  for i, item in enumerate(b_sub):
    if i+1 == item:
      takeable.append(i)
  if len(takeable) == 0:
    print(-1)
    return -1
  for item in takeable[::-1]:
    tmp = b_sub
    taken = tmp.pop(item)
    ans.append(taken)
    dfs(tmp, ans)
  
print(dfs(b, []))

Submission status: Runtime Error

Solution code:
length = int(input())
progression = list(map(int,input().split()))
N = 0
submit_array = []

def error_case():
  print(-1)

if progression[0] == 1:
  one_count = progression.count(1)
  element_num = [i for i, x in enumerate(progression) if x == 1]
  element_max = max(element_num)
  ushiro = progression[element_max:]
  ushiro.pop(0)
  print(ushiro)
  tsugi = progression[]
  while N < length:
    if N == 0:
      submit_array.append(1)
    if N == 1:
      if 2 in ushiro:
        submit_array.append(2)
      else:
        submit_array.append(1)
    two_num = [i for i, x in enumerate(progression) if x == 2]
    three_num = [i for i, x in enumerate(progression) if x == 3]
    if N == 2:
      if two_num>=2:
        submit_array.append(2)
      else:
        if 3 in ushiro:
          submit_array.append(3)
        else:
          submit_array.append(1)
    if N == 3:
      if two_num>=3:
        submit_array.append(2)
      else:
        if three_num>=2:
          submit_array.append(3)
        else:
          if 4 in ushiro:
            submit_array.append(4)
          else:
            submit_array.append(1)
      
    if progression[N] > (N+1):
      error_case()
      break
    N+=1
    
else:
  error_case()

Submission status: Runtime Error

Solution code:
n = int(input())
list = []
a = []
for i in range(n):
  list.append(int(input))

for i in range(1, n):
  for j in range(1, i):
    if list[i] == j:
      a.insert(j, j)

if a == list:
  for i in range(n):
    print(list[i])
else:
  print(-1)

Submission status: Runtime Error

Solution code:
N = int(input())
b = list(map(int,input().split()))
ans = []
if b[0]!=1:
  print('-1')
else:
  for j in range(N):
    tmp = sorted(list(set(b)),reverse = True)
    for i in tmp:
      if i == b[i-1]:
        ans.insert(0,b[i-1])
        b.pop(i-1)
        break
  for k in range(N):
    print(ans[k])

Submission status: Runtime Error

Solution code:
def rightMinNumber(L):
    min = L[len(L)-1]
    min_index = len(L) - 1
    for i in range(len(L)-2,-1,-1):
        if L[i] < min:
            min = L[i]
            min_index = i
    a.append(min)
    if min_index+1 == len(L)-1 and min_index > 0:
        lL = L[:min_index]
        rightMinNumber(lL)
    elif min_index + 1 < len(L)-1:
        rL = L[min_index+1:]
        rightMinNumber(rL)

N = int(input())
B = [int(_) for _ in input().split()]
#出力
a = []
#Bのエンコーダを作る
x = 0

#Bの正当性を調べる。
for i in range(N):
    if B[i] > i+1:
        x = -1
        break
if x == -1:
    print(x)
else :
    rightMinNumber(B)
    for i in range(N):
        print(a[i])

Submission status: Runtime Error

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

ans = 0
for i in range(N):
    if 1 <= b[i] <= i+1:
        pass
    else:
        ans = -1

a = []
c = []
if ans == 0:
    k = 0
    flag = 0
    for i in range(1, N):
        if b[i] == 1 and flag == 0:
            a.append(sorted(b[:i]))
            flag = 1
            k = i
        elif b[i] == 1 and flag == 1:
            a.append(sorted(b[k:i]))
            k = i
    a.append(sorted(b[k:N]))
        
    for i in range(len(a)-1, -1, -1):
        for j in range(len(a[i])):
            c.append(a[i][j])

f = 1            
for i in range(N):
    if c[i] <= i+1:
        pass
    else:
        
        f = 0
        break

if f == 0:
    print(-1)
else:
    for i in range(N):
        print(c[i])

Submission status: Runtime Error

Solution code:
n=int(input())
b=input().split()
c=n
x=n
a=[]
while len(b)!=1 and b[0]=="1":
    while c>1:
        if b[x-1]==str(x):
            del b[x-1]
            a.append(int(x))
            c=c-1
            x=len(b)+1
            #print(a)
        x=x-1

if len(a)==n-1:
    print(1)
    for x in range(len(a)-1,-1,-1):
        print(a[x])
else:
    print(-1)

Submission status: Runtime Error

Solution code:
N = int(input())
b = input()

def func(a, n):
  if not a: return n
  for i in range(1, len(a)+1):
    if a[i-1] == i:
      func(a[:i-1]+a[i:], n+1)
  return -1

print(func(n, 0)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# -*- coding: utf-8 -*-

# -*- coding: utf-8 -*-

from sys import stdin

###########################################


############################################
#from sys import stdin
import numpy as np

# read data for n sequences.
n = stdin.readline().split()
data = stdin.readline().split()

out = []

token = 0

# check first data and return -1 if != 1
if int(data[0]) != 1:
    token = -1
else:    
# print first data
    out.append(1)

for i,x in enumerate(data):
    data[i]=int(x)
    
# split to multiple data.
x = 1
split = []
chunck = []
#while x < len(data):
for i,num in enumerate(data[x:]):
    chunck.append(num)
    if num == 1:
        split.append(chunck)
        chunck=[]
        x = i+1
split.append(chunck)

for x in reversed(split):
    maxnum=max(x)
    if x == [1]:
        out.append(1)
    else:
        for i in range(1,maxnum+1):
            if i in x:
                count = x.count(i)
                if x.index(i) >= i-2:
                    for xx in range(count):
                        out.append(i)
                else:
                    token = -1

if token == -1:
    print(-1)
else:
    # print outputs
    for x in out:
        print(x)

Submission status: Runtime Error

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

a=[]

for i in range(N):
  if i+1 < b[i]:
    a=[0]*1
    a[0]= -1
    break
  a.insert(b[i],b[i])

for j in range(N):
  print(a[j])

Submission status: Runtime Error

Solution code:
def rightMinNumber(L):
    min = L[len(L)-1]
    min_index = len(L) - 1
    for i in range(len(L)-2,-1,-1):
        if L[i] < min:
            min = L[i]
            min_index = i
    a.append(min)
    if min_index+1 == len(L) and min_index > 0:
        lL = L[:min_index]
        rightMinNumber(lL)
    elif min_index + 1 < len(L):
        rL = L[min_index+1:]
        rightMinNumber(rL)

N = int(input())
B = [int(_) for _ in input().split()]
#出力
a = []
#Bのエンコーダを作る
x = 0

#Bの正当性を調べる。
for i in range(N):
    if B[i] > i+1:
        x = -1
        break
if x == -1:
    print(x)
else :
    rightMinNumber(B)
    for i in range(N):
        print(a[i])

Submission status: Runtime Error

Solution code:
n = int(input())
listB = list(map(int, input().split()))
i = 1
if i == 1:
    listA = []
    index2 = len(listB)-1
    befI = len(listB)
    while index2 > -1:
        if listB[index2]!=1:
            pass
        else:
            if index2 != befI:
                newL = listB[index2:befI]
                newL.sort()
                listA.extend(newL)
                befI = index2
            else:
                listA.append(1)
        index2-=1
    listC = []
    index3=0
    while index3 < len(listA):
        if index3 == 0:
            if listA[index3] == 1:
                listC.append(listA[index3])
            else:
                listC.append(0)
        elif listA[index3] > index3+1:
            listC.append(0)
        else:
            if listA[index3]-1 <=  len(listC):
                listC.insert(listA[index3]-1, listA[index3])
            else:
                listC.append(0)
        index3+=1
    if index3 == len(listA):
        if listC == listB:
            for ans in listA:
                print(ans)
        else:
            print(a)

Submission status: Runtime Error

Solution code:
def solve(N, b):
    for i in range(N):
        if b[i] > i + 1:
            return -1
    ans = [None for _ in range(N)]
    for i in reversed(range(N)):
        min_j = b[i]
        max_j = N + b[i] - i - 1
        for j in reversed(range(min_j - 1, max_j)):
            if not ans[j]:
                ans[j] = b[i]
                break
    return ans


N = int(input())
b = list(map(int, input().split()))

for i in solve(N, b):
    print(i)

Submission status: Runtime Error

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

b_order = [-1]*N

def f():
    
    for i in range(N,0,-1):
        i_order = N - (i - b[i-1])

        while b_order[i_order - 1] != -1:
            i_order -= 1
            if i_order < 0:
                print(-1)
                return

        b_order[i_order - 1] = b[i-1]

    for i in b_order:
        print(i)

f()

Submission status: Runtime Error

Solution code:
N = int(input())
b_list = list(map(int,input().split()))
answer_list = []

for i in range(N):
    if b_list[i] > i+1:
        print(-1)
        break


    
    for j in range(N-i, 0, -1):
        
        if b_list[j-1] == j:
            answer_list.append(b_list[j-1])
            b_list.pop(j-1)
            
            break

answer_list.reverse()


for i in range(N):
    print(answer_list[i])

Submission status: Runtime Error

Solution code:
def rightMinNumber(L):
    min = L[len(L)-1]
    min_index = len(L) - 1
    for i in range(len(L)-2,-1,-1):
        if L[i] < min:
            min = L[i]
            min_index = i
    a.append(min)
    if min_index+1 == len(L) and min_index > 0:
        rightMinNumber(lL)
    elif min_index + 1 < len(L):
        rL = L[min_index+1:]
        rightMinNumber(rL)

N = int(input())
B = (int(i) for i in input().split())
#出力
a = []
#Bのエンコーダを作る
x = 0

#Bの正当性を調べる。
for i in range(N):
    if B[i] > i:
        x = -1
        break
if x == -1:
    print(x)
else :
    rightMinNumber(B)
    for i in range(N):
        print(a[i])

Submission status: Runtime Error

Solution code:
N = int(input())
b_list = list(map(int,input().split()))
answer_list = []

for i in range(N):
    if b_list[i] > i+1:
        print(-1)
        break

for i in range(N): 
    
    for j in range(N-i, 0, -1):
        
        if b_list[j-1] == j:
            answer_list.append(b_list[j-1])
            b_list.pop(j-1)
            
            break

answer_list.reverse()


for i in range(N):
    print(answer_list[i])

Submission status: Runtime Error

Solution code:
def remove(data):
    global result
    pos = min(len(data), max(data))
    for n in range(pos-1, -1, -1):
        if data[n] == n + 1:
            result.append(data.pop(n))
            #print('remove {0} '.format(n + 1), end='')
            if len(data) == 0:
                #print('OK')
                return True
            else:
                #print(data)
                if remove(data):
                    return True
    else:
        return False

_ = input()
B = list(map(int, input().split()))

result = []

if remove(B):
    result.reverse()
    for res in result:
        print(res)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
n=int(input())
b=list(map(int,input().split()))
if b[0]!=1:
    print(-1)
else:
    ans=[1]
    for j in range(len(b)-1):
        for i in range(len(b)-1,-1,-1):
            if i==0 and b[0]==1:
                ans+=[b.pop(i)]
                break
            if b[i]==i+1:
                ans+=[b.pop(i)]
                break                
if len(ans)!=n:  
    print(-1)
else:
    print(1)
    for i in range(n-1,0,-1):
        print(ans[i])

Submission status: Runtime Error

Solution code:
N = int(input())
B = list(map(int,input().split()))
TF = [False]*N
L = []
s = 0
lenstr = N-1
for i in range(N):
  cnt = 0
  tr = 0
  for j in range(N-1,-1,-1):
    if TF[j] == False:
      if B[lenstr-cnt-tr+i] == lenstr-cnt+1:
        TF[lenstr-cnt-tr+i] = True
        L.append(lenstr-cnt+1)
        lenstr -= 1
        break
      else:
        cnt += 1
    else:
      tr += 1
if len(L) == N:
  for i in range(N):
    print(L[N-i-1])
else:
  print(-1)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
Edge = [0] * N
for _ in range(M):
    a, b = map(int, input().split())
    Edge[a - 1] += 1
    Edge[b - 1] += 1
if any([i%2 == 1 for i in Edge]):
    print('No')
elif len([i for i in Edge if i > 4]) > 0:
    print('Yes')
elif len([i for i in Edge if i > 2]) > 1:
    print('Yes')
else:
    print('No')

Submission status: Runtime Error

Solution code:
def rightMinNumber(L):
    min = L[len(L)-1]
    min_index = len(L) - 1
    for i in range(len(L)-2,-1,-1):
        if L[i] < min:
            min = L[i]
            min_index = i
    lL = L[:min_index]
    rL = L[min_index+1:]
    a.append(min)
    rightMinNumber(rL)
    rightMinNumber(lL)


N = int(input())
B = (int(i) for i in input().split())
#出力
a = []
#Bのエンコーダを作る
x = 0

#Bの正当性を調べる。
for i in range(N):
    if B[i] > i:
        x = -1
        break
if x == -1:
    print(x)
else :
    rightMinNumber(B)
    for i in range(N):
        print(a[i])

Submission status: Runtime Error

Solution code:
9
1 1 1 2 2 1 2 3 2

Submission status: Runtime Error

Solution code:
def rightMinNumber(L):
    min = L[len(L)-1]
    min_index = len(L) - 1
    for i in range(len(L)-2,-1,-1):
        if L[i] < min:
            min = L[i]
            min_index = i
    lL = L[:min_index]
    rL = L[min_index+1:]
    a.append(min)
    rightMinNumber(rL)
    rightMinNumber(lL)


N = int(input())
B = (int(i) for i in input().split())
#出力
a = []
#Bのエンコーダを作る

#Bの正当性を調べる。
for i in range(N):
    if B[i] > i:
        x = -1
        break
if x == -1:
    print(x)
else :
    rightMinNumber(B)
    for i in range(N):
        print(a[i])

Submission status: Runtime Error

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


def naive():
    # (1), (1,2), ..., (1,...,N)
    import itertools
    candidates = itertools.product(*[range(1, i + 1) for i in range(1, N+1)])
    for candidate in candidates:
        a = list()
        for j in candidate:
            a.insert(j-1, j)

        if a == b:
            return candidate
    
    return -1


def fast():
    candidate = list()
    
    while len(b) != 0:
        for i in range(len(b))[::-1]:
            if b[i] == (i+1):
                value = b.pop(i)
                candidate.append(value)
                break
            
        else:
            return -1

    candidate.reverse()
    return candidate
 
# print(naive())
# print(fast())
ans_list = fast()
for ans in ans_list:
    print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
b = [int(x) for x in input().split()]
ans = []
while len(b) > 1:
    tmp = max(b)
    flag = 0
    while flag == 0:
        if b[tmp-1] == tmp: # 数字とインデックスが一致
            ans.append(b.pop(tmp-1))
            flag = 1
        else:
            tmp -= 1
        if tmp == 0:
            flag = -1
            break
    if flag == -1:
        ans = None
        break

if ans == None or b[0] != 1:
    print(-1)
else: 
    ans.append(1)
    for i in ans[::-1]:
        print(i)

Submission status: Runtime Error

Solution code:
length = int(input())
progression = list(map(int,input().split()))
N = 0
submit_array = []

if progression[0] != 1:
  one_count = progression.count(1)
  submit_array.append[1]
  element_num = [i for i, x in enumerate(progression) if x == 1]
  element_max = max(element_num)
  while N < length:
    
    if progression[N] < (N+1):
      error_case()
      break
    
    N+=1
    
else:
  error_case()
  
def error_case():
  print(-1)

Submission status: Runtime Error

Solution code:
import sys

N=int(input())
b=list(map(int,input().split()))

ans=[]
flag=0

def f(x):
	global flag
	for j in range(x,N+1):
		if b==[]:
			break
		elif j+1==len(b):
			ans.insert(0,b.pop(j))
			flag=0
#			print(j)
#			print(ans)
#			print(b)
			f(j-1)
		elif b[j+1]<=j+1:
			ans.insert(0,b.pop(j))
			flag=0
#			print(j)
#			print(ans)
#			print(b)
			f(j)
		elif flag==0:
			flag=1
			f(0)
		else:
			f(j+1)

for i in range(N):
	if b[i]>i+1:
		print(-1)
		sys.exit()

f(0)

for i in range(N):
	print(ans[i])

Submission status: Runtime Error

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

def matchIndex(b):
    N = len(b)
    for i in range(N-1, -1, -1):
        val = b[i]
        if val == i+1:
            return i
    return -1

ret = []
while len(b) > 0:
    index = matchIndex(b)
    if index >= 0:
        ret.append(b.pop(index))
#         print(ret[-1])
    else:
        ret = []
        ret = -1
        break

for it in ret[::-1]:
    print(it)

Submission status: Runtime Error

Solution code:
import copy

N = int(input())
b = tuple(map(int, input().split()))

memo = {}

def dfs(b):
    if len(b) == 0:
        return []

    if b in memo:
        return memo[b]

    for i, c in enumerate(b):
        if c>len(b):
            return None

    ans = None
    for i, c in enumerate(b):
        if c == i+1:
            r = dfs((*b[:i],*b[i+1:]))
            if r is not None:
                ans = [i, *r]
                memo[b] = ans
                break
    return ans

ans = dfs(b)
if ans is None:
    print(-1)
else:
    ans.reverse()
    for a in ans:
        print(a+1)

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10 ** 9)


def rec(arr, l, lst):
    # lstは操作の逆順
    # print(arr, l, lst[::-1])
    if l == 0:
        for p in lst[::-1]:
            print(p)
        exit()
        return

    for i in sorted(range(1, l + 1), reverse=True):
        # 1-indexed
        if arr[i] == i:
            # print(aa, '除去')
            # 最後に入れた数は、何番目と数の大きさが一致する
            rec(arr[:i - 1] + arr[i:], l - 1, lst + [i])
        elif arr[i] > i:
            # 何番目よりも数が大きい
            return
    return


N = int(input())
b = list(map(int, input().split()))

rec(b, N, [])

print(-1)

Submission status: Runtime Error

Solution code:
import sys
ans_list = []
N = int(input())
B = list(map(int, input().split()))
B_length = len(B)

def check(B, idx = 0):
    global ans_list, B_length
    if len(B) < 1 or len(ans_list) == B_length:
        ans_list.reverse()
        print('\n'.join(list(map(str, ans_list))))
        sys.exit()
    if idx + 1 > len(B):
        print(-1)
        sys.exit()
    
    temp_B = B[:]
    temp_B.sort(reverse = True)
    temp_B = temp_B[idx:]
    max_b = temp_B[0]
    max_idx = B.index(max_b)
    if max_b == max_idx + 1:
        B.pop(max_idx)
        ans_list.append(max_b)
        check(B)
    else:
        idx += 1
        check(B, idx)

check(B, 0)

Submission status: Runtime Error

Solution code:
n,*b=map(int,open(0).read().split())

a=[]
for i in range(n):
    mx=max(b)
    while 1:
        mxi=b.index(mx)
        if mxi==mx-1:
            del b[mxi]
            a.append(mx)
            break
        elif mxi>mx-1:
            mx-=1
        else:
            break
    if mxi<mx-1:
        print(-1)
        break

print(*a[::-1],sep="\n")

Submission status: Runtime Error

Solution code:
length = int(input())
progression = list(map(int,input().split()))

n = 1
N = 0

if progression[0] != 1:
  while n < length:
    remainder = progression[n]-progression[n-1]
    nijou = remainder**2
    if nijou > 1:
      error_case()
      break
    n+=1
  while N < length:
    if progression[N] < (N+1):
      error_case()
      break
    N+=1
    
else:
  error_case()
  
def error_case():
  print(-1)

Submission status: Runtime Error

Solution code:
for i in range(1e5):
  print(1)

Submission status: Runtime Error

Solution code:
n=int(input())
b=[int(x) for x in input().split()]

b=sorted(b)
for i in range(n):
    if !(b[i]<=i+1):
        print(-1)
        break
        
print(b)

Submission status: Runtime Error

Solution code:
N = int(input())
b = [int(x) for x in input().split()]

if sum([(x > idx + 1) for (idx, x) in enumerate(b)]) >= 1:
  print(-1)

list_ = []
while len(b) > 0:
  for idx, c in enumerate(b):
    if idx+1 == c:
      del_idx = idx
  list_.append(b.pop(del_idx))
  
for c in list_[::-1]:
	print(c)

Submission status: Runtime Error

Solution code:
a = []
b = [1, 1, 1, 2, 2, 1, 2, 3, 2]
N = 9
for i in range(N):
  if b[i] < i:
    a.append(b[i])
  else:
    print(-1)
    return
print(a)