General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
101141810 Practice:
amitjoshi24
1454F - 23 PyPy 3 Wrong answer on test 2 1153 ms 10128 KB 2020-12-14 08:06:44 2020-12-14 08:06:45
→ Source
import heapq
from collections import defaultdict

testCaseCounter = int(input())
for lksjdfa in range(testCaseCounter):
	n = int(input())
	arr = [int(amit) for amit in input().split(" ")]
	leftPointer = 0
	rightPointer = n-1
	leftMax = arr[leftPointer]
	rightMax = arr[rightPointer]
	middleHeap = arr[1:-1].copy()
	#print (arr)
	heapq.heapify(middleHeap)
	#print (arr)
	freqMiddle = defaultdict(int)# stores the freq of every element in middle section
	maxMiddle = None
	freqMiddle[leftMax] += 1
	freqMiddle[rightMax] += 1
	for item in middleHeap:
		freqMiddle[item] += 1
		if freqMiddle[item] >= 3 and (maxMiddle is None or item > maxMiddle):
			maxMiddle = item
	freqMiddle[leftMax] -= 1
	freqMiddle[rightMax] -= 1
	if maxMiddle is None:
		print ("NO")
		continue

	need = 3
	leftContainsTripleMax = False
	rightContainsTripleMax = False
	if leftMax == maxMiddle:
		leftContainsTripleMax = True
	if rightMax == maxMiddle:
		rightContainsTripleMax = True

	xd = False

	while leftPointer < rightPointer + 1 and len(middleHeap) > 0:
		#print ((leftMax, middleHeap[0], rightMax))
		#print ((leftPointer, rightPointer))
		if leftMax == rightMax == middleHeap[0]:
			# success
			break
		elif leftMax < rightMax:
			leftPointer += 1
			if arr[leftPointer] == maxMiddle:
				leftContainsTripleMax = True
			leftMax = max(leftMax, arr[leftPointer])
			freqMiddle[arr[leftPointer]] -= 1
			while len(middleHeap) > 0 and freqMiddle[middleHeap[0]] == 0:
				heapq.heappop(middleHeap)
		elif rightMax < leftMax:
			rightPointer -= 1
			if arr[rightPointer] == maxMiddle:
				rightContainsTripleMax = True
			rightMax = max(rightMax, arr[rightPointer])
			freqMiddle[arr[rightPointer]] -= 1
			while len(middleHeap) > 0 and freqMiddle[middleHeap[0]] == 0:
				heapq.heappop(middleHeap)
		elif leftMax == rightMax:
			if arr[leftPointer + 1] < maxMiddle or (arr[leftPointer + 1] == maxMiddle and (rightContainsTripleMax == True or freqMiddle[maxMiddle] >= 3) and freqMiddle[maxMiddle] >= 2):
				# eat the left
				leftPointer += 1
				if arr[leftPointer] == maxMiddle:
					leftContainsTripleMax = True
				leftMax = max(leftMax, arr[leftPointer])
				freqMiddle[arr[leftPointer]] -= 1
				while len(middleHeap) > 0 and freqMiddle[middleHeap[0]] == 0:
					heapq.heappop(middleHeap)
			elif arr[rightPointer - 1] < maxMiddle or (arr[rightPointer - 1] == maxMiddle and (leftContainsTripleMax == True or freqMiddle[maxMiddle] >= 3) and freqMiddle[maxMiddle] >= 2):
				rightPointer -= 1
				if arr[rightPointer] == maxMiddle:
					rightContainsTripleMax = True
				rightMax = max(rightMax, arr[rightPointer])
				freqMiddle[arr[rightPointer]] -= 1
				while len(middleHeap) > 0 and freqMiddle[middleHeap[0]] == 0:
					heapq.heappop(middleHeap)
			else:
				print ("NO")
				xd = True
				break
	if xd:
		continue

	if len(middleHeap) > 0 and leftMax == rightMax == middleHeap[0]:
		x = leftPointer + 1
		y = rightPointer - 1 - leftPointer
		z = (n - x - y)
		print ("YES")
		print (str(x) + " " + str(y) + " " + str(z))
	else:
		print ("NO")


?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details