Submission #312735

#	Time	Username	Problem	Language	Result	Execution time	Memory
312735		DEPRomaniac	Non-boring sequences (CERC12_D)	Cpython 3	0 / 1	27 ms	4212 KiB

D

def check_boring(first, last):
	if first>=last:
		return 1
	for i in range(first,int((first+last)/2)+1):
		if prev[i]<first and next[i]>last:
			return (check_boring(first,i-1) and check_boring(i+1, last))
		if prev[last-i]<first and next[last-i]>last:
			return (check_boring(first,last-i-1) and check_boring(last-i+1, last))
	return 0

def assign_prev():
	d.clear()
	for i in range(0,n):
		if arr[i] in d:
			prev[i] = d[arr[i]]
		else:
			prev[i] = -1
		d[arr[i]] = i

def assign_next():
	d.clear()
	for i in range(n-1, -1, -1):
		if arr[i] in d:
			next[i] = d[arr[i]]
		else:
			next[i] = n
		d[arr[i]] = i

d = dict()

t = int(input())
for i in range(t):
	n = int(input())
	next = [n] *n
	prev = [-1] *n
	arr = list(map(int,input().split()))
	assign_prev()
	assign_next()
	if check_boring(0,n-1) == 1:
		print('non-boring')
	else:
		print('boring')

• Subtask 1: 0 / 1