정령과 눈 감고 숨바꼭질 게임

제한 시간 1000 ms, 메모리 제한 1024 MB.

Semia와 친구 9명이 놀이터에서 눈을 감고 숨바꼭질을 하고 있다. 술래는 눈을 감은 채 놀이터 곳곳에 숨은 나머지 9명을 찾아낸다. 놀이터는 $200 \times 200$ 크기의 격자이다. 격자의 $i$행 $j$열 칸은 $(i, j)$로 표기한다. $(0 \le i, j \le 199)$

게임이 시작되기 전에 술래를 제외한 9명이 격자에서 칸을 하나씩 골라 숨는다. 한 칸에 여러 명이 숨을 수도 있다. 이후 술래는 중앙의 $100 \times 100$ 크기 격자 안 무작위 위치에서 친구들을 찾기 시작한다. 코끼리 코를 격렬하게 돌리기 때문에 술래는 자신이 시작한 위치를 정확히 알지 못한다. 다만 술래의 시작 위치 $(i_{0}, j_{0})$는 $50 \le i_{0}, j_{0} \le 149$를 만족함이 보장된다.

나머지 9명의 위치를 $(i_{k}, j_{k})$ $(1 \le k \le 9)$라고 하자. 술래가 너무 빨리 들키지 않도록, 모든 $1 \le k \le 9$에 대해 $|i_{k} - i_{0}| > 1$이고 $|j_{k} - j_{0}| > 1$일 때만 게임이 정상적으로 시작된다. 그렇지 않으면 게임을 다시 시작하므로 이 경우는 고려하지 않아도 된다.

이번 게임에서는 Semia가 술래다. Semia는 친구들을 찾기 전에 남몰래 정령을 불러내 도움을 받으려 한다. 정령은 나머지 9명이 숨은 위치를 보고 놀이터의 모든 격자 칸에 양의 정수를 적는다. 정령은 1부터 24까지의 수만 알기 때문에 1 이상 24 이하의 정수만 적을 수 있다.

Semia는 정령이 적은 수를 이용해 나머지 9명의 위치를 파악한다. Semia는 마나를 써서 다음 두 능력을 사용할 수 있다. 두 능력 모두 마나를 많이 소모하므로 사용할 수 있는 횟수가 각각 제한되어 있다.

• Find x. 값 $x$가 적힌 격자 중 유클리드 거리로 가장 가까운 격자의 위치를, 현재 위치를 기준으로 한 상대 좌표로 알 수 있다. 그 격자가 $(u, v)$라면 Semia는 $(u - i_{0}, v - j_{0})$를 알게 된다. 이 능력은 최대 한 번 사용할 수 있다. 가장 가까운 격자가 여러 개라면 그중 한 칸의 좌표만 알 수 있다.
• Get x y. Semia 기준 상대 좌표가 $(x, y)$인 위치, 즉 $(i_{0} + x, j_{0} + y)$에 적힌 값을 알 수 있다. 이때 $|x| \leq 1$이고 $|y| \leq 1$이어야 한다. 이 능력은 최대 네 번 사용할 수 있다.

Semia는 나머지 9명이 각각 자신의 시작 위치를 원점으로 한 사분면 중 어디에 있는지 구하려 한다. 사분면은 다음과 같이 번호를 붙인다.

• $i - i_{0} > 0$이고 $j - j_{0} > 0$이면 $(i, j)$는 1사분면에 속한다.
• $i - i_{0} < 0$이고 $j - j_{0} > 0$이면 $(i, j)$는 2사분면에 속한다.
• $i - i_{0} < 0$이고 $j - j_{0} < 0$이면 $(i, j)$는 3사분면에 속한다.
• $i - i_{0} > 0$이고 $j - j_{0} < 0$이면 $(i, j)$는 4사분면에 속한다.
• $i - i_{0}$, $j - j_{0}$ 중 하나 이상이 0이면 이 문제에서는 고려하지 않아도 된다.

Semia와 정령의 전략을 각각 구현해 보자.

pair<int, int> Find(int x)

• 값 $x$가 적힌 격자 중 유클리드 거리로 가장 가까운 격자의 Semia 기준 상대 좌표를 반환한다. 가장 가까운 격자가 여러 개라면 그중 무작위로 고른 하나의 값을 반환한다.
• 정령이 칸에 적은 값 중에 $x$가 반드시 있어야 한다. 그렇지 않으면 "틀렸습니다"를 받는다.
• 이 함수를 1번보다 많이 호출하면 "틀렸습니다"를 받는다.

int Get(int x, int y)

• Semia 기준 상대 좌표가 $(x, y)$인 위치에 적힌 값을 반환한다.
• $|x| \leq 1$, $|y| \leq 1$을 만족하지 않으면 "틀렸습니다"를 받는다.
• 이 함수를 4번보다 많이 호출하면 "틀렸습니다"를 받는다.

구현해야 하는 함수는 다음 두 가지다.

vector< vector<int> > play_spirit(vector< pair<int, int> > &hider_positions)

• 인자 hider_positions의 크기는 9이다. $i$번째 원소는 $i$번째 숨은 사람의 좌표다. ($0 \leq i \leq 8$)
• $200 \times 200$ 크기의 2차원 배열을 반환해야 한다. $i$번째 배열의 $j$번째 원소는 정령이 $(i, j)$ 좌표에 적을 값이며, 1 이상 24 이하여야 한다.

vector<int> play_semia()

• Find 함수는 최대 1번, Get 함수는 최대 4번 호출할 수 있다.
• 길이 9의 배열을 반환한다. $i$번째 값은 $i$번 사람이 숨어 있는 사분면 번호다.

제출한 소스 코드의 어느 부분에서도 입출력 함수를 실행해서는 안 된다. 각 테스트 케이스에 대해 프로그램은 정확히 두 번 실행된다.

첫 번째 실행에서는 play_spirit이 호출되고, 그 실행 결과가 채점 시스템에 저장된다. 이때 play_semia는 호출되지 않는다.

두 번째 실행에서는 play_semia가 호출된다. play_semia가 호출하는 Find와 Get의 반환 값은 앞선 play_spirit 실행 결과에 따라 정해진다. 이때 play_spirit은 호출되지 않는다.

이 문제의 실행 시간과 메모리 사용량은 두 번의 실행을 합하여 계산한다.

그레이더는 두 번의 실행에서 다음과 같이 입출력을 수행한다. 그레이더를 포함한 파일은 providing.zip에 들어 있다. 코드는 sol_template.cpp에 작성한 뒤 로컬에서 컴파일해 볼 수 있다.

첫 번째 실행의 입력은 다음과 같다.

• 1번째 줄: Semia의 위치를 나타내는 두 정수
• 2번째 줄부터 10번째 줄: 친구들의 위치를 나타내는 두 정수

첫 번째 실행의 출력이자 두 번째 실행의 입력은 다음과 같다.

• 1번째 줄부터 200번째 줄: 정령이 각 격자 칸에 적은 정수
• 201번째 줄: Semia의 위치를 나타내는 두 정수

두 번째 실행에서 그레이더는 play_semia의 반환 값을 공백으로 구분하여 한 줄에 출력한다.