이 문제는 인터랙션 문제입니다. 이 문제에서는 C++만 사용할 수 있습니다.

타키나와 치사토는 과일 박람회에 있습니다. 좋아하는 과일 코스프레를 한 사람들과 사진을 찍으며 하루를 보낸 후, 그들은 게임 부스를 발견했습니다.

게임 규칙은 다음과 같습니다: $n$개의 과일이 있으며, 각 과일에는 1부터 $n$까지의 서로 다른 라벨이 붙어 있습니다. 정확히 하나의 과일이 레몬이지만, 타키나와 치사토는 아직 어느 것이 레몬인지 모릅니다. * 타키나는 $n$개의 과일을 하나씩 받게 됩니다. 타키나의 목표는 (이 과정 동안 눈을 가리고 있는) 치사토에게 레몬의 라벨을 전달하는 것입니다.

과일을 받기 전에, 타키나는 과일 라벨이 나타나는 순서를 나타내는 배열 $p$를 받습니다. $p[1]$은 첫 번째 과일의 라벨이고, $p[2]$는 두 번째 과일의 라벨이며, 이런 식으로 계속됩니다. 그 후, 타키나는 0과 1로만 구성된 이진 문자열 $b$를 작성합니다. 문자열의 길이는 5000자를 넘을 수 없지만, 비어 있을 수도 있습니다. $x$를 $b$의 길이라고 합시다.

그 후, 과일들은 앞서 언급한 순서대로 타키나에게 하나씩 주어집니다. 각 과일을 받을 때마다 타키나는 그 과일이 레몬인지에 대한 정보를 받습니다. 과일이 레몬이 아니면, 타키나는 그것을 먹을지 말지 선택할 수 있습니다. 이 결정은 다음 과일을 받기 전에 내려야 하며 변경할 수 없습니다. 과일이 레몬이면, 타키나는 그것을 먹어서는 안 됩니다.

$y$를 타키나가 먹은 총 과일 수라고 합시다.

마지막으로, 치사토는 문자열 $b$와 먹지 않은 과일 라벨들의 정렬된 목록을 받습니다. 이 정보를 사용하여 치사토는 레몬인 과일의 라벨을 결정해야 합니다.

타키나와 치사토는 이 게임을 $t$번 하기로 했습니다. $x$와 $y$를 모두 최소화하면서 레몬을 정확하게 식별할 수 있는 전략을 설계하세요.

구현 세부사항

이 문제는 인터랙션 문제입니다. 표준 입력에서 읽거나 표준 출력에 쓰지 마십시오. 세 가지 프로시저를 구현해야 합니다.

타키나를 위해 다음을 구현해야 합니다:

std::string init(int subtask, int n, std::vector<int> p) subtask: 테스트 케이스가 속한 서브태스크의 인덱스입니다. n: 과일의 개수입니다. p: 길이가 $n + 1$인 배열로, 다음을 만족합니다: $p[0] = 0$ 각 $1 \le i \le n$에 대해, $p[i]$는 타키나에게 주어질 $i$번째 과일의 라벨입니다. 이 프로시저는 테스트 케이스당 $t$번, 각 게임 시작 시 한 번씩 호출됩니다.

이 프로시저는 0과 1로만 구성된, 길이가 0 이상 5000 이하인 문자열 $b$를 반환해야 합니다. 유효하지 않은 길이나 형식의 문자열이 반환되면 Wrong Answer 판정을 받게 됩니다.

bool receive_fruit(int id, bool is_lemon) id: 타키나에게 주어진 과일의 라벨입니다. is_lemon: 주어진 과일이 레몬이면 true, 아니면 false입니다. * 이 프로시저는 $t$개의 각 게임에 대해 $n$번, 각 과일마다 한 번씩 호출됩니다.

이 프로시저는 과일을 먹어야 하면 true를, 아니면 false를 반환해야 합니다. is_lemon이 true일 때 true를 반환하면 Wrong Answer 판정을 받게 됩니다.

치사토를 위해 다음을 구현해야 합니다:

