Round 967 (Div 2) Problem D [Test case needed]

#	User	Rating
1	Benq	3792
2	VivaciousAubergine	3647
3	Kevin114514	3603
4	jiangly	3583
5	strapple	3515
6	tourist	3470
7	dXqwq	3436
8	Radewoosh	3415
9	Otomachi_Una	3413
10	Um_nik	3376

#	User	Contrib.
1	Qingyu	157
2	adamant	153
3	Um_nik	146
3	Proof_by_QED	146
5	Dominater069	145
6	errorgorn	141
7	cry	139
8	YuukiS	135
9	TheScrasse	134
10	chromate00	133

Hi,

I am stuck at 2001D - Longest Max Min Subsequence. My logic is similar to other accepted solutions. Also, my solution works for all the small test cases I can find from other people's accepted solutions. Some test cases are big and truncated on CF, so I could not test my code with those cases.

Can someone please point out the bug/ provide a test case for which the code does not work?

Thanks in advance.

My submission: 280104081

my solution

import heapq


def solve(nums):
    uq = set()
    cum = [0] * len(nums)
    for i, v in enumerate(nums[::-1]):
        uq.add(v)
        cum[i] = len(uq)
    cum = cum[::-1]

    min_heap, max_heap = [], []
    for i, v in enumerate(nums):
        heapq.heappush(min_heap, (-cum[i], v, i))
        heapq.heappush(max_heap, (-cum[i], -v, i))

    last_idx = -1
    ans, used = [], set()
    for i in range(len(uq)):
        if i%2: # pick small
            while min_heap and (min_heap[0][2] < last_idx or min_heap[0][1] in used):
                heapq.heappop(min_heap)
            now = heapq.heappop(min_heap)
            ans.append(now[1])
            used.add(now[1])
            last_idx = now[2]
            continue

        while max_heap and (max_heap[0][2] < last_idx or -max_heap[0][1] in used):
            heapq.heappop(max_heap)
        now = heapq.heappop(max_heap)
        ans.append(-now[1])
        used.add(-now[1])
        last_idx = now[2]

    return ans

if __name__ == '__main__':
    for _ in range(int(input())):
        n = int(input())
        num = list(map(int, input().split()))

        ans_ = solve(num)
        print(len(ans_))
        print(*ans_)

DhurBaal's blog