Problem:


Score : 1200 points

Problem Statement

There are N arrays.
The length of each array is M and initially each array contains integers (1，2，...，M) in this order.

Mr. Takahashi has decided to perform Q operations on those N arrays.
For the i-th (1≤i≤Q) time, he performs the following operation.

Choose an arbitrary array from the N arrays and move the integer a_i (1≤a_i≤M) to the front of that array. For example, after performing the operation on a_i=2 and the array (5，4，3，2，1), this array becomes (2，5，4，3，1).

Mr. Takahashi wants to make N arrays exactly the same after performing the Q operations.
Determine if it is possible or not.

Constraints

2≤N≤10^5

2≤M≤10^5

1≤Q≤10^5

1≤a_i≤M

Input

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

N M
Q
a_1 a_2 ... a_Q

Output

Print Yes if it is possible to make N arrays exactly the same after performing the Q operations.
Otherwise, print No.

Sample Input 1

2 2
3
2 1 2

Sample Output 1

Yes

You can perform the operations as follows.

Sample Input 2

3 2
3
2 1 2

Sample Output 2

No

Sample Input 3

2 3
3
3 2 1

Sample Output 3

Yes

You can perform the operations as follows.

Sample Input 4

3 3
6
1 2 2 3 3 3

Sample Output 4

No



Sample input:
2 2
3
2 1 2


Sample output:
Yes

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.readline

def check1(A):
    K = max(A)
    table = [-1]*(K+1)
    for i in range(Q):
        table[A[i]] = i
    
    if -1 in table:
        return False
    if any(t1-t2 < 0 for t1, t2 in zip(table, table[1:])):
        return False
    return True

INF = 10**9+7
def check2(A):
    stack = []
    used = set()
    for a in A[::-1] + list(range(M)):
        if a not in used:
            used.add(a)
            stack.append(a)
    
    C = dict()
    for i in range(M):
        C[stack[i]] = i
    
    table = [0]*M + [INF]
    for a in A[::-1]:
        if table[C[a]] < table[C[a]-1]:
            table[C[a]] += 1
    
    zero = stack.index(0)
    if all(t2 > t1 for t1, t2 in zip(stack[zero:], stack[zero+1:])):
        for a in stack[zero:]:
            table[C[a]] = N
    

    return  all(t >= N or t == 0 for t in table)

N, M = map(int, readline().split())
Q = int(readline())
A = list(map(lambda x: int(x)-1, readline().split()))

ans = 'Yes'
if not check1(A):
    if not check2(A):
        ans = 'No'
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.readline

def check1(A):
    K = max(A)
    table = [-1]*(K+1)
    for i in range(Q):
        table[A[i]] = i
    
    if -1 in table:
        return False
    if any(t1-t2 < 0 for t1, t2 in zip(table, table[1:])):
        return False
    return True

INF = 10**9+7
def check2(A):
    table = [0]*M + [INF]
    idx = 0 
    C = dict()
    for i in range(len(A)-1, -1, -1):
        a = A[i]
        if a not in C:
            C[a] = idx
            idx += 1
        
        cidx = C[a]
        if table[cidx] < table[cidx-1]:
            table[cidx] += 1
                
    if all(table[i] >= N for i in range(idx)):
        return True
    return False

N, M = map(int, readline().split())
Q = int(readline())
A = list(map(lambda x: int(x)-1, readline().split()))

ans = 'Yes'
if not check1(A):
    A = [0]*N + A
    if not check2(A):
        ans = 'No'
print(ans)

Submission status: Wrong Answer

Solution code:

"""
Writer: SPD_9X2
https://atcoder.jp/contests/code-festival-2016-quala/tasks/codefestival_2016_qualA_e

最後の配列の状態は何で決定されるか。
同じaが同じ配列に複数回採用されたとき、効果があるのは最後に
採用したaのみ。(それ以前は合っても無くても同じになる)

最初、1が採用状態になっていると考えてよい。
→おそらく気にすべきは配列aのみ(Nこの配列は考慮しなくてよい)

1以外は、出現するなら少なくともN個出現しなければ不可能
2,3だけで考えてみよう

N==3のとき

322233 →不可能(2が先頭が1つ生まれてしまう)
232233 →可能

→終了後の配列の数字は、最後に出現した順に前から並ぶ
→よってaを見れば構成後の数列は分かる

→後ろからaを見ていって、先に登場したやつより後に登場したほうが数が越えたらダメ
→ただし、N個目以降は完全無視する
→終了時に数がNに達していないのがあったらダメ(1を除く？)

いや例3…
→初期状態、の扱い方を考え直さなきゃな…

aの前に M…M(N個),M-1…M-1,…,1…1 があると考える
すると、aを後ろから見ていった時に先に登場したやつより後に登場したほうが数が越えてはいけない、
だけの条件になる！！

"""
import sys
N,M = map(int,input().split())

