====== 중앙값 구하기 ======

===== 풀이 =====
  * [[ps:우선순위큐#Running Median]]문제. [[ps:problems:boj:1655]]와 거의 동일하므로 풀이도 그쪽을 참고.
  * 다만, [[ps:problems:boj:1655]]에 비해서 입출력 형식이 쓸데없이 복잡하다. 숫자들을 10개단위로 라인을 쪼개 놓아서 번거롭다.

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 2696. 중앙값 구하기".

- Problem link: https://www.acmicpc.net/problem/2696
- Solution link: http://www.teferi.net/ps/problems/boj/2696
"""

import heapq
import sys

INF = float('inf')


def main():
    T = int(sys.stdin.readline())
    for i in range(T):
        M = int(sys.stdin.readline())
        print(M // 2 + 1)
        max_heap = []
        min_heap = []
        median = INF
        read_count = 0
        while read_count < M:
            nums = [int(x) for x in sys.stdin.readline().split()]
            for num in nums:
                if num < median:
                    heapq.heappush(max_heap, -num)
                    if len(max_heap) > len(min_heap) + 1:
                        heapq.heappush(min_heap, -heapq.heappop(max_heap))
                else:
                    heapq.heappush(min_heap, num)
                    if len(max_heap) < len(min_heap):
                        heapq.heappush(max_heap, -heapq.heappop(min_heap))
                median = -max_heap[0]
                read_count += 1
                if read_count % 2:
                    print(median, end=('\n' if read_count % 20 == 19 else ' '))
        print()


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:boj:골드_2}}