시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB65583.333%

문제

건축가 제이크는 우주 배달 사업에 대하여 영감을 얻어 스타트업 스타티링크(Star-T-Link)를 창업하였다. 제이크는 우주에 $N$개의 비콘을 설치하여 $N+2$개 단말 행성 간 택배를 배달하려고 한다. 비콘과 단말 행성 간 네트워크 구성은 처음 구축할 때 고정되어 바뀌지 않는다. 편의상 모든 비콘과 단말 행성을 통틀어서 노드라 부르자. 이때 네트워크는 아래 규칙을 만족한다.

  • 모든 비콘은 정확히 $3$개의 노드와 직접 연결되어야 한다.
  • 모든 단말 행성은 정확히 하나의 비콘과 직접 연결되어야 한다.
  • 네트워크가 모든 노드를 직ㆍ간접적으로 연결해야 한다.

제이크는 단말 행성에는 $-(N+2)$ 이상 $-1$ 이하의 정수 번호를, 비콘에는 $0$ 이상 $N-1$ 이하의 정수 번호를 매겼다. 비콘과 단말 행성 간 네트워크 구성으로 가능한 예는 아래 그림과 같다.

우주 공간 안에 있는 $N$개의 비콘은 수시로 암흑 물질의 영향을 받아 택배 서비스의 성능이 다소 불안정해질 수 있다. 따라서 제이크는 아래와 같은 방식으로 작동하는 프로토콜을 설계하였다.

  • 비콘 $i$($0 \leq i < N$)와 연결된 노드의 번호를 $C_i [0]$, $C_i [1]$, $C_i [2]$라고 하자.
  • 각 비콘에 대하여 정책 $R_i [0]$, $R_i [1]$, $R_i [2]$를 $0$ 이상 $2$ 이하의 정수로 미리 정하자. $R_i [j]$는 $j$와 달라야 한다.
  • 모든 단말 행성에서 비콘으로 편지 각 $1$장을 배달한다.
  • $C_i [j]$($0 \leq j \leq 2$)번 노드에서 비콘 $i$로 온 편지가 있다고 하자. $i$번 비콘이 암흑 물질의 영향을 받고 있다면 해당 편지를 $C_i [R_i [j]]$번 노드로 보내고, 그렇지 않다면 해당 편지를 $C_i [3 - j - R_i [j]]$번 노드로 보낸다.
  • 편지가 단말 행성에 도착한다면 배달이 끝난다.

제이크는 정책 $R$을 적절히 정한다면 각 단말 행성으로 도달하는 편지의 수만 확인해도 $N$개의 비콘이 암흑 물질의 영향을 받고 있는지 확인할 수 있다고 생각하는 것 같다. 제이크의 생각이 맞는지 프로그램으로 확인해보자.

함수 목록 및 정의

여러분은 아래 함수를 구현해야 한다.

int[][] init(int[][] C)
  • $C$: $N \times 3$ 크기의 배열. $C[i][j]$는 비콘 $i$과 연결된 세 노드의 번호를 의미한다. ($0 \leq i < N$)
  • 이 함수는 정책을 의미하는 $N \times 3$ 크기의 배열 $R$을 반환해야 한다. 이 함수는 health_check 함수가 호출되기 전에 한 번 호출된다.
int[] health_check(int[] L)
  • $L$ : $N+2$ 크기의 배열. 각 단말 행성에서 편지를 각 $1$장 배달했을 때, $L[i]$는 $-(i+1)$번 단말 행성으로 도달하는 편지의 수이다. ($0 \leq i < N+2$)
  • 이 함수는 각 비콘의 상태를 의미하는 $N$ 크기의 배열 $H$를 반환해야 한다. $H[i]$는 $i$번 비콘이 암흑 물질의 영향을 받고 있다면 $1$, 그렇지 않다면 $0$이다. ($0 \leq i < N$) 이 함수는 $Q$번 호출된다.

제출하는 소스 코드의 어느 부분에서도 입출력 함수를 실행해서는 안 된다.

서브태스크

모든 데이터에 대해서, $1 ≤ N ≤ 100\,000$; $1 ≤ Q ≤ 10$ 을 만족한다.

번호배점제한
11

$N ≤ 10$

21

$N ≤ 1\,000$

31

추가 제약조건은 없다.

예제 1

네트워크 구성이 본문에 있는 그림과 같은 경우를 생각해보자. 맨 처음에 init([[-1, -2, 1], [0, 2, -3], [1, -4, -5]]])이 호출된다.

제이크가 init 함수에서 정책 $R$ = [[1, 2, 0], [2, 2, 1], [2, 0, 1]]을 반환했다고 하자.

$0, 1, 2$번 비콘 중 $0$번 비콘만 암흑 물질의 영향을 받고 있다면 편지는 다음과 같이 배달된다.

  • $-1$번 단말 행성에서 출발하는 편지는 $0$번 비콘을 거쳐서 $-2$번 단말 행성에 도착한다.
  • $-2$번 단말 행성에서 출발하는 편지는 $0$, $1$, $2$번 비콘을 거쳐서 $-4$번 단말 행성에 도착한다.
  • $-3$번 단말 행성에서 출발하는 편지는 $1$, $0$번 비콘을 거쳐서 $-1$번 단말 행성에 도착한다.
  • $-4$번 단말 행성에서 출발하는 편지는 $2$번 비콘을 거쳐서 $-5$번 단말 행성에 도착한다.
  • $-5$번 단말 행성에서 출발하는 편지는 $1$, $0$번 비콘을 거쳐서 $-1$번 단말 행성에 도착한다.

이런 경우 health_check([2, 1, 0, 1, 1])이 호출되며 [1, 0, 0]을 반환해야 한다.

샘플 그레이더

샘플 그레이더는 첫 번째 줄에 $N$, $Q$를 입력받는다. 두 번째 줄부터 $N$개의 줄에는 $C[i][j]$에 해당하는 정수 $3$개를 입력받는다. 그 다음 줄부터 $Q$개의 줄에는 각 비콘의 상태 $H[i]$에 해당하는 $N$개의 정수를 입력받는다. 채점 프로그램은 해당 값을 이용하여 $L[i]$를 계산한 다음 health_check 함수를 호출한다.

샘플 그레이더는 health_check 함수가 올바른지 여부에 따라 Correct 또는 Wrong을 출력한다.

실제 채점에서 사용하는 그레이더는 샘플 그레이더와 다를 수 있음에 유의하라. 그레이더는 적응적(adaptive)으로 호출할 health_check 함수의 인자가 init 함수의 반환값에 따라 바뀔 수 있다.

출처

Contest > BOJ User Contest > FunctionCup > FunctionCup 2023 ST번

제출할 수 있는 언어

C++17, C++20, C++17 (Clang), C++20 (Clang)

채점 및 기타 정보

  • 예제는 채점하지 않는다.