안나와 브루노는 도박의 달인입니다. 그들은 게임의 딜러인 D-타로와 게임을 하려고 합니다.
이 게임에서 안나와 브루노는 서로 다른 방에 머무릅니다. 그들은 오직 고장난 장치 하나만을 사용하여 서로 통신할 수 있습니다. D-타로는 안나에게 정수 하나를 줍니다. 안나와 브루노에게 이 게임의 목적은 장치를 사용하여 안나에게 주어진 정수를 브루노에게 전달하는 것입니다.
게임이 시작될 때, 맨 처음에 안나는 $1$ 이상 $2\,000$ 이하의 정수 $m$을 선언합니다. 그 후 그들은 $Q$번의 라운드를 진행합니다. 라운드 $i$ ($1\le i\le Q$)는 다음과 같이 진행됩니다.
- D-타로가 안나에게 정수 $A_i$를 줍니다.
- 안나는 장치에 배열 $s_i,t_i$를 입력합니다. 배열 $s_i,t_i$의 모든 원소는 $0$ 또는 $1$이어야 합니다. 배열 $s_i,t_i$는 길이가 같아야 하며, 그 길이는 $1$ 이상 $m$ 이하입니다.
- 배열 $s_i$와 $t_i$로부터 리플 셔플(아래 참조)에 의해 얻어진 배열을 $u_i$라고 합시다. 그러면 장치는 $u_i$를 브루노에게 보냅니다.
- 브루노는 D-타로에게 정수 하나를 보냅니다. 만약 이 정수가 D-타로가 안나에게 준 정수 $A_i$와 같다면, 안나와 브루노는 이번 라운드에서 승리합니다.
안나와 브루노가 $Q$번의 라운드 모두에서 승리하도록 두 사람의 전략을 구현하는 프로그램을 작성하십시오.
리플 셔플
배열 $Z$의 원소들을 두 그룹으로 나누어 다음 두 조건을 만족하도록 할 수 있을 때, 배열 $Z$가 배열 $X$와 $Y$로부터 리플 셔플에 의해 얻어졌다고 말합니다.
- 첫 번째 그룹에 속한 원소들을 원래 순서대로 나열한 배열은 배열 $X$와 같습니다.
- 두 번째 그룹에 속한 원소들을 원래 순서대로 나열한 배열은 배열 $Y$와 같습니다.
예를 들어, 배열 $Z$의 첫 번째, 두 번째, 네 번째 원소를 원래 순서대로 나열한 배열은 $[1,1,0]$이고, $Z$의 세 번째, 다섯 번째, 여섯 번째 원소를 원래 순서대로 나열한 배열은 $[1,0,0]$이므로, 배열 $Z=[1,1,1,0,0,0]$은 $X=[1,1,0]$과 $Y=[1,0,0]$으로부터 리플 셔플에 의해 얻어집니다.
반면에, $X=[1,1,0]$, $Y=[1,0,0]$이고 $Z=[0,0,0,1,1,1]$이면, 배열 $Z$는 $X$와 $Y$로부터 리플 셔플에 의해 얻어지지 않습니다.
구현 세부사항
두 개의 파일을 제출해야 합니다.
첫 번째 파일은 Anna.cpp입니다. 이 파일은 안나의 전략을 구현해야 하며, 다음 함수들을 구현해야 합니다. 프로그램은 전처리기 지시문 #include를 사용하여 Anna.h를 포함해야 합니다.
int Declare()이 함수는 맨 처음에 한 번 호출됩니다.
- 반환값은 안나가 선언한 정수 $m$입니다.
- 정수 $m$은 $1$ 이상 $2\,000$ 이하여야 합니다. 이 조건을 만족하지 않으면 프로그램은
Wrong Answer [1]로 판정됩니다.
std::pair<std::vector<int>, std::vector<int> > Anna(long long A)Declare함수가 호출된 후, 이 함수는 $Q$번 호출됩니다. 이 함수의 $i$번째 호출($1\le i\le Q$)은 라운드 $i$의 1단계와 2단계에 해당합니다.- 매개변수
A는 D-타로가 안나에게 준 정수 $A_i$입니다. - 반환값은 안나가 장치에 입력한 두 배열 $s_i,t_i$의 쌍(pair)입니다.
- 배열 $s_i,t_i$의 모든 원소는 $0$ 또는 $1$이어야 합니다. 이 조건을 만족하지 않으면 프로그램은
Wrong Answer [2]로 판정됩니다. - 배열 $s_i,t_i$의 길이는 둘 다 $1$ 이상 $m$ 이하여야 합니다. 이 조건을 만족하지 않으면 프로그램은
Wrong Answer [3]로 판정됩니다. - 배열 $s_i,t_i$는 길이가 같아야 합니다. 이 조건을 만족하지 않으면 프로그램은
Wrong Answer [4]로 판정됩니다.
- 매개변수
두 번째 파일은 Bruno.cpp입니다. 이 파일은 브루노의 전략을 구현해야 하며, 다음 함수를 구현해야 합니다. 프로그램은 전처리기 지시문 #include를 사용하여 Bruno.h를 포함해야 합니다.
long long Bruno(std::vector<int> u)안나가 장치에 배열을 입력한 후, 이 함수가 한 번 호출됩니다. 총 $Q$번 호출됩니다. 이 함수의 $i$번째 호출($1\le i\le Q$)은 라운드 $i$의 3단계와 4단계에 해당합니다.
- 매개변수
u는 라운드 $i$에서 장치가 브루노에게 보낸 배열 $u_i$입니다. - 반환값은 브루노가 D-타로에게 보낸 정수입니다.
- 반환값은 D-타로가 안나에게 준 정수 $A_i$와 같아야 합니다. 이 조건을 만족하지 않으면 프로그램은
Wrong Answer [5]로 판정됩니다.
- 매개변수
중요 안내
- 프로그램은 내부적인 용도로 다른 함수를 구현하거나 전역 변수를 사용할 수 있습니다. 제출된 파일들은 그레이더와 함께 컴파일되어 하나의 실행 파일이 됩니다. 다른 파일과의 충돌을 피하기 위해 모든 전역 변수와 내부 함수는 이름 없는 이름공간(unnamed namespace) 안에 선언되어야 합니다. 채점 시에는 안나의 프로세스와 브루노의 프로세스, 총 두 개의 프로세스로 실행됩니다. 안나의 프로세스와 브루노의 프로세스는 전역 변수를 공유할 수 없습니다.
- 프로그램은 표준 입력과 표준 출력을 사용해서는 안 됩니다. 프로그램은 어떠한 방법으로도 다른 파일과 통신해서는 안 됩니다. 단, 표준 오류 출력(standard error)으로 디버깅 정보를 출력하는 것은 허용됩니다.
컴파일 및 테스트 실행
대회 웹페이지에서 프로그램을 테스트하기 위한 샘플 그레이더가 포함된 압축 파일을 다운로드할 수 있습니다. 압축 파일에는 프로그램의 샘플 소스 파일도 포함되어 있습니다.
샘플 그레이더는 grader.cpp 파일입니다. 프로그램을 테스트하려면 grader.cpp, Anna.cpp, Bruno.cpp, Anna.h, Bruno.h를 같은 디렉터리에 놓고 다음 명령어를 실행하여 프로그램을 컴파일하십시오.
g++ -std=gnu++17 -O2 -o grader grader.cpp Anna.cpp Bruno.cpp
컴파일이 성공하면 실행 파일 grader가 생성됩니다.
실제 그레이더는 샘플 그레이더와 다르다는 점에 유의하십시오. 샘플 그레이더는 단일 프로세스로 실행되며, 표준 입력으로부터 입력 데이터를 읽고 표준 출력으로 결과를 출력합니다.
샘플 그레이더의 입력
샘플 그레이더는 표준 입력으로부터 다음 데이터를 읽어들입니다.
$$ \begin{gathered} Q\\ A_1\\ A_2\\ \vdots\\ A_Q \end{gathered} $$
샘플 그레이더의 출력
샘플 그레이더는 표준 출력으로 다음 정보를 출력합니다 (따옴표는 명확성을 위한 것입니다).
- 프로그램이 정답으로 판정되면,
Declare함수의 반환값 $m$을 “Accepted: 2000”과 같이 출력합니다. - 프로그램이 오답(Wrong Answer) 중 하나로 판정되면, 샘플 그레이더는 그 종류를 “
Wrong Answer [1]”과 같이 출력합니다.
프로그램이 여러 종류의 오답 조건을 동시에 만족하는 경우, 샘플 그레이더는 그중 하나만 보고합니다.
샘플 그레이더가 실행될 때, 각 라운드의 리플 셔플은 의사 난수를 사용하여 계산됩니다. 그 결과는 여러 번 실행해도 바뀌지 않습니다. 의사 난수의 시드(seed)를 변경하려면 다음과 같이 샘플 그레이더를 실행하십시오.
./grader 2022
첫 번째 인자는 정수여야 합니다.
제한
- $1\le Q\le 1\,000$.
- $1\le A_i\le 1\,000\,000\,000\,000\,000\,000\ (=10^{18})$ ($1\le i\le Q$).
서브태스크
- (5점) $A_i\le 2\,000$ ($1\le i\le Q$).
- (5점) $A_i\le 4\,000\,000$ ($1\le i\le Q$).
- (3점) $A_i\le 10\,000\,000\ (=10^7)$ ($1\le i\le Q$).
- (12점) $A_i\le 100\,000\,000\ (=10^8)$ ($1\le i\le Q$).
- (15점) $A_i\le 100\,000\,000\,000\ (=10^{11})$ ($1\le i\le Q$).
(60점) 추가 제한 없음. 이 서브태스크에서 점수는 다음과 같이 계산됩니다.
- 이 서브태스크의 모든 테스트 케이스에 대해 안나가 선언한 정수 $m$의 최댓값을 $m^*$라고 합시다.
- 점수는 다음과 같습니다.
| $m^*$의 값 | 점수 |
|---|---|
| $201\le m^*\le 2\,000$ | $40-25\times\log_{10}\left(\frac{m^*}{200}\right)$점 (소수점 아래 버림) |
| $161\le m^*\le 200$ | 40점 |
| $156\le m^*\le 160$ | 44점 |
| $151\le m^*\le 155$ | 48점 |
| $146\le m^*\le 150$ | 52점 |
| $141\le m^*\le 145$ | 56점 |
| $m^*\le 140$ | 60점 |
예제
다음은 샘플 그레이더에 대한 예제 입력과 그에 대응하는 함수 호출입니다.
입력 1
2 42 2000
예제 함수 호출
| 호출 | 반환값 |
|---|---|
Declare() |
4 |
Anna(42) |
([0, 0, 1, 0], [1, 1, 0, 1]) |
Bruno([1, 0, 0, 1, 0, 1, 0, 1]) |
42 |
Anna(2000) |
([0, 1], [0, 0]) |
Bruno([0, 0, 1, 0]) |
2000 |
이 예제 입력에는 $Q\ (=2)$번의 라운드가 있습니다. 라운드 1에서 D-타로는 안나에게 정수 $A_1\ (=42)$를 줍니다. 라운드 2에서 D-타로는 안나에게 정수 $A_2\ (=2000)$을 줍니다.
이 예제 입력은 모든 서브태스크의 제한을 만족합니다.