글 읽기 - 반례가 있을까요? 50퍼에서 틀립니다 도와주세요ㅕ ㅜㅜㅜ

zinzun 2년 전 0

리스트 개수가 10개와 그 이상으로 나누고

왼쪽 맥스힙과 오른쪽 민 힙으로 나눠서 (왼쪽 힙은 항상 오늘쪽 힙보다 작음)

힙 상태를 유지하면서 i*j가 짝수인 것만 출력하게 했습니다.

import sys
import heapq
input = sys.stdin.readline
t = int(input())
for i in range(t):
	lst = []
	n = int(sys.stdin.readline().rstrip())

	if n // 11 == 0:
		print(n // 2 + 1)
		lst = list(map(int, input().split()))
		left = []
		right = []
		for i, v in enumerate(lst):
			if len(left) == len(right):
				heapq.heappush(left, -v)
			else:
				heapq.heappush(right, v)
			if right and -left[0] > right[0]:
				lf = heapq.heappop(left)
				rg = heapq.heappop(right)
				heapq.heappush(left, -rg)
				heapq.heappush(right, -lf)
			if i % 2 == 0:
				print(-left[0], end =' ')
		print()
	else:

		answer = []
		lst = [list(map(int, input().split())) for j in range(n//10+1)]
		# print(lst)
		left = []
		right = []
		row = n // 10
		for i in range(row+1):
			if i == row:
				for j in range(n % 10):
					if len(left) == len(right):
						heapq.heappush(left, -lst[i][j])
					else:
						heapq.heappush(right, lst[i][j])
					if right and -left[0] > right[0]:
						lf = heapq.heappop(left)
						rg = heapq.heappop(right)
						heapq.heappush(left, -rg)
						heapq.heappush(right, -lf)
					if j % 2 == 0:
						answer.append(-left[0])
			else:
				for j in range(10):
					if len(left) == len(right):
						heapq.heappush(left, -lst[i][j])
					else:
						heapq.heappush(right, lst[i][j])
					if right and -left[0] > right[0]:
						lf = heapq.heappop(left)
						rg = heapq.heappop(right)
						heapq.heappush(left, -rg)
						heapq.heappush(right, -lf)
					if i == 0:
						if j % 2 ==0:
							answer.append(-left[0])
					elif (i*j) % 2 == 0:
						answer.append(-left[0])
		print(n // 2 + 1)
		for i in range(0, len(answer), 10):
			print(*answer[i:i+10])

zinzun 2년 전 0

append 할때 j 의 조건 때문에 틀렸네요

60~63 번째줄을 다음과 같이 바꾸면 됩니다.

if j % 2 == 0:
    answer.append(-left[0])

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

문제

문제

출처

ICPC

반례가 있을까요? 50퍼에서 틀립니다 도와주세요ㅕ ㅜㅜㅜ

zinzun 2년 전 0

zinzun 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말