시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB82903909306249.451%

문제

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

예를 들어, 수열이 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비트 부호있는 정수이다.

출력

각 테스트 케이스에 대해 첫째 줄에 출력하는 중앙값의 개수를 출력하고, 둘째 줄에는 홀수 번째 수를 읽을 때 마다 구한 중앙값을 차례대로 공백으로 구분하여 출력한다. 이때, 한 줄에 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
W3sicHJvYmxlbV9pZCI6IjI2OTYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM5MTFcdWM1NTlcdWFjMTIgXHVhZDZjXHVkNTU4XHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM1YjRcdWI1YTQgXHVjMjE4XHVjNWY0XHVjNzQ0IFx1Yzc3ZFx1YWNlMCwgXHVkNjQwXHVjMjE4XHViYzg4XHVjOWY4IFx1YzIxOFx1Yjk3YyBcdWM3N2RcdWM3NDQgXHViNTRjIFx1YjljOFx1YjJlNCwgXHVjOWMwXHVhZTA4XHVhZTRjXHVjOWMwIFx1Yzc4NVx1YjgyNVx1YmMxYlx1Yzc0MCBcdWFjMTJcdWM3NTggXHVjOTExXHVjNTU5XHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWMyMThcdWM1ZjRcdWM3NzQgMSwgNSwgNCwgMywgMiBcdWM3NzRcdWJhNzQsIFx1ZDY0MFx1YzIxOFx1YmM4OFx1YzlmOCBcdWMyMThcdWIyOTQgMVx1YmM4OFx1YzlmOCBcdWMyMTgsIDNcdWJjODhcdWM5ZjggXHVjMjE4LCA1XHViYzg4XHVjOWY4IFx1YzIxOFx1Yzc3NFx1YWNlMCwgMVx1YmM4OFx1YzlmOCBcdWMyMThcdWI5N2MgXHVjNzdkXHVjNWM4XHVjNzQ0IFx1YjU0YyBcdWM5MTFcdWM1NTlcdWFjMTJcdWM3NDAgMSwgM1x1YmM4OFx1YzlmOCBcdWMyMThcdWI5N2MgXHVjNzdkXHVjNWM4XHVjNzQ0IFx1YjU0Y1x1YjI5NCA0LCA1XHViYzg4XHVjOWY4IFx1YzIxOFx1Yjk3YyBcdWM3N2RcdWM1YzhcdWM3NDQgXHViNTRjXHViMjk0IDNcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFQoMSAmbGU7IFQgJmxlOyAxLDAwMClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWQwNmNcdWFlMzAgTSgxICZsZTsgTSAmbGU7IDk5OTksIE1cdWM3NDAgXHVkNjQwXHVjMjE4KVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWFjZTAsIFx1YWRmOCBcdWIyZTRcdWM3NGMgXHVjOTA0XHViZDgwXHVkMTMwIFx1Yzc3NCBcdWMyMThcdWM1ZjRcdWM3NTggXHVjNmQwXHVjMThjXHVhYzAwIFx1Y2MyOFx1Yjg0MFx1YjMwMFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzZkMFx1YzE4Y1x1YjI5NCBcdWQ1NWMgXHVjOTA0XHVjNWQwIDEwXHVhYzFjXHVjNTI5IFx1YjA5OFx1YjIwNFx1YzViNFx1YzgzOFx1Yzc4OFx1YWNlMCwgMzJcdWJlNDRcdWQyYjggXHViZDgwXHVkNjM4XHVjNzg4XHViMjk0IFx1YzgxNVx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzQgXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWNkOWNcdWI4MjVcdWQ1NThcdWIyOTQgXHVjOTExXHVjNTU5XHVhYzEyXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWFjZTAsIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkNjQwXHVjMjE4IFx1YmM4OFx1YzlmOCBcdWMyMThcdWI5N2MgXHVjNzdkXHVjNzQ0IFx1YjU0YyBcdWI5YzhcdWIyZTQgXHVhZDZjXHVkNTVjIFx1YzkxMVx1YzU1OVx1YWMxMlx1Yzc0NCBcdWNjMjhcdWI4NDBcdWIzMDBcdWI4NWMgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1ZDU1OFx1YzVlYyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1Yzc3NFx1YjU0YywgXHVkNTVjIFx1YzkwNFx1YzVkMCAxMFx1YWMxY1x1YzUyOSBcdWNkOWNcdWI4MjVcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjI2OTYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJSdW5uaW5nIE1lZGlhbiIsImRlc2NyaXB0aW9uIjoiPHA+Rm9yIHRoaXMgcHJvYmxlbSwgeW91IHdpbGwgd3JpdGUgYSBwcm9ncmFtIHRoYXQgcmVhZHMgaW4gYSBzZXF1ZW5jZSBvZiAzMi1iaXQgc2lnbmVkIGludGVnZXJzLiBBZnRlciBlYWNoIG9kZC1pbmRleGVkIHZhbHVlIGlzIHJlYWQsIG91dHB1dCB0aGUgbWVkaWFuIChtaWRkbGUgdmFsdWUpIG9mIHRoZSBlbGVtZW50cyByZWNlaXZlZCBzbyBmYXIuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBhIHNpbmdsZSBpbnRlZ2VyIFAsICgxICZsZTsgUCAmbGU7IDEwMDApLCB3aGljaCBpcyB0aGUgbnVtYmVyIG9mIGRhdGEgc2V0cyB0aGF0IGZvbGxvdy4gVGhlIGZpcnN0IGxpbmUgb2YgZWFjaCBkYXRhIHNldCBjb250YWlucyBhbiBvZGQgZGVjaW1hbCBpbnRlZ2VyIE0sICgxICZsZTsgTSAmbGU7IDk5OTkpLCBnaXZpbmcgdGhlIHRvdGFsIG51bWJlciBvZiBzaWduZWQgaW50ZWdlcnMgdG8gYmUgcHJvY2Vzc2VkLiBUaGUgcmVtYWluaW5nIGxpbmUocykgaW4gdGhlIGRhdGFzZXQgY29uc2lzdHMgb2YgdGhlIHZhbHVlcywgMTAgcGVyIGxpbmUsIHNlcGFyYXRlZCBieSBhIHNpbmdsZSBzcGFjZS4gVGhlIGxhc3QgbGluZSBpbiB0aGUgZGF0YXNldCBtYXkgY29udGFpbiBsZXNzIHRoYW4gMTAgdmFsdWVzLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIGRhdGEgc2V0IHRoZSBmaXJzdCBsaW5lIG9mIG91dHB1dCBjb250YWlucyB0aGUgbnVtYmVyIG9mIG1lZGlhbnMgb3V0cHV0ICh3aGljaCBzaG91bGQgYmUgb25lLWhhbGYgdGhlIG51bWJlciBvZiBpbnB1dCB2YWx1ZXMgcGx1cyBvbmUpLiBUaGUgb3V0cHV0IG1lZGlhbnMgd2lsbCBiZSBvbiB0aGUgZm9sbG93aW5nIGxpbmVzLCAxMCBwZXIgbGluZSBzZXBhcmF0ZWQgYnkgYSBzaW5nbGUgc3BhY2UuIFRoZSBsYXN0IGxpbmUgbWF5IGhhdmUgbGVzcyB0aGFuIDEwIGVsZW1lbnRzLCBidXQgYXQgbGVhc3QgMSBlbGVtZW50LiBUaGVyZSBzaG91bGQgYmUgbm8gYmxhbmsgbGluZXMgaW4gdGhlIG91dHB1dC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

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