Hi, ↵
↵
I am stuck at [problem: 2001D]. 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 thus not present in complete formruncated 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: [submission:280104081]↵
↵
↵
<spoiler summary="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_)↵
↵
~~~~~↵
↵
</spoiler>↵
↵
↵
I am stuck at [problem: 2001D]. 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 t
↵
Can someone please point out the bug/ provide a test case for which the code does not work?↵
↵
Thanks in advance.↵
↵
↵
My submission: [submission:280104081]↵
↵
↵
<spoiler summary="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_)↵
↵
~~~~~↵
↵
</spoiler>↵
↵
