시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1032 477 380 51.213%

문제

어떤 수열을 읽고, 홀수번째 수를 읽을 때 마다, 지금까지 입력받은 값의 중앙값을 출력하는 프로그램을 작성하시오.

예를 들어, 수열이 1,5,4,3,2 이면, 홀수번째 수는 1번째 수, 3번째 수, 5번째 수이고, 1번째 수를 읽었을 때 중앙값은 1, 3번째 수를 읽었을 때는 4, 5번째 수를 읽었을 때는 3이다.

입력

첫째 줄에 테스트 케이스의 개수 T(1<=T<=1,000)가 주어진다. 각 테스트 케이스의 첫째 줄에는 수열의 크기 M(1<=M<=9999, M=홀수)이 주어지고, 그 다음 줄부터 이 수열의 원소가 차례대로 주어진다. 원소는 한 줄에 10개씩 나누어져있고, 32비트 부호있는 정수이다. (대부분의 언어에서 int)

출력

각 테스트 케이스에 대해 첫째 줄에 출력하는 중앙값의 개수를 출력하고, 둘째 줄에는 홀수 번째 수를 읽을 때 마다 구한 중앙값을 차례대로 공백으로 구분하여 출력한다. 이때, 한 줄에 10개씩 출력해야 한다.

예제 입력 1

3
9
1 2 3 4 5 6 7 8 9
9
9 8 7 6 5 4 3 2 1
23
23 41 13 22 -3 24 -31 -11 -8 -7
3 5 103 211 -311 -45 -67 -73 -81 -99
-33 24 56

예제 출력 1

