?
# | 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 |
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")
?
?
?
?