Q = int(input())

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

dic = {}
lis = []
flag = True

a = [[M-i,N] for i in range(M)]
for i in range(Q):
    a.append([A[i],1])
a.reverse()

for i in range(len(a)):

    if a[i][0] not in dic:
        ind = len(dic)
        dic[a[i][0]] = ind
        lis.append(a[i][1])
    else:
        ind = dic[a[i][0]]
        lis[ind] = min(N,lis[ind] + a[i][1])
    
    if ind != 0 and lis[ind] > lis[ind-1]:
        print ("No")
        sys.exit()

print ("Yes")

Submission status: Wrong Answer

Solution code:
def reads(offset = 0):
	return [int(i) - offset for i in input().split(' ')]
(N, M) = reads()
Q = int(input())
A = reads(1)
pos = [-1] * M
pat = []
freq = [0] * (M+1)
freq[0] = N
counter = 0
for i in A[::-1]:
	if (i not in pat):
		pat.append(i)
		pos[i] = counter
		freq[counter] -= 1
		counter += 1
		freq[counter] += 1
		print('freq is',freq)
	else:
		temp = pos[i]
		if (freq[temp] > 0):
			freq[temp] -= 1
			freq[temp+1] += 1
			print('freq is',freq)
if(counter != M):
	for i in range(M):
		if (i not in pat):
			pat.append(i)
for i in range(M):
	if (freq[i] != 0):
		start = i
		break
p = pat[start:]
p.sort()
if(p == pat[start:]):
	print("Yes")
else:
	print("No")

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
#-*- coding: utf-8 -*-
# E-LRU Puzle
def reads(offset = 0):
	return [int(i) - offset for i in input().split(' ')]
#Data input
(N, M) = reads()
Q = int(input())
A = reads(1)

#Data structure initial
pos = [-1] * M
pat = []
freq = [0] * (M+1)
freq[0] = N

#Pattern search & Match count
counter = 0
for i in A[::-1]:
	if (i not in pat):
		pat.append(i)
		pos[i] = counter
		freq[counter] -= 1
		counter += 1
		freq[counter] += 1
		print('freq is',freq)
	else:
		temp = pos[i]
		if (freq[temp] > 0):
			freq[temp] -= 1
			freq[temp+1] += 1
			print('freq is',freq)

if(counter != M):
	for i in range(M):
		if (i not in pat):
			pat.append(i)

#Result judge
for i in range(M):
	if (freq[i] != 0):
		start = i
		break

p = pat[start:]
p.sort()
if(p == pat[start:]):
	print("Yes")
else:
	print("No")

Submission status: Wrong Answer

Solution code:
def reads(offset = 0):
	return [int(i) - offset for i in input().split(' ')]
(N, M) = reads()
Q = int(input())
A = reads(1)
pos = [-1 for i in range(M)]
pat = []
freq = [0 for i in range(M+1)]
freq[0] = N
counter = 0
for i in A[::-1]:
	if (i not in pat):
		pat.append(i)
		pos[i] = counter
		--(freq[counter])
		++counter 
		++(freq[counter])
	else:
		temp = pos[i]
		if (freq[temp] > 0):
			--freq[temp]
			++freq[temp+1]
if(counter != M):
	for i in range(M):
		if (i not in pat):
			pat.append(i)
for i in freq:
	if (i != 0):
		start = i
		break
temp = pat[start:]
temp.sort()
if(temp == pat[start:]):
	print("Yes")
else:
	print("No")

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
#-*- coding: utf-8 -*-
# E-LRU Puzle
def reads(offset = 0):
	return [int(i) - offset for i in input().split(' ')]
#Data input
(N, M) = reads()
Q = int(input())
A = reads(1)

#Data structure initial
pos = [-1 for i in range(M)]
pat = []
freq = [0 for i in range(M+1)]
freq[0] = N

#Pattern search & Match count
counter = 0
for i in A[::-1]:
	if (i not in pat):
		pat.append(i)
		pos[i] = counter
		--(freq[counter])
		++counter 
		++(freq[counter])
	else:
		temp = pos[i]
		if (freq[temp] > 0):
			--freq[temp]
			++freq[temp+1]

if(counter != M):
	for i in range(M):
		if (i not in pat):
			pat.append(i)

#Result judge
for i in freq:
	if (i != 0):
		start = i
		break

temp = pat[start:]
temp.sort()
if(temp == pat[start:]):
	print("Yes")
