4E. 국왕성 방어 작전 (Castle-Defend-Operation)

문제

인덱스국 전쟁사 : Day 4

모든 무기를 모아 싸워도 부족한 판에 무기들을 정확히 반으로 나누어 싸우던 인덱스국의 군대는 패배를 거듭했고, 수도가 함락당하는 지경에 이르렀습니다. 인덱스국의 두 장군 유신장군과 돌장군은 최후의 보루인 국왕성을 보호하기 위해 국왕성을 몇 개의 구역으로 나누어 각자 담당하기로 하였습니다. 국왕성은 직육면체 모양으로, X × Y × Z 크기를 가집니다. 두 장군은 우선 국왕성을 3차원 직교좌표계로 표현했습니다. 국왕성의 한 꼭짓점을 원점으로 두고, 국왕성 8개의 모서리가 모두 축과 평행하며, 국왕성 내부의 어떤 점도 좌표가 음수가 되지 않도록 조정했습니다. 이제 국왕성을 모든 모서리가 축과 평행한 1 × 1 × 1 크기의 정육면체 구역들로 나누고, (x + 0.2, y + 0.7, z + 0.4)를 포함하는 구역을 $A_{x,y,z}$ 로 부르기로 했습니다.

두 구역 $A_{x,y,z}$ 와 $A_{a,b,c}$ 가 인접했다는 것은, 걸어서 바로 이동할 수 있거나, 국왕성의 경계에 있는 포탈을 이용하여 이동할 수 있는 두 구역을 말합니다. (정확히 말하면, min(|x − a|, X − |x − a|) + min(|y − b|, Y − |y − b|) + min(|z − c|, Z − |z − c|) = 1인 경우 두 구역이 인접합니다.) 구역 $A_{x,y,z}$ 의 평균 온도는 $T_{x,y,z}$ 입니다. 유신장군은 찬 곳을 좋아하고, 돌장군은 따뜻한 곳을 좋아하기 때문에, 이 구역의 행복도 $H_{x,y,z}$ 는 유신장군의 구역에서 $−T_{x,y,z}$ 이고, 돌장군의 구역에서 $T_{x,y,z}$ 입니다. (검열됨)은 매우 인성이 터진 국왕으로, 매우 이상한 조건에 만족을 느낍니다.

산책 도중 인접한 두 구역 사이를 이동할 때마다 만족도를 얻는데, 인접한 두 구역 $A_{x,y,z}$ 와 $A_{a,b,c}$ 에 대해서, $|H_{x,y,z} − H_{a,b,c}|$ 의 만족도를 얻습니다.

두 장군은 구역을 나누기 위해 국왕 (검열됨)에게 조언을 구했습니다. 간신들의 입막음으로 수도가 함락되었다는 사실도 모르는 (검열됨)은 매일 성 산책을 다닙니다. 같은 구역을 두 번 지나지 않는 모든 경로들의 집합을 S라고 했을 때, S의 모든 경로들은 각각 $\frac{1}{|S|}$ 의 확률로 오늘의 산책으로 선정됩니다. (검열됨)은 이 산책의 만족도의 기댓값이 최대가 되도록 두 장군에게 구역을 배정하려고 합니다.

구현 세부 사항

다음 함수를 구현하세요.

void assignArea(int X, int Y, int Z)

이 함수는 처음 단 한 번 그레이더에 의해 호출됩니다.
X, Y, Z는 국왕성의 크기를 나타내는 정수입니다.

assignArea는 다음 함수들을 호출할 수 있습니다.

int temperature(int x, int y, int z)

assignArea는 이 함수를 사용해서 입력을 받습니다.
0 ≤ x < X, 0 ≤ y < Y, 0 ≤ z < Z를 만족해야 합니다.
이 함수는 $T_{x,y,z}$ 를 반환합니다.

void assign(int x, int y, int z, int g)

assignArea는 이 함수를 사용해서 출력합니다.
0 ≤ x < X, 0 ≤ y < Y, 0 ≤ z < Z, g = 0, 1을 만족해야 합니다.
같은 (x, y, z)로 이 함수를 여러번 호출해서는 안됩니다.
$A_{x,y,z}$ 는 g = 0일 경우 유신장군의 구역, g = 1일 경우 돌장군의 구역으로 배정됩니다.

제한 조건

1 ≤ X, Y, Z ≤ 300,000
X, Y 는 짝수이고, Z는 짝수이거나 1입니다.
V = XYZ ≤ 300,000
$|T_{x,y,z}|$ ≤ 100,000 (0 ≤ x < X, 0 ≤ y < Y, 0 ≤ z < Z)

서브태스크

서브태스크	점수	제한 조건
1	6	`V` ≤ 20
2	7	`Z` = 1
3	5	`X`, `Y`, `Z` ≤ 300
4	2	추가 제한 조건 없음

예제 입출력

X = 2, Y = 2, Z = 2

그레이더는 다음 함수를 호출합니다.

assignArea(2, 2, 2)

assignArea는 다음 함수를 호출하여 입력을 받습니다.

temperature(0, 0, 0) = 30

temperature(0, 0, 1) = 2

temperature(0, 1, 0) = -1

temperature(0, 1, 1) = 0

temperature(1, 0, 0) = 70

temperature(1, 0, 1) = -10

temperature(1, 1, 0) = -60

temperature(1, 1, 1) = 5

assignArea는 다음 함수를 호출하여 답을 출력합니다.

assign(0, 0, 0, 1)

assign(0, 0, 1, 0)

assign(0, 1, 0, 1)

assign(0, 1, 1, 0)

assign(1, 0, 0, 0)

assign(1, 0, 1, 0)

assign(1, 1, 0, 0)

assign(1, 1, 1, 0)

샘플 그레이더

Sample Grader는 다음과 같은 형식으로 입력을 받습니다.

line 1 : X Y Z
line 2 + Yi + j (0 ≤ i ≤ X − 1, 0 ≤ j ≤ Y − 1) : $T_{i,j,0}, T_{i,j,1}, \cdots, T_{i,j,Z−1}$