아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

Let's Play Curling

시간 제한1초메모리 제한512 MB

요약
수직선 위에 놓인 빨강 돌과 파랑 돌의 위치가 주어질 때, 모든 파랑 돌보다 c에 더 가까운 빨강 돌의 수가 최대가 되는 중심 c를 찾아 그 최댓값을 구하거나 불가능하면 Impossible을 출력한다.
난이도

보통10점 중 5점

유형
정렬, 그리디, 수학, 배열
정답자
아직 제출이 없습니다

문제

컬링은 선수들이 얼음판 위에서 스톤을 목표 영역을 향해 미끄러뜨리는 스포츠이다. 목표 영역의 중심에 가장 가까운 스톤을 가진 팀이 경기에서 승리한다.

두 팀 Red와 Blue가 수직선 위에서 겨루고 있다. 경기가 끝난 뒤 수직선 위에는 (n+m)(n+m)개의 스톤이 남아 있고, 그중 nn개는 Red 팀, 나머지 mm개는 Blue 팀의 것이다. Red 팀의 ii번째 스톤은 aia_i에, Blue 팀의 ii번째 스톤은 bib_i에 있다.

목표 영역의 중심 위치를 cc라 하자. 위 설명에서 알 수 있듯이, 1≤i≤n1 \le i \le n인 어떤 ii가 존재하여 모든 1≤j≤m1 \le j \le m에 대해 ∣c−ai∣<∣c−bj∣|c - a_i| < |c - b_j|이면 Red가 경기에서 승리한다. 또한 이 조건을 만족하는 ii의 개수가 정확히 pp개이면 Red가 pp점을 얻는다고 한다.

Red 팀과 Blue 팀 스톤의 위치가 주어질 때, Red가 승리하면서 최대한 많은 점수를 얻도록 목표 영역의 중심 위치 cc를 정해야 한다. cc는 정수일 필요가 없고 어떤 실수든 될 수 있다.

입력

입력은 여러 테스트 케이스로 이루어진다. 입력의 첫 줄에는 테스트 케이스의 개수를 나타내는 정수 TT가 주어진다. 각 테스트 케이스는 다음과 같다.

첫 줄에는 Red의 스톤 개수와 Blue의 스톤 개수를 나타내는 두 정수 nn과 mm이 주어진다. (1≤n,m≤1051 \le n, m \le 10^5)

둘째 줄에는 Red의 스톤 위치를 나타내는 nn개의 정수 a1,a2,⋯ ,ana_1, a_2, \cdots, a_n이 주어진다. (1≤ai≤1091 \le a_i \le 10^9)

셋째 줄에는 Blue의 스톤 위치를 나타내는 mm개의 정수 b1,b2,⋯ ,bmb_1, b_2, \cdots, b_m이 주어진다. (1≤bi≤1091 \le b_i \le 10^9)

nn의 합과 mm의 합은 각각 5×1055 \times 10^5를 넘지 않는다.

출력

각 테스트 케이스마다 한 줄을 출력한다. Red가 승리하면서 최대한 많은 점수를 얻도록 하는 cc가 존재하면 Red가 얻을 수 있는 최대 점수를 나타내는 정수 하나를 출력한다. (cc가 아니다.) 그렇지 않으면 "Impossible"을 큰따옴표 없이 출력한다.

힌트

첫 번째 예시 테스트 케이스에서는 c=2.5c = 2.5로 두면 위치 2와 3에 있는 Red의 스톤이 득점한다.

두 번째 예시 테스트 케이스에서는 c=7c = 7로 두면 위치 5와 7에 있는 Red의 스톤이 득점한다.

예제1

  1. 예제 1

    입력
    3
    2 2
    2 3
    1 4
    6 5
    2 5 3 7 1 7
    3 4 3 1 10
    1 1
    7
    7
    
    예상 출력
    2
    3
    Impossible