else:
	print("No")

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
#-*- coding: utf-8 -*-
# E-LRU Puzle

from collections import defaultdict
def ReadInput():
	return [int(a) for a in input().split(' ')]

(N, M) = ReadInput()
Q = int(input())
Array = ReadInput()
def ifEqual(x):
	temp = None
	for i in x:
		if (temp == None):	
			temp = x[i]
			continue
		elif (x[i] != temp):
			return 0
	return temp

def check(Array, N, M, *args):
	Count = defaultdict(int)
	Array.reverse()
	for i in Array:
		if (i == 1 or Count[i] < Count[i-1]):
			Count[i] += 1
	Count.pop(N)
	if(ifEqual(Count)):
		return 1
	
	Count = defaultdict(int)
	for i in Array:
		if (i == N or Count[i] < Count[i+1]):
			Count[i] += 1
	Count.pop(1)
	if(ifEqual(Count) >= M):
		return 1
	else:
		return 0
if (check(Array, N, M)):
	print("Yes")
else:
	print("No")

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
#-*- coding: utf-8 -*-
# E-LRU Puzle

from collections import defaultdict
def ReadInput():
	return [int(a) for a in input().split(' ')]

(N, M) = ReadInput()
Q = int(input())
Array = ReadInput()
def ifEqual(x):
	temp = None
	for i in x:
		if (temp == None):	
			temp = x[i]
			continue
		elif (x[i] != temp):
			print('ifEqual is 0')
			return 0
	return temp

def check(Array, N, M, *args):
	Count = defaultdict(int)
	Array.reverse()
	if ("reverse") not in args:
		for i in Array:
			if (i == 1 or Count[i] < Count[i-1]):
				Count[i] += 1
			else:	
				return 0
		Count.pop(N)
		if(ifEqual(Count)):
			return 1
		else:
			return 0
	else:
		for i in Array:
			if (i == N or Count[i] < Count[i+1]):
				Count[i] += 1
			else:
				return 0
		Count.pop(1)
		if(ifEqual(Count) >= M):
			return 1
		else:
			return 0
if (check(Array, N, M) or check(Array, N, M, "reverse")):
	print("Yes")
else:
	print("No")

Submission status: Wrong Answer

Solution code:
printd=lambda *args:0 #print
N,M = [int(x) for x in input().split()]
Q=int(input())


a = [int(x)-1 for x in input().split()]
target=[]


for x in reversed(a):
    if x not in target:
        target.append(x)

if target[-1]==0:
    target.pop()
if all(target[i]==i for i in range(M)):
    target=[]
printd(target)
can_trash= set()

b = [0 for _ in range(N)]

for x in reversed(a):
    for i,value in enumerate(b):
        printd(i,value,x,b)
        if value<len(target) and target[value]==x:
            b[i] = value+1
            printd(b)
            can_trash.add(x)
            break
    if x==0:
        if any(val==len(target) for val in b ):
            can_trash.add(0)
    if x in can_trash:
        continue

    else:
        print('No')
        exit()

if all(x==len(target) for x in b):
    print('Yes')
else:
    print("No")

Submission status: Wrong Answer

Solution code:

def read():
    return int(input())

def reads(sep=None):
    return list(map(int, input().split()))

def f(m, a):
	sa = set(a)
	seen = set()
	r = []
	for n in a[::-1]:
		if n not in seen:
			r.append(n)
			seen.add(n)
	for i in range(m):
		if (i+1) not in sa:
			r.append(i+1)
	return r

def isSorted(a):
	for i in range(1, len(a)):
		if a[i-1] > a[i]:
			return False
	return True

n, m = reads()
q = read()
a = reads()

r = f(m, a)
count = [0] * (m+1)
count[0] = n

table = [-1] * (m+1)
for i in range(len(r)):
	table[r[i]] = i

for aa in a[::-1]:
	index = table[aa]
	if 0 < count[index]:
		count[index] -= 1
		count[index+1] += 1

to = 0
for i in range(m):
	if 0 < count[i]:
		to = i
		break

if isSorted(r[to:]):
	print('Yes')
else:
	print('No')

Submission status: Wrong Answer

Solution code:
# find what should answer be
N, M = map(int, raw_input().split())
Q = int(raw_input())
a_list = map(int, raw_input().split())

sol = "Yes"

# back search
final_order = []
for i in range(Q, 0, -1):
    if a_list[i-1] not in final_order:
        final_order.append(a_list.pop(i-1))

final_list_1 = final_order
for i in range(1, M+1):
    if i not in final_list_1:
        final_list_1.append(i)