int answer(int subtask, int n, std::string b, std::vector<int> uneaten) subtask: 테스트 케이스가 속한 서브태스크의 인덱스입니다. n: 과일의 개수입니다. b: init에서 반환된 문자열입니다. uneaten: 타키나가 먹지 않은 과일 라벨들의 길이가 $n - y + 1$인 정렬된 벡터이며, 다음을 만족합니다: uneaten[0] = 0 uneaten[i]는 먹지 않은 과일 중 $i$번째로 작은 라벨입니다. * 이 프로시저는 테스트 케이스당 $t$번, 각 게임 종료 시 한 번씩 호출됩니다.

이 프로시저는 레몬의 라벨인 정수를 반환해야 합니다. 반환값이 올바른 라벨과 일치하지 않으면 Wrong Answer 판정을 받게 됩니다.

실제 채점 시, 위 프로시저들을 호출하는 프로그램은 두 번 실행됩니다: 1. 첫 번째 실행에서는 다음 단계가 $t$번 수행됩니다: init이 한 번 호출됩니다. receive_fruit가 타키나에게 주어진 과일 순서에 따라 $n$번 호출됩니다. 프로그램은 연속적인 호출 간에 정보를 저장하고 유지할 수 있습니다. 2. 두 번째 실행에서는 게임의 순서가 첫 번째 실행과 다를 수 있습니다. $t$개의 각 게임에 대해: answer가 한 번 호출됩니다. answer에 전달된 매개변수 외에, 프로그램은 첫 번째 실행의 정보에 접근할 수 없습니다.

프로시저가 여러 번 호출될 수 있으므로, 이전 호출의 남은 데이터가 현재 호출에 미치는 영향에 주의해야 합니다.

제한

모든 테스트 케이스에 대해 입력은 다음 범위를 만족합니다: $1 \le t \le 10\,000$ $n = 500$ 모든 $1 \le i \le n$에 대해 $1 \le p[i] \le n$ 레몬은 정확히 하나입니다.

각 서브태스크에 대해, 타키나가 작성하는 문자열의 길이 $x$와 그녀가 먹는 과일의 수 $y$에 따라 프로그램의 점수가 다르게 매겨집니다. 각 테스트 케이스에 대한 점수는 모든 $t$번의 게임에서의 $x$의 최댓값과 $y$의 최댓값을 사용하여 계산됩니다.

예제

입력 1

(input data)

출력 1

(output data)

테스트

첨부 파일에서 샘플 그레이더(grader.cpp), 헤더 파일(lemon.h), 솔루션 템플릿(lemon.cpp)을 다운로드할 수 있습니다. 테스트를 위해 sample1.txt와 sample2.txt라는 두 개의 입력 파일이 제공됩니다. 테스트를 위해 compile.sh 스크립트로 컴파일하고 run.sh로 실행할 수 있습니다.

이 문제에서는 CMS 사용자 테스트를 지원하지 않습니다.

샘플 그레이더

로컬에서 구현을 테스트할 수 있도록 샘플 그레이더가 제공됩니다. 공식 그레이더와 달리, 샘플 그레이더는 프로그램을 한 번만 실행하며 타키나와 치사토를 위한 테스트 순서를 변경하지 않습니다.

입력

입력의 첫 번째 줄에는 정수 subtask가 포함되어 있습니다. 입력의 두 번째 줄에는 정수 t가 포함되어 있습니다. 다음 $t$개의 입력 줄은 각각 하나의 게임을 설명합니다. 각 게임은 다음과 같이 설명됩니다: 과일의 개수와 레몬의 라벨을 나타내는 두 개의 공백으로 구분된 정수 $n$과 $l$이 포함된 줄 $n$개의 공백으로 구분된 정수 $p[1], p[2], \dots, p[n]$이 포함된 줄

출력

샘플 그레이더는 모든 게임에 걸친 $x$와 $y$의 값으로부터 계산된 점수 비율을 나타내는 하나의 실수를 출력합니다.

참고

추가적인 진단 메시지가 표준 에러로 출력될 수 있습니다. 샘플 그레이더는 공식 그레이더의 동작을 시뮬레이션하지 않습니다.