Hat Game

Every Thursday, CS-House covers various stories about Yonsei University's Department of Computer Science in podcast form. On the episode aired March 18, 2021, alumnus Inseop Yoon, who had advanced to the ICPC World Final, appeared as a guest and talked about algorithms and competitive programming. During the conversation, he solved some fun problems together with the viewers, and the organizers decided to modify one of those problems and use it in the Yonsei University Freshman Programming Contest. Consider the following problem.

As shown in the figure, $N$ people stand in a line facing forward. Each person, except the one at the very back, wears a hat with an integer from $0$ to $63$ written on it.

Each person can see the numbers on the hats of everyone in front of them, but cannot see the numbers on the hats of anyone behind them, including their own hat.

When the game starts, starting from the person at the very back, each person in order says one integer from $0$ to $63$.

Before the game starts, the $N$ people gather to plan a strategy. Devise a strategy that maximizes the number of people whose spoken number equals the number on their own hat.

To solve this problem, you must submit the file hat.cpp. The functions that must be included in hat.cpp are as follows.

void init(int N);

• Called exactly once, immediately after the program starts running. N is the number of people standing in line.

int call(vector<int> F, vector<int> B, int num);

• Returns the number that the (num+1)-th person from the front must say. num is an integer from $0$ to $N-1$.
• F is an integer array of length $N$ holding the numbers on the hats worn by the people in front. F[i] holds the number on the hat worn by the (i+1)-th person. If the (num+1)-th person cannot see the number on the hat worn by the (i+1)-th person, that array value is $0$.
• B is an integer array of length $N$ holding the numbers spoken by the people behind. B[i] holds the number spoken by the (i+1)-th person. If the (i+1)-th person has not yet had a turn to speak before the (num+1)-th person speaks, that array value is $0$.
• In each game, call is called a total of $N$ times. On each call to call, num takes the values $N-1$ down to $0$ in order.

A total of $T$ hat games run simultaneously, and in each game $N-1$ people must say the number equal to the one on their own hat to receive Accepted. If the grader judges the submission as wrong during execution, the program terminates immediately.

• $1 \le N \le 10$
• $1 \le T \le 200\,000$