# back search
for n in range(N-1):
    final_order = []
    for i in range(len(a_list), 0, -1):
        if a_list[i-1] not in final_order:
            final_order.append(a_list.pop(i-1))

    final_list = final_order
    for i in range(1, M+1):
        if i not in final_list:
            final_list.append(i)
    if final_list_1 != final_list:
        sol = "No"
print sol

Submission status: Wrong Answer

Solution code:
n, m = map(int,raw_input().split(' '))
q = int(raw_input())
a = map(lambda i: int(i) - 1, raw_input().split(' '))
a.reverse()

s = set(range(m))
ans = []

for i in a:
    if i in s:
        s -= set([i])
        ans.append(i)

rest = list(s)
rest.reverse()

for i in rest:
    ans.append(i)

maximum = 10000000

while ans and ans[-1] < maximum:
    maximum = ans[-1]
    ans.pop()

index = [-1] * m

for i, v in enumerate(ans):
    index[v] = i

num = [0] * len(ans)

for i in a:
    ind = index[i]
    if ind == -1: continue
    if ind == 0 or num[ind-1] > num[ind]:
        num[ind] += 1

print "Yes" if len(num) == 0 or num[-1] >= n else "No"

Submission status: Wrong Answer

Solution code:
import numpy as np
import itertools as it



n, m = map(int, raw_input().split())
num = int(raw_input())
arr = np.empty(shape=(n,m),dtype=int)
for i in range(n):
    arr[i] = np.arange(1, m+1)


st = raw_input()
q = st.split()
q = [int(a) for a in q]

list =[]
for i in range (1, n+1):
    for i in range(1, n + 1):
        list.append(i)
        list.append(i)
        list.append(i)

global copy

kol=0
mySet = []
mySet = set(it.permutations(list, num))

for item in mySet:
    copy = arr.copy()
    for i in range(0, len(item)):
        line = copy[item[i]-1]
        for j in range(0, m):
            if (line[j] == q[i]):
                n = j
        line = np.delete(line, n)
        line = np.insert(line, 0, q[i])
        for k in range(0, len(line)):
            copy[item[i] - 1][k] = line[k]

    if (copy == copy[0]).all():
        kol+=1


if kol>0:
    print "Yes"
else:
    print "No"

Submission status: Wrong Answer

Solution code:
input()
input()
input()

print('Yes')

Submission status: Wrong Answer

Solution code:
import numpy as np


def move(arr, item):
    for i in range (0, len(arr)):
        if arr[i] == item:
            n=i
    arr=np.delete(arr,n)
    arr=np.insert(arr, 0, item)


n, m = map(int, raw_input().split())
num = int(raw_input())
arr = np.empty(shape=(n,m),dtype=int)
for i in range(n):
    arr[i] = np.arange(1, m+1)


st = raw_input()
q = st.split()
q = [int(a) for a in q]

k=0
mySet = set((a, b, c, d, e, f) for a in range(1,n+1) for b in range(1,n+1) for c in range(1,n+1) for d in range(1,n+1) for e in range(1,n+1) for f in range(1,n+1))
for item in mySet:
    copy = arr.copy()
    for i in range(0, len(item)):
        move(copy[item[i]-1], q[item[i]-1])

    if (copy == copy[0]).all():
        k+=1


if k>0:
    print "Yes"
else:
    print "No"

Submission status: Wrong Answer

Solution code:
# find what should answer be
N, M = map(int, raw_input().split())
Q = int(raw_input())
a_list = map(int, raw_input().split())

sol = "YES"

# back search
final_order = []
for i in range(Q, 0, -1):
    if a_list[i-1] not in final_order:
        final_order.append(a_list.pop(i-1))

final_list_1 = final_order
for i in range(1, M+1):
    if i not in final_list_1:
        final_list_1.append(i)

# back search
for n in range(N-1):
    final_order = []
    for i in range(len(a_list), 0, -1):
        if a_list[i-1] not in final_order:
            final_order.append(a_list.pop(i-1))

    final_list = final_order
    for i in range(1, M+1):
        if i not in final_list:
            final_list.append(i)
    if final_list_1 != final_list:
        sol = "NO"
print sol

Submission status: Wrong Answer

Solution code:
import random

n, m = map(int, raw_input().split())
q = int(raw_input())
a = map(int, raw_input().split())
print random.choice(["Yes", "No"])

Submission status: Time Limit Exceeded

Solution code:
def reads(offset = 0):
	return [int(i) - offset for i in input().split(' ')]
def Judge(vector):
	length = len(vector)-1
	for i in range(length):
		if(vector[i] > vector[i+1]):		
			return 0
	return 1
