시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB112266.667%

문제

오늘은 선우의 생일이다. 성훈이와 희승이는 선우를 위해 선물을 준비하려고 한다. 둘은 우선 짝수 $N$을 골라 선우의 선물로 고려할 후보 $N$개를 선택하였다. 희승이는 정해진 $N$가지 선물 후보의 우선순위를 자신의 취향대로 미리 정해놓았다. 성훈이와 희승이는 다음과 같은 방식으로 $N/2$가지 선물을 고르려고 한다.

  1. 성훈이는 선우의 선물 취향을 예측해서 $N$가지 선물 후보의 우선순위를 정한다.
  2. $N$가지 선물 후보를 일렬로 나열한다.
  3. 4번과 5번 과정을 번갈아서 $N/2$번 반복한다.
  4. 희승이가 남아있는 선물 후보 중에서 본인 기준 우선순위가 가장 낮은 것을 제외한다.
  5. 성훈이는 남아있는 선물 후보 중에서 본인 기준 우선순위가 가장 높은 것을 선택한다.

곧 있으면 희승이의 생일도 다가오기 때문에 성훈이는 선우의 선물을 고르는 척 희승이의 취향을 확인하려고 한다. 성훈이가 선우의 선물 취향을 다양하게 예측하여 희승이와 함께 선물을 선택한 다음, 결과를 가지고 희승이의 취향을 예측하려고 한다. 시간이 얼마 없기 때문에 성훈이는 희승이와 같이 최대 $2\,048$번 선물을 고르려고 한다. 성훈이를 도와 희승이의 취향을 구하는 프로그램을 작성하여라.

함수 목록 및 정의

여러분은 아래 함수를 구현해야 한다. 선물의 번호는 $0$이상 $N-1$이하 정수이다.

int[] estimate_favor(int N)
  • $N$: 성훈이와 희승이가 고르려는 선물 후보의 수
  • 이 함수는 크기가 $N$인 배열 $F$를 반환해야 한다. $F[i]$는 희승이가 $i +1$번째로 좋아하는 선물의 번호이다.

여러분은 아래 함수를 호출할 수 있다.

int[] choose_gift(int[] S)
  • $S$: 길이가 $N$인 배열. $S$는 $\{i | 0 ≤ i < N\}$의 순열이어야 한다.
  • 이 함수는 성훈이가 $i +1$번째로 좋아하는 선물의 번호를 $S[i]$로 정한 다음 희승이와 같이 선물을 골랐을 때 골라진 선물의 번호를 오름차순으로 정렬한 길이 $N/2$짜리 배열을 반환한다.
  • 이 함수는 최대 $2\,048$번 호출 가능하다.
  • 함수를 제한 횟수보다 많이 호출하거나 잘못된 인자로 호출한 경우 프로그램이 즉시 종료되며 틀렸습니다를 받게 된다.

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

서브태스크

모든 데이터에 대해서, $2 ≤ N ≤ 2\,048$; $N \equiv 0 \pmod 2$를 만족한다.

번호배점제한
11

$N ≤ 64$

21

$N ≤ 256$

31

추가 제약조건은 없다.

예제 1

희승이의 취향 F = [0, 4, 2, 1, 3, 5]인 경우를 생각해보자. 그레이더는 estimate_favor(6)을 호출한다. 여러분이 choose_gift([5, 4, 3, 2, 1, 0])를 호출했다면 다음과 같이 선물을 고르게 된다.

  1. 희승이가 $5$번 선물을 제외한다.
  2. 성훈이가 $4$번 선물을 선택한다.
  3. 희승이가 $3$번 선물을 제외한다.
  4. 성훈이가 $2$번 선물을 선택한다.
  5. 희승이가 $1$번 선물을 제외한다.
  6. 성훈이가 $0$번 선물을 선택한다.

따라서 해당 함수의 반환값은 [0, 2, 4]이다.

여러분이 choose_gift([3, 1, 4, 0, 2, 5])를 호출한다면 반환값은 [0, 3, 4]가 된다.

여러분은 estimate_favor 함수의 반환값으로 [0, 4, 2, 1, 3, 5]를 반환해야 한다.

샘플 그레이더

샘플 그레이더는 첫 번째 줄에 $N$을 입력받는다. 두 번째 줄에는 희승이의 취향 $F[i]$에 해당하는 $N$개의 정수를 입력받는다.

샘플 그레이더는 여러분이 구현한 함수가 올바르게 동작했는지 여부를 출력한다.

실제 채점에서 사용하는 그레이더는 샘플 그레이더와 다를 수 있음에 유의하라. 그레이더는 비적응적(non-adaptive)으로 처음에 정한 $F$의 값을 여러분의 함수 호출 상황에 따라 바꾸지 않는다.

출처

Contest > BOJ User Contest > FunctionCup > FunctionCup 2023 EF번

제출할 수 있는 언어

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

채점 및 기타 정보

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