5
1 2 3 4 5
5
9 8 7 6 5
12
23 23 22 22 13 3 5 5 3 -3
-7 -3
W3sicHJvYmxlbV9pZCI6IjI2OTYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM5MTFcdWM1NTlcdWFjMTIgXHVhZDZjXHVkNTU4XHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWM1YjRcdWI1YTQgXHVjMjE4XHVjNWY0XHVjNzQ0IFx1Yzc3ZFx1YWNlMCwgXHVkNjQwXHVjMjE4XHViYzg4XHVjOWY4IFx1YzIxOFx1Yjk3YyBcdWM3N2RcdWM3NDQgXHViNTRjIFx1YjljOFx1YjJlNCwgXHVjOWMwXHVhZTA4XHVhZTRjXHVjOWMwIFx1Yzc4NVx1YjgyNVx1YmMxYlx1Yzc0MCBcdWFjMTJcdWM3NTggXHVjOTExXHVjNTU5XHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWMyMThcdWM1ZjRcdWM3NzQgMSw1LDQsMywyIFx1Yzc3NFx1YmE3NCwgXHVkNjQwXHVjMjE4XHViYzg4XHVjOWY4IFx1YzIxOFx1YjI5NCAxXHViYzg4XHVjOWY4IFx1YzIxOCwgM1x1YmM4OFx1YzlmOCBcdWMyMTgsIDVcdWJjODhcdWM5ZjggXHVjMjE4XHVjNzc0XHVhY2UwLCAxXHViYzg4XHVjOWY4IFx1YzIxOFx1Yjk3YyBcdWM3N2RcdWM1YzhcdWM3NDQgXHViNTRjIFx1YzkxMVx1YzU1OVx1YWMxMlx1Yzc0MCAxLCAzXHViYzg4XHVjOWY4IFx1YzIxOFx1Yjk3YyBcdWM3N2RcdWM1YzhcdWM3NDQgXHViNTRjXHViMjk0IDQsIDVcdWJjODhcdWM5ZjggXHVjMjE4XHViOTdjIFx1Yzc3ZFx1YzVjOFx1Yzc0NCBcdWI1NGNcdWIyOTQgM1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuIiwiaW5wdXQiOiI8cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFQoMSZsdDs9VCZsdDs9MSwwMDApXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMyMThcdWM1ZjRcdWM3NTggXHVkMDZjXHVhZTMwIE0oMSZsdDs9TSZsdDs9OTk5OSwgTT1cdWQ2NDBcdWMyMTgpXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljMFx1YWNlMCwgXHVhZGY4IFx1YjJlNFx1Yzc0YyBcdWM5MDRcdWJkODBcdWQxMzAgXHVjNzc0IFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWM2ZDBcdWMxOGNcdWFjMDAgXHVjYzI4XHViODQwXHViMzAwXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNmQwXHVjMThjXHViMjk0IFx1ZDU1YyBcdWM5MDRcdWM1ZDAgMTBcdWFjMWNcdWM1MjkgXHViMDk4XHViMjA0XHVjNWI0XHVjODM4XHVjNzg4XHVhY2UwLCAzMlx1YmU0NFx1ZDJiOCBcdWJkODBcdWQ2MzhcdWM3ODhcdWIyOTQgXHVjODE1XHVjMjE4XHVjNzc0XHViMmU0LiAoXHViMzAwXHViZDgwXHViZDg0XHVjNzU4IFx1YzViOFx1YzViNFx1YzVkMFx1YzExYyBpbnQpPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjZDljXHViODI1XHVkNTU4XHViMjk0IFx1YzkxMVx1YzU1OVx1YWMxMlx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHVhY2UwLCBcdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDY0MFx1YzIxOCBcdWJjODhcdWM5ZjggXHVjMjE4XHViOTdjIFx1Yzc3ZFx1Yzc0NCBcdWI1NGMgXHViOWM4XHViMmU0IFx1YWQ2Y1x1ZDU1YyBcdWM5MTFcdWM1NTlcdWFjMTJcdWM3NDQgXHVjYzI4XHViODQwXHViMzAwXHViODVjIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWQ1NThcdWM1ZWMgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1ZDU1YyBcdWM5MDRcdWM1ZDAgMTBcdWFjMWNcdWM1MjkgXHVjZDljXHViODI1XHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyNjk2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUnVubmluZyBNZWRpYW4iLCJkZXNjcmlwdGlvbiI6IjxwPkZvciB0aGlzIHByb2JsZW0sIHlvdSB3aWxsIHdyaXRlIGEgcHJvZ3JhbSB0aGF0IHJlYWRzIGluIGEgc2VxdWVuY2Ugb2YgMzItYml0IHNpZ25lZCBpbnRlZ2Vycy4gQWZ0ZXIgZWFjaCBvZGQtaW5kZXhlZCB2YWx1ZSBpcyByZWFkLCBvdXRwdXQgdGhlIG1lZGlhbiAobWlkZGxlIHZhbHVlKSBvZiB0aGUgZWxlbWVudHMgcmVjZWl2ZWQgc28gZmFyLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgYSBzaW5nbGUgaW50ZWdlciBQLCAoMSAmbGU7IFAgJmxlOyAxMDAwKSwgd2hpY2ggaXMgdGhlIG51bWJlciBvZiBkYXRhIHNldHMgdGhhdCBmb2xsb3cuIFRoZSBmaXJzdCBsaW5lIG9mIGVhY2ggZGF0YSBzZXQgY29udGFpbnMgdGhlIGRhdGEgc2V0IG51bWJlciwgZm9sbG93ZWQgYnkgYSBzcGFjZSwgZm9sbG93ZWQgYnkgYW4gb2RkIGRlY2ltYWwgaW50ZWdlciBNLCAoMSAmbGU7IE0gJmxlOyA5OTk5KSwgZ2l2aW5nIHRoZSB0b3RhbCBudW1iZXIgb2Ygc2lnbmVkIGludGVnZXJzIHRvIGJlIHByb2Nlc3NlZC4gVGhlIHJlbWFpbmluZyBsaW5lKHMpIGluIHRoZSBkYXRhc2V0IGNvbnNpc3RzIG9mIHRoZSB2YWx1ZXMsIDEwIHBlciBsaW5lLCBzZXBhcmF0ZWQgYnkgYSBzaW5nbGUgc3BhY2UuIFRoZSBsYXN0IGxpbmUgaW4gdGhlIGRhdGFzZXQgbWF5IGNvbnRhaW4gbGVzcyB0aGFuIDEwIHZhbHVlcy4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBkYXRhIHNldCB0aGUgZmlyc3QgbGluZSBvZiBvdXRwdXQgY29udGFpbnMgdGhlIGRhdGEgc2V0IG51bWJlciwgYSBzaW5nbGUgc3BhY2UgYW5kIHRoZSBudW1iZXIgb2YgbWVkaWFucyBvdXRwdXQgKHdoaWNoIHNob3VsZCBiZSBvbmUtaGFsZiB0aGUgbnVtYmVyIG9mIGlucHV0IHZhbHVlcyBwbHVzIG9uZSkuIFRoZSBvdXRwdXQgbWVkaWFucyB3aWxsIGJlIG9uIHRoZSBmb2xsb3dpbmcgbGluZXMsIDEwIHBlciBsaW5lIHNlcGFyYXRlZCBieSBhIHNpbmdsZSBzcGFjZS4gVGhlIGxhc3QgbGluZSBtYXkgaGF2ZSBsZXNzIHRoYW4gMTAgZWxlbWVudHMsIGJ1dCBhdCBsZWFzdCAxIGVsZW1lbnQuIFRoZXJlIHNob3VsZCBiZSBubyBibGFuayBsaW5lcyBpbiB0aGUgb3V0cHV0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

ACM-ICPC > Regionals > North America > Greater New York Region > 2009 Greater New York Programming Contest D번

  • 문제를 번역한 사람: baekjoon
  • 잘못된 데이터를 찾은 사람: tncks0121