(N, M) = reads()
Q = int(input())
A = reads(1)
pos = [-1] * M
pat = []
freq = [0] * (M+1)
freq[0] = N
counter = 0
for i in A[::-1]:
	if (i not in pat):
		pat.append(i)
		pos[i] = counter
		counter += 1
		if(counter == M):
			break
for i in range(M):
	if (pos[i] == -1):
		pat.append(i)
for i in A[::-1]:
	temp = pos[i]
	if (freq[temp] > 0):
		freq[temp] -= 1
		freq[temp+1] += 1
for i in range(M):
	if (freq[i] != 0):
		start = i
		break
print("Yes") if Judge(pat[start:]) else print("No")

Submission status: Time Limit Exceeded

Solution code:
def reads(offset = 0):
	return [int(i) - offset for i in input().split(' ')]
(N, M) = reads()
Q = int(input())
A = reads(1)
pos = [-1] * M
pat = []
freq = [0] * (M+1)
freq[0] = N
counter = 0
for i in A[::-1]:
	if (i not in pat):
		pat.append(i)
		pos[i] = counter
		counter += 1
		if(counter == M):
			break
for i in range(M):
	if (pos[i] == -1):
		pat.append(i)	
for i in A[::-1]:
	temp = pos[i]
	if (freq[temp] > 0):
		freq[temp] -= 1
		freq[temp+1] += 1
for i in range(M):
	if (freq[i] != 0):
		start = i
		break
p = pat[start:]
p.sort()
if(p == pat[start:]):
	print("Yes")
else:
	print("No")

Submission status: Time Limit Exceeded

Solution code:
def reads(offset = 0):
	return [int(i) - offset for i in input().split(' ')]
(N, M) = reads()
Q = int(input())
A = reads(1)
pos = [-1] * M
pat = []
freq = [0] * (M+1)
freq[0] = N
counter = 0
for i in A[::-1]:
	if (i not in pat):
		pat.append(i)
		pos[i] = counter
		freq[counter] -= 1
		counter += 1
		freq[counter] += 1
	else:
		temp = pos[i]
		if (freq[temp] > 0):
			freq[temp] -= 1
			freq[temp+1] += 1
if(counter != M):
	for i in range(M):
		if (i not in pat):
			pat.append(i)
for i in range(M):
	if (freq[i] != 0):
		start = i
		break
p = pat[start:]
p.sort()
if(p == pat[start:]):
	print("Yes")
else:
	print("No")

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
#-*- coding: utf-8 -*-
# E-LRU Puzle
def reads(offset = 0):
	return [int(i) - offset for i in input().split(' ')]
#Data input
(N, M) = reads()
Q = int(input())
A = reads(1)

#Data structure initial
pos = [-1] * M
pat = []
freq = [0] * (M+1)
freq[0] = N

#Pattern search & Match count
counter = 0
for i in A[::-1]:
	if (i not in pat):
		pat.append(i)
		pos[i] = counter
		freq[counter] -= 1
		counter += 1
		freq[counter] += 1
	else:
		temp = pos[i]
		if (freq[temp] > 0):
			freq[temp] -= 1
			freq[temp+1] += 1

if(counter != M):
	for i in range(M):
		if (i not in pat):
			pat.append(i)

#Result judge
for i in range(M):
	if (freq[i] != 0):
		start = i
		break

p = pat[start:]
p.sort()
if(p == pat[start:]):
	print("Yes")
else:
	print("No")

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

printd = print
printd= lambda *args:0
N, M = [int(x) for x in input().split()]
Q = int(input())

a = [int(x) - 1 for x in input().split()]
target = []

for x in list(reversed(a)) + list(range(M)):
    if x not in target:
        target.append(x)
printd(target)
assert len(target) == M
target_length = M - 1
for i in range(len(target) - 1, 0, -1):
    if target[i] > target[i - 1]:
        target_length -= 1
    else:
        break

printd('target_length:',target_length)
can_trash = set()

bd = defaultdict(int)
bd[0] = N
for x in reversed(a):
    _flag = False
    printd('x:', x)
    _index = target.index(x)
    printd(bd,_index,bd[_index])
    if bd[_index]:
        bd[_index] -= 1
        bd[_index+1] += 1
        can_trash.add(x)
        printd('+1')
        continue
    if x == 0:
        if any((not val) or (key>= len(target))  for key,val in bd.items()):
            can_trash.add(0)
    if x in can_trash:
        continue
    else:
        printd('else',bd)
        print('No')
        exit()

printd(bd)
if all((value==0) or key >= target_length for key,value in bd.items()):
    print('Yes')
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
printd = print
printd= lambda *args:0 #print
N, M = [int(x) for x in input().split()]
Q = int(input())

a = [int(x) - 1 for x in input().split()]
target = []

for x in list(reversed(a)) + list(range(M)):
    if x not in target:
        target.append(x)
printd(target)
assert len(target) == M
target_length =M-1
for i in range(len(target) - 1, 0, -1):
    if target[i] > target[i-1]:
        target_length-=1
    else:
        break

printd(target_length)
can_trash = set()


b = [0 for _ in range(N)]

for x in reversed(a):
    _flag =False
    printd('x:',x)
    for i, value in enumerate(b):
        printd(i, value, x, b)
        if value < M and target[value] == x:
            b[i] = value + 1
            printd('value add ',b)
            can_trash.add(x)
            _flag = True
            break
    if _flag:
        continue

    if x == 0:
        if any(val == len(target) for val in b):
            can_trash.add(0)
    if x in can_trash:
        continue

    else:
        print('No')
        exit()

if all(x >= target_length for x in b):
    print('Yes')
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:

def read():
    return int(input())

def reads(sep=None):
    return list(map(int, input().split()))

def f(m, a):
	r = []
	for n in a[::-1]:
		if n not in r:
			r.append(n)
	for i in range(m):
		if (i+1) not in r:
			r.append(i+1)
	return r

def isSorted(a):
	for i in range(1, len(a)):
		if a[i-1] > a[i]:
			return False
	return True

n, m = reads()
q = read()
a = reads()

r = f(m, a)
count = [0] * (m+1)
count[0] = n

table = [-1] * (m+1)
for i in range(len(r)):
	table[r[i]] = i

for aa in a[::-1]:
	index = table[aa]
	if 0 < count[index]:
		count[index] -= 1
		count[index+1] += 1

to = 0
for i in range(m):
	if 0 < count[i]:
		to = i
		break

if isSorted(r[to:]):
	print('Yes')
else:
	print('No')

Submission status: Time Limit Exceeded

Solution code:

def read():
    return int(input())

def reads(sep=None):
    return list(map(int, input().split()))

def f(m, a):
	r = []
	for n in a[::-1]:
		if n not in r:
			r.append(n)
	for i in range(m):
		if (i+1) not in r:
			r.append(i+1)
	return r

def isSorted(a):
	for i in range(1, len(a)):
		if a[i-1] > a[i]:
			return False
	return True

n, m = reads()
q = read()
a = reads()

r = f(m, a)
count = [0] * (m+1)
count[0] = n

for aa in a[::-1]:
	index = r.index(aa)
	if 0 < count[index]:
		count[index] -= 1
		count[index+1] += 1

to = 0
for i in range(m):
	if 0 < count[i]:
		to = i
		break

if isSorted(r[to:]):
	print('Yes')
else:
	print('No')

Submission status: Time Limit Exceeded

Solution code:

def read():
    return int(input())

def reads(sep=None):
    return list(map(int, input().split()))

def f(m, a):
	r = []
	for n in a[::-1]:
		if n not in r:
			r.append(n)
	for i in range(m):
		if (i+1) not in r:
			r.append(i+1)
	return r


n, m = reads()
q = read()
a = reads()

r = f(m, a)
count = [0] * (m+1)
count[0] = n

for aa in a[::-1]:
	index = r.index(aa)
	if 0 < count[index]:
		count[index] -= 1
		count[index+1] += 1

to = 0
for i in range(m):
	if 0 < count[i]:
		to = i
		break

left, right = r[:to], r[to:]
left = set(left)

flag = True
index = 0
for i in range(1, len(r)+1):
	if i in left:
		continue
	if right[index] != i:
		flag = False
		break
	if right[index] == i:
		index += 1

if flag:
	print('Yes')
else:
	print('No')

Submission status: Time Limit Exceeded

Solution code:

def read():
    return int(input())

def reads(sep=None):
    return list(map(int, input().split()))

def f(m, a):
	r = []
	for n in a[::-1]:
		if n not in r:
			r.append(n)
	for i in range(m):
		if (i+1) not in r:
			r.append(i+1)
	return r


n, m = reads()
q = read()
a = reads()

r = f(m, a)
count = [0] * (m+1)
count[0] = n

for aa in a[::-1]:
	index = r.index(aa)
	if 0 < count[index]:
		count[index] -= 1
		count[index+1] += 1

to = 0
for i in range(m):
	if 0 < count[i]:
		to = i
		break

left, right = r[:to], r[to:]

flag = True
index = 0
for i in range(1, len(r)+1):
	if i in left:
		continue
	if right[index] != i:
		flag = False
		break
	if right[index] == i:
		index += 1

if flag:
	print('Yes')
else:
	print('No')

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline

import sys
from itertools import product
readline = sys.stdin.readline

def check1(A):
    K = max(A)
    table = [-1]*(K+1)
    for i in range(Q):
        table[A[i]] = i
    
    if -1 in table:
        return False
    if any(t1-t2 < 0 for t1, t2 in zip(table, table[1:])):
        return False
    return True

INF = 10**9+7
def check2(A):
    stack = []
    used = set()
    for a in A[::-1] + list(range(M)):
        if a not in used:
            used.add(a)
            stack.append(a)
    
    C = dict()
    for i in range(M):
        C[stack[i]] = i
    
    table = [0]*M + [INF]
    for a in A[::-1]:
        if table[C[a]] < table[C[a]-1]:
            table[C[a]] += 1
    
    used = set()
    ch = []
    for i in range(M):
        if table[i] < N:
            break
        ch.append(stack[i])
        used.add(stack[i])
    for i in range(M):
        if i not in used:
            used.add(i)
            ch.append(i)
    
    return stack == ch

N, M = map(int, readline().split())
Q = int(readline())
A = list(map(lambda x: int(x)-1, readline().split()))

ans = 'Yes'
if not check1(A):
    if not check2(A):
        ans = 'No'
print(ans)

Submission status: Accepted

Solution code:

"""
Writer: SPD_9X2
https://atcoder.jp/contests/code-festival-2016-quala/tasks/codefestival_2016_qualA_e

最後の配列の状態は何で決定されるか。
同じaが同じ配列に複数回採用されたとき、効果があるのは最後に
採用したaのみ。(それ以前は合っても無くても同じになる)

最初、1が採用状態になっていると考えてよい。
→おそらく気にすべきは配列aのみ(Nこの配列は考慮しなくてよい)

1以外は、出現するなら少なくともN個出現しなければ不可能
2,3だけで考えてみよう

N==3のとき

322233 →不可能(2が先頭が1つ生まれてしまう)
232233 →可能

→終了後の配列の数字は、最後に出現した順に前から並ぶ
→よってaを見れば構成後の数列は分かる

→後ろからaを見ていって、先に登場したやつより後に登場したほうが数が越えたらダメ
→ただし、N個目以降は完全無視する
→終了時に数がNに達していないのがあったらダメ(1を除く？)

いや例3…
→初期状態、の扱い方を考え直さなきゃな…

aの前に M…M(N個),M-1…M-1,…,1…1 があると考える
すると、aを後ろから見ていった時に先に登場したやつより後に登場したほうが数が越えてはいけない、
だけの条件になる！！

あ、2233223 は…？
最後の2つの2を1箇所に適応すれば可能じゃん！
lis[a[i][0]]ってなんだ…？
→それ以降に先頭をa[i][0]に更新できる最大数
→よって、indに対して単調減少になっていなければいけない

うん？前を超えないようにして、最終的にすべてN以上になればおｋ？
"""
import sys
N,M = map(int,input().split())

Q = int(input())

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

dic = {}
lis = []
flag = True

a = [[M-i,N] for i in range(M)]
for i in range(Q):
    a.append([A[i],1])
a.reverse()
#print (a)

for i in range(len(a)):

    if a[i][0] not in dic:
        ind = len(dic)
        dic[a[i][0]] = ind
        if ind != 0:
            lis.append(min(lis[ind-1] , a[i][1]))
        else:
            lis.append(a[i][1])
    else:
        ind = dic[a[i][0]]
        if ind != 0:
            lis[ind] = min(N, lis[ind] + a[i][1] , lis[ind-1])
        else:
            lis[ind] = min(N, lis[ind] + a[i][1])

if lis[-1] == N:
    print ("Yes")
else:
    print ("No")

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N,M = map(int,input().split())
Q = int(input())
A = [int(x) for x in input().split()]

used = [False] * (M+1)
arr = []
for x in A[::-1]:
    if used[x]:
        continue
    used[x] = True
    arr.append(x)
for x in range(1,M+1):
    if used[x]:
        continue
    arr.append(x)

x_to_i = {x:i for i,x in enumerate(arr,1)}

made = [N] + [0] * M

for x in A[::-1]:
    i = x_to_i[x]
    if made[i-1] > 0:
        made[i-1] -= 1
        made[i] += 1

L = 0
prev = M+100
for x in arr[::-1]:
    if x >= prev:
        break
    prev = x
    L += 1

x = sum(made[::-1][:L+1])
answer = 'Yes' if x == N else 'No'
print(answer)

Submission status: Accepted

Solution code:
def reads(offset = 0):
	return [int(i) - offset for i in input().split(' ')]
def Judge(vector):
	length = len(vector)-1
	for i in range(length):
		if(vector[i] > vector[i+1]):		
			return 0
	return 1
(N, M) = reads()
Q = int(input())
A = reads(1)
pos = [-1] * M
pat = []
freq = [0] * (M+1)
freq[0] = N
found = set()
counter = 0
for i in A[::-1]:
	if (i not in found):
		pat.append(i)
		found.add(i)
		pos[i] = counter
		freq[counter] -= 1
		counter += 1
		freq[counter] += 1
	elif (freq[pos[i]] > 0):
		freq[pos[i]] -= 1
		freq[pos[i]+1] += 1
for i in range(M):
	if (pos[i] == -1):
		pat.append(i)
for i in range(M+1):
	if (freq[i] != 0):
		start = i
		break
print("Yes") if Judge(pat[start:]) else print("No")

Submission status: Accepted

Solution code:
def reads(offset = 0):
	return [int(i) - offset for i in input().split(' ')]
def Judge(vector):
	length = len(vector)-1
	for i in range(length):
		if(vector[i] > vector[i+1]):		
			return 0
	return 1
(N, M) = reads()
Q = int(input())
A = reads(1)
pos = [-1] * M
pat = []
freq = [0] * (M+1)
freq[0] = N
found = set()
counter = 0
for i in A[::-1]:
	if (i not in found):
		pat.append(i)
		found.add(i)
		pos[i] = counter
		counter += 1
for i in range(M):
	if (pos[i] == -1):
		pat.append(i)	
for i in A[::-1]:
	temp = pos[i]
	if (freq[temp] > 0):
		freq[temp] -= 1
		freq[temp+1] += 1
for i in range(M+1):
	if (freq[i] != 0):
		start = i
		break
print("Yes") if Judge(pat[start:]) else print("No")

Submission status: Accepted

Solution code:
def reads(offset = 0):
	return [int(i) - offset for i in input().split(' ')]
def Judge(vector):
	length = len(vector)-1
	for i in range(length):
		if(vector[i] > vector[i+1]):		
			return 0
	return 1
(N, M) = reads()
Q = int(input())
A = reads(1)
pos = [-1] * M
pat = []
freq = [0] * (M+1)
freq[0] = N
found = set()
counter = 0
for i in A[::-1]:
	if (i not in found):
		pat.append(i)
		found.add(i)
		pos[i] = counter
		counter += 1
		if(counter == M):
			break
for i in range(M):
	if (pos[i] == -1):
		pat.append(i)	
for i in A[::-1]:
	temp = pos[i]
	if (freq[temp] > 0):
		freq[temp] -= 1
		freq[temp+1] += 1
start = M
for i in range(M):
	if (freq[i] != 0):
		start = i
		break
print("Yes") if Judge(pat[start:]) else print("No")

Submission status: Accepted

Solution code:

def read():
    return int(input())

def reads(sep=None):
    return list(map(int, input().split()))

def f(m, a):
	sa = set(a)
	seen = set()
	r = []
	for n in a[::-1]:
		if n not in seen:
			r.append(n)
			seen.add(n)
	for i in range(m):
		if (i+1) not in sa:
			r.append(i+1)
	return r

def isSorted(a):
	for i in range(1, len(a)):
		if a[i-1] > a[i]:
			return False
	return True

n, m = reads()
q = read()
a = reads()

r = f(m, a)
count = [0] * (m+1)
count[0] = n

table = [-1] * (m+1)
for i in range(len(r)):
	table[r[i]] = i

for aa in a[::-1]:
	index = table[aa]
	if 0 < count[index]:
		count[index] -= 1
		count[index+1] += 1

to = m
for i in range(m):
	if 0 < count[i]:
		to = i
		break

if isSorted(r[to:]):
	print('Yes')
else:
	print('No')

Submission status: Accepted

Solution code:
from sys import stdin
from itertools import repeat
def main():
    n, m = map(int, stdin.readline().split())
    q = int(stdin.readline())
    a = map(int, stdin.readline().split(), repeat(10, q))
    a = [x - 1 for x in a]
    l = [[] for i in xrange(m)]
    la = []
    for i in xrange(q - 1, -1, -1):
        x = a[i]
        if not l[x]:
            la.append(x)
        l[x].append(i)
    ok = 1
    b = [q] * n
    f = [0] * m
    xt = 0
    for i, x in enumerate(la):
        j = 0
        for y in l[x]:
            if j < n and y < b[j]:
                b[j] = y
                j += 1
        if j < n:
            ok = 0
            b[j] = -1
        if not ok:
            while f[xt]:
                  xt += 1
            if x != xt:
                print "No"
                return
            f[xt] = 1
        else:
            f[x] = 1
    print "Yes"
main()