27320번 - 코코아⋯. 이거 아니라고 언어 제한함수 구현

코코아와 치노는 도서관에서 책을 찾고 있었습니다. 그러다 코코아가 실수로 $2N+1$ 권의 책이 꽂혀있던 책장을 엎어버렸습니다.

다행히 각 책에는 번호가 $1$부터 $2N+1$까지 순서대로 붙어있어서 책이 원래 꽂혀 있던 순서를 알아내는 것은 어렵지 않았습니다.

코코아와 치노는 서로 분담하여 책을 찾기로 했습니다.

코코아는 홀수 번호가 붙어있는 $N+1$ 권의 책, 즉, $1,3,\cdots ,2N+1$의 번호가 붙어있는 책을 찾아놓았고, 치노는 짝수 번호가 붙어있는 $N$ 권의 책, 즉, $2,4,\cdots ,2N$의 번호가 붙어있는 책을 찾아 놓았습니다.

이제부터 코코아와 치노는 코코아부터 시작해 각자가 찾아놓은 책을 번갈아가면서 앞에서부터 꽂으려고 합니다. 코코아가 $i$ 번째에 꽂는 책의 번호를 $A_{i}$라 하고, 치노가 $i$ 번째에 꽂는 책의 번호를 $B_{i}$라 하면, $1\leq i\leq N$인 모든 정수 $i$에 대해서 $A_{i}$ 번 책이 $B_{i}$ 번 책의 앞에 꽂히고, $B_{i}$ 번 책이 $A_{i+1}$ 번 책보다 앞에 꽂힙니다.

코코아는 책을 순서대로 꽂는 것에 그다지 관심이 없습니다. 그래서 한 권의 책을 꽂고 나면, 남아있는 책 중 그때그때 내키는 책 한 권을 다음 꽂을 책으로 골라놓습니다.

치노는 최소한의 순서라도 맞출 수 있도록, 코코아가 골라놓는 책을 확인해가면서 자신이 꽂는 책의 번호가 그 책과 인접해서 코코아가 꽂는 두 권의 책의 번호 사이에 오게 하고자 합니다.

즉, $1\leq i\leq N$인 모든 정수 $i$에 대해서 $A_{i}<B_{i}<A_{i+1}$ 또는 $A_{i}>B_{i}>A_{i+1}$이 성립해야 합니다.

치노가 위와 같은 방법으로 책을 꽂을 수 있도록 방법을 알려주는 프로그램을 작성해 봅시다.

여러분의 프로그램은 제공되는 “books.h”를 include 해야 합니다.

여러분의 프로그램은 다음과 같은 함수를 구현해야 합니다.

• void solve(int N, int P, int Q)
  • N은 본문에서 주어진 $N$을 의미하며, $1\leq N\leq 1\, 000\, 000$입니다.
  • P는 코코아가 $1$ 번째로 꽂은 책의 번호, 즉, $A_{1}$을 의미합니다.
  • Q는 코코아가 $2$ 번째에 꽂기 위해 골라놓은 책의 번호, 즉, $A_{2}$를 의미합니다.
  • 이때, 다음과 같은 조건들이 성립합니다.
    • $1\leq A_1,A_2\leq 2N+1$
    • $A_1,A_2$는 홀수
    • $A_1\neq A_2$
  • 이 함수는 프로그램이 실행될 때 정확히 한 번 호출됩니다.
  • 이 함수가 반환하기 전까지 answer 함수를 정확히 $N$ 번 호출해야 합니다. 그렇지 않으면 틀렸습니다를 받게 됩니다.

여러분의 프로그램은 다음과 같은 함수를 호출할 수 있습니다.

• int answer(int V)
  • 이 함수를 $i$ 번째로 호출할 때, V는 치노가 $i$ 번째로 꽂는 책의 번호, 즉, $B_{i}$를 의미합니다. 이때, 다음과 같은 조건들이 성립해야 합니다.
    • $2\leq B_{i}\leq 2N$
    • $B_{i}$는 짝수
    • $1\leq j\leq i-1$인 모든 정수 $j$에 대해 $B_{i}\neq B_{j}$
    • $A_{i}<B_{i}<A_{i+1}$ 또는 $A_{i}>B_{i}>A_{i+1}$
  • 위의 조건들이 성립하지 않으면 틀렸습니다를 받게 됩니다.
  • $1\leq i\leq N-1$인 모든 정수 $i$에 대해, 이 함수가 $i$ 번째로 호출되면, 코코아가 $i+2$ 번째에 꽂기 위해 골라놓은 책의 번호, 즉, $A_{i+2}$를 반환합니다. 이때, 다음과 같은 조건들이 성립합니다.
    • $1\leq A_{i+2}\leq 2N+1$
    • $A_{i+2}$는 홀수
    • $1\leq j\leq i+1$인 모든 정수 $j$에 대해 $A_{i+2}\neq A_{j}$
  • 이 함수가 $N$ 번째로 호출되면, $-1$을 반환합니다.

그레이더는 적응적일 수 있습니다. 즉, answer 함수를 호출할 때 넘기는 인자의 값에 따라, 그 함수 호출이나 그 이후의 함수 호출의 반환값이 바뀔 수 있습니다.

$N=4$, $A_1=3$, $A_2=7$라고 합시다. 그러면 그레이더는 solve(4, 3, 7)와 같이 solve 함수를 호출합니다. 이때, 다음과 같은 인터랙션이 가능합니다.

• answer(6)이 $9$를 반환합니다.
• answer(8)이 $1$을 반환합니다.
• answer(4)가 $5$를 반환합니다.
• answer(2)가 $-1$을 반환합니다.

이때, $(A_3,A_4,A_5) =(9,1,5)$이고, $(B_1,B_2,B_3,B_4) =(6,8,4,2)$입니다.

아래는 예시를 나타낸 사진입니다.

샘플 그레이더는 다음 형식으로 입력을 읽습니다:

• line $1$: $N$
• line $1+i$ ($1\leq i\leq N+1$): $A_{i}$

샘플 그레이더가 여러분의 프로그램이 해당 입력에 대해 맞았다고 판정하면, Accepted를 출력합니다.

샘플 그레이더가 여러분의 프로그램이 해당 입력에 대해 틀렸다고 판정하면, Wrong Answer:와 함께 이유를 출력합니다. 자세한 사항은 샘플 그레이더의 코드를 참고해 주세요.

샘플 그레이더는 실제 채점에서 사용하는 그레이더와 다를 수 있음에 유의하세요.

• files.zip