글 읽기 - 파이썬 틀리다고 합니다.... 반례나 틀린 부분을 알려주시면 감사하겠습니다

tmddud0103 2년 전 0

무엇이 문제일지 정말 모르겠습니다...

import sys
import heapq
sys.stdin = open('input.txt')


TC = int(sys.stdin.readline().lstrip())
for _ in range(TC):
    heap = []
    maxheap = []
    ins = 0
    dele = 0
    n = int(sys.stdin.readline().lstrip())
    for _ in range(n):
        in_de, num = list(map(str, sys.stdin.readline().split()))
        if in_de == 'I':
            heapq.heappush(heap, int(num))
            heapq.heappush(maxheap, (-0.1 * int(num), num))
            ins += 1
        else:
            dele += 1
            if ins <= dele:
                if ins > 0:
                    heap = []
                    maxheap = []
                    ins = 0
                dele = 0
            else:
                if num == '1':
                    heapq.heappop(maxheap)
                else:
                    heapq.heappop(heap)
    if ins == 0:
        print('EMPTY')
    elif ins - dele == 1:
        print('{} {}'.format(heap[0], heap[0]))
    else:
        print('{} {}'.format(maxheap[0][1], heap[0]))

byeongkeunahn 2년 전 4

우선순위 큐에서 최댓값/최솟값을 삭제할 때 maxheap/heap 중 한 쪽만 변경해주셨는데요, 그렇게 되면 반대쪽에 삭제되지 않고 남은 원소가 나중에 문제를 일으킬 수 있습니다.

should print -1 -3, but prints 2 -3

한 가지 덧붙이자면, python에서 int 자료형은 64비트입니다. 입력 자료형은 32비트입니다. 따라서 17번 줄과 같이 처리할 필요는 없습니다. 그러나 64비트 정수 x가 입력으로 들어온다고 하더라도 -x-1로 저장하면 double이 필요하지 않습니다.

1
9
I 1
I 2
I 3
D -1
D -1
I -1
I -2
I -3
D 1

tmddud0103 2년 전 0

친절한 답변과 예시 감사드립니다!

maxheap/heap 중 한 쪽만 변경하고 최대, 최소만 변경하면 될 줄 알았는데 반례가 있었네요! 저걸 해결할 방법을 찾아보겠습니다.

그리고 약간의 변명을 하자면 -0.1은 알고 있었는데 저게 문제인가 싶어서 건들여 본 것입니다. 원래는 -1이었습니다

이제 문제가 생긴 부분을 알았으니 방향을 잡은 것 같습니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

파이썬 틀리다고 합니다.... 반례나 틀린 부분을 알려주시면 감사하겠습니다

tmddud0103 2년 전 0

byeongkeunahn 2년 전 4

tmddud0103 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말