Lockpicking

The Hungarian State Treasury replaced the locking mechanism on one of their safes. This new lock
can only be opened by custom keycards. The verification of a keycard follows a special protocol.

The lock has $N$ internal states numbered from $0$ to $N-1$. For each $i$ from $0$ to $N-1$, inclusive,
there is a bit $A[i]$ and there are two states $S[i][0]$ and $S[i][1]$ associated with state $i$. A bit is a binary
digit that is either $0$ or $1$. States $S[i][0]$ and $S[i][1]$ may coincide, and a state may be associated with
itself.

Similarly to this, a keycard has $M$ states numbered from $0$ to $M-1$, and for each $j$ from $0$ to
$M-1$, bit $B[j]$ and states $T[j][0]$ and $T[j][1]$ are associated with state $j$. Hereafter, lock states and
keycard states are both referred to as states.

In the verification process, the lock gets paired up with a keycard. Both of them are capable of
outputting bits, as well as reading bits from the output of the other. At the start of the process, the
lock sets to a specific initial state $i_0$. The keycard also sets to initial state $j_0$, specific to the
keycard. They repeat the following steps at most $10^7$ times:

1. Each of them outputs a single bit according to its current state. If the lock is in state $i$, it
   outputs the bit $A[i]$. Analogously, the keycard outputs $B[j]$ if it is in state $j$.
2. They read the bit that was outputted by the other. The lock reads $B[j]$, and the keycard reads
   $A[i]$. If the two bits are different, they register an error.
3. The devices change their states based on the bit they read and the states associated with the
   current one. The lock enters state $S[i][B[j]]$, and the keycard enters state $T[j][A[i]]$.

If, at any point over the verification process, the number of errors reaches $K$, the verification fails,
and the process terminates. Otherwise, if they complete $10^7$ iterations without registering at least
$K$ errors, the verification succeeds, and the lock opens.

Upon setting up the new lock, the mechanics made a mistake: they forgot to specify state $i_0$, the
initial state used in the verification process. As a result, whenever the lock gets paired up with a
keycard, it is set to an arbitrary (unknown) initial state.

Your task is to construct a keycard capable of opening the lock despite the mistake.

Implementation Details

You should implement the following procedure.

void construct_card(int N, int[] A, int[][] S)

• $N$: the number of internal states of the lock.
• $A$: array of length $N$ specifying the bits associated with the states of the lock.
• $S$: array of length $N$ containing arrays of length 2. Specifies the two states associated with
  the states of the lock.
• This procedure adds a move of type 4 to the sequence of moves.

Procedures move_right, move_left, swap_places, and move_around are called for a total of $M$
times.

int get_position(int D)

• $D$: an integer representing a dancer.
• This procedure should return the position of dancer $D$ after performing every move added
  to the sequence of moves before this call.
• This procedure is called $Q$ times.

Example

Consider the following sequence of calls:

init(6, [5, 1, 4, 2, 0, 3])

There are 6 dancers, and the initial order of the dancers is given by the array [5, 1, 4, 2, 0, 3], that is,
position 0 is occupied by dancer 5, position 1 is occupied by dancer 1, position 2 is occupied by
dancer 4, and so on.

move_left(2)

Each dancer moves two places to the left cyclically. After the move, the order of the dancers
becomes [4, 2, 0, 3, 5, 1].

get_position(0)

This call asks the position of dancer 0 after performing the first move. Dancer 0 is standing at
position 2. Therefore, the procedure should return 2.

swap_places()

After this move, the order of the dancers becomes [2, 4, 3, 0, 1, 5].

move_around()

The new position of each dancer is determined as follows.
* Dancer 0: position 0 is occupied by dancer 2, so dancer 0 moves to position 2.
* Dancer 1: position 1 is occupied by dancer 4, so dancer 1 stays at position 4.
* Dancer 2: position 2 is occupied by dancer 3, so dancer 2 moves to position 3.
* Dancer 3: position 3 is occupied by dancer 0, so dancer 3 moves to position 0.
* Dancer 4: position 4 is occupied by dancer 1, so dancer 4 stays at position 1.
* Dancer 5: position 5 is occupied by dancer 5, so dancer 5 stays at position 5.

After this move, the order of the dancers becomes [3, 4, 0, 2, 1, 5].

get_position(3)

Dancer 3 is at position 0 after performing every move so far. The procedure should return 0.

Constraints

• $2 \le N \le 150$
• $0 \le A[i] \le 1$ (for each $i$ such that $0 \le i < N$)
• $0 \le S[i][0] < N$ and $0 \le S[i][1] < N$ (for each $i$ such that $0 \le i < N$)
• $1 \le M \le 50\,000$
• $0 \le B[j] \le 1$ (for each $j$ such that $0 \le j < M$)
• $0 \le T[j][0] < M$ and $0 \le T[j][1] < M$ (for each $j$ such that $0 \le j < M$)
• $K = N$

Sample Grader

The sample grader reads the input in the following format:

• line 1: $N \; M \; Q$
• line 2: $P[0] \; P[1] \; \ldots \; P[N-1]$
• line 3 + $l$ ($0 \le l < M + Q$):
• To perform a move of type 1: $1 \; K$
• To perform a move of type 2: $2 \; K$
• To perform a move of type 3: $3$
• To perform a move of type 4: $4$
• To ask the position of a dancer: $5 \; D$

The sample grader prints your answers in the following format:

• line 1 + $q$ ($0 \le q < Q$): the values returned by get_position procedure should construct a keycard capable of opening the lock irrespective of its
  initial state.
• This procedure is called exactly once for each test case.

This procedure must call the following procedure exactly once to construct a keycard:

void define_states(int M, int[] B, int[][] T, int j0)

• $M$: the number of internal states of the keycard.
• $B$: array of length $M$ specifying the bits associated with the states of the keycard.
• $T$: array of length $M$ containing arrays of length 2. Specifies the two states associated with
  the states of the keycard.
• $j0$: a number representing the initial state of the keycard.
• This procedure constructs a keycard with $M$ internal states. For each $j$ from $0$ to $M-1$,
  inclusive, bit $B[j]$ and states $T[j][0]$ and $T[j][1]$ are associated with state $j$. The initial state of
  the keycard is set to $j0$.
• This procedure should be called exactly once by the procedure construct_card.

Constraints on the parameters of define_states are given in the Constraints section below.

Example

Consider a lock that has $N = 2$ states. Bit $A[0] = 0$ and states $S[0][0] = 1$ and $S[0][1] = 0$ are
associated with state 0, and bit $A[1] = 1$ and states $S[1][0] = 1$ and $S[1][1] = 0$ are associated with
state 1. For this example, suppose that the value of $K$ is 2.

The procedure construct_card is called the following way.

construct_card(2, [0, 1], [[1, 0], [1, 0]])

First, consider a keycard with $M = 1$ state where $B[0] = 1$, $T[0][0] = T[0][1] = 0$ and the initial
state is $j_0 = 0$.

In the case when the unknown initial state of the lock is 1, the steps of the verification process are
shown in the following table. The states of the lock and the keycard are denoted by $i$ and $j$,
respectively.

Note that the last two columns show the state of the lock and the keycard for the next step.

We see that there is no error in step 0 as we have $A[i] = B[j]$. Following step 0, there is an error in
step 1, as well as in step 2, so the verification fails, and the process terminates. Therefore, this
keycard is not capable of opening the lock.

Consider a keycard with $M = 2$ states and suppose that $B = [0, 1]$ and $T = [[1, 1], [0, 0]]$ and the
initial state is $j_0 = 0$.

If the initial state of the lock is 0, the verification goes as follows.

At this point, we may deduce that the verification process will succeed without errors.

If the initial state of the lock is 1, the verification goes as follows.

At this point, we may deduce that the verification process will succeed without additional errors.

Therefore, this keycard can open the lock irrespective of its initial state. The procedure may call
define_states in the following way.

define_states(2, [0, 1], [[1, 1], [0, 0]], 0)

After define_states completes, procedure construct_card should return.

Constraints

• $2 \le N \le 150$
• $0 \le A[i] \le 1$ (for each $i$ such that $0 \le i < N$)
• $0 \le S[i][0] < N$ and $0 \le S[i][1] < N$ (for each $i$ such that $0 \le i < N$)
• $1 \le M \le 50\,000$
• $0 \le B[j] \le 1$ (for each $j$ such that $0 \le j < M$)
• $0 \le T[j][0] < M$ and $0 \le T[j][1] < M$ (for each $j$ such that $0 \le j < M$)
• $K = N$

Sample Grader

The sample grader reads the input in the following format:

• line 1: $N \; K$
• line 2 + $i$ ($0 \le i < N$): $A[i] \; S[i][0] \; S[i][1]$

If the sample grader detects a protocol violation, the output of the sample grader is Protocol Violation: <MSG>, where <MSG> is one of the error messages:

• missing call: the procedure construct_card returned without making a call to
  define_states.
• too many calls: the procedure construct_card made more than one call to
  define_states.
• invalid number: $M$ is not an integer between 1 and 50 000.
• invalid array: the length of array $B$ or the length of array $T$ is different from $M$, or there
  exists an index $j$ ($0 \le j < M$) such that the length of $T[j]$ is not 2.
• invalid bit: there exists an index $j$ ($0 \le j < M$) such that $B[j]$ is not 0 or 1.
• invalid state: there exists an index $j$ ($0 \le j < M$) such that at least one of $T[j][0]$ and
  $T[j][1]$ is not an integer between 0 and $M-1$.
• invalid initial state: $j0$ is not an integer between 0 and $M-1$.

Otherwise, the sample grader produces two outputs.

First, the sample grader prints the constructed keycard in the following format:

• line 1: $M \; j0$
• line 2 + $j$ ($0 \le j < M$): $B[j] \; T[j][0] \; T[j][1]$

Second, the sample grader writes a file lockpicking.bin in the working directory. This file serves
as the input of the testing tool described in the following section.

Testing Tool

The attachment package for this task contains a file named display.py. When invoked, this
Python script simulates the verification process between a lock and a keycard. For this, the binary
file lockpicking.bin must be present in the working directory.

The initial state of the lock is 0 in the first simulation. After the simulation completes, a simple
graphical interface shows up. The main features are as follows.

• You can see the overall result of the verification (for the current initial state of the lock) at the
  bottom of the window.
• You can browse through the steps of the process by clicking the arrow buttons or pressing
  their hotkeys.
• To set the initial state of the lock, use the Init Lock button.
• The Reload button reloads the configuration file lockpicking.bin. It is useful if the
  contents of lockpicking.bin have changed.

The last two operations automatically rerun the simulation and update the GUI.

To invoke the script, execute the following command.

python3 display.py

You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution, then provide a complete implementation in C++17. You should correctly implement the routine(s) described in Implementation Details, without reading or writing anything directly from stdin or to stdout, as input and output are passed through the implemented routines. Assume your code will be run on the OFFICIAL grader, and do not add a main, a sample grader, or any other functionality unless it has been explicitly requested.
Put your final solution within a single code block: cpp <your code here>

Problem statement (Lockpicking)

The Hungarian State Treasury replaced the locking mechanism on one of their safes. This new lock
can only be opened by custom keycards. The verification of a keycard follows a special protocol.

The lock has $N$ internal states numbered from $0$ to $N-1$. For each $i$ from $0$ to $N-1$, inclusive,
there is a bit $A[i]$ and there are two states $S[i][0]$ and $S[i][1]$ associated with state $i$. A bit is a binary
digit that is either $0$ or $1$. States $S[i][0]$ and $S[i][1]$ may coincide, and a state may be associated with
itself.

Similarly to this, a keycard has $M$ states numbered from $0$ to $M-1$, and for each $j$ from $0$ to
$M-1$, bit $B[j]$ and states $T[j][0]$ and $T[j][1]$ are associated with state $j$. Hereafter, lock states and
keycard states are both referred to as states.

In the verification process, the lock gets paired up with a keycard. Both of them are capable of
outputting bits, as well as reading bits from the output of the other. At the start of the process, the
lock sets to a specific initial state $i_0$. The keycard also sets to initial state $j_0$, specific to the
keycard. They repeat the following steps at most $10^7$ times:

1. Each of them outputs a single bit according to its current state. If the lock is in state $i$, it
   outputs the bit $A[i]$. Analogously, the keycard outputs $B[j]$ if it is in state $j$.
2. They read the bit that was outputted by the other. The lock reads $B[j]$, and the keycard reads
   $A[i]$. If the two bits are different, they register an error.
3. The devices change their states based on the bit they read and the states associated with the
   current one. The lock enters state $S[i][B[j]]$, and the keycard enters state $T[j][A[i]]$.

If, at any point over the verification process, the number of errors reaches $K$, the verification fails,
and the process terminates. Otherwise, if they complete $10^7$ iterations without registering at least
$K$ errors, the verification succeeds, and the lock opens.

Upon setting up the new lock, the mechanics made a mistake: they forgot to specify state $i_0$, the
initial state used in the verification process. As a result, whenever the lock gets paired up with a
keycard, it is set to an arbitrary (unknown) initial state.

Your task is to construct a keycard capable of opening the lock despite the mistake.

Implementation Details

You should implement the following procedure.

void construct_card(int N, int[] A, int[][] S)

• $N$: the number of internal states of the lock.
• $A$: array of length $N$ specifying the bits associated with the states of the lock.
• $S$: array of length $N$ containing arrays of length 2. Specifies the two states associated with
  the states of the lock.
• This procedure adds a move of type 4 to the sequence of moves.

Procedures move_right, move_left, swap_places, and move_around are called for a total of $M$
times.

int get_position(int D)

• $D$: an integer representing a dancer.
• This procedure should return the position of dancer $D$ after performing every move added
  to the sequence of moves before this call.
• This procedure is called $Q$ times.

Example

Consider the following sequence of calls:

init(6, [5, 1, 4, 2, 0, 3])

There are 6 dancers, and the initial order of the dancers is given by the array [5, 1, 4, 2, 0, 3], that is,
position 0 is occupied by dancer 5, position 1 is occupied by dancer 1, position 2 is occupied by
dancer 4, and so on.

move_left(2)

Each dancer moves two places to the left cyclically. After the move, the order of the dancers
becomes [4, 2, 0, 3, 5, 1].

get_position(0)

This call asks the position of dancer 0 after performing the first move. Dancer 0 is standing at
position 2. Therefore, the procedure should return 2.

swap_places()

After this move, the order of the dancers becomes [2, 4, 3, 0, 1, 5].

move_around()

The new position of each dancer is determined as follows.
* Dancer 0: position 0 is occupied by dancer 2, so dancer 0 moves to position 2.
* Dancer 1: position 1 is occupied by dancer 4, so dancer 1 stays at position 4.
* Dancer 2: position 2 is occupied by dancer 3, so dancer 2 moves to position 3.
* Dancer 3: position 3 is occupied by dancer 0, so dancer 3 moves to position 0.
* Dancer 4: position 4 is occupied by dancer 1, so dancer 4 stays at position 1.
* Dancer 5: position 5 is occupied by dancer 5, so dancer 5 stays at position 5.

After this move, the order of the dancers becomes [3, 4, 0, 2, 1, 5].

get_position(3)

Dancer 3 is at position 0 after performing every move so far. The procedure should return 0.

Constraints

• $2 \le N \le 150$
• $0 \le A[i] \le 1$ (for each $i$ such that $0 \le i < N$)
• $0 \le S[i][0] < N$ and $0 \le S[i][1] < N$ (for each $i$ such that $0 \le i < N$)
• $1 \le M \le 50\,000$
• $0 \le B[j] \le 1$ (for each $j$ such that $0 \le j < M$)
• $0 \le T[j][0] < M$ and $0 \le T[j][1] < M$ (for each $j$ such that $0 \le j < M$)
• $K = N$

Sample Grader

The sample grader reads the input in the following format:

• line 1: $N \; M \; Q$
• line 2: $P[0] \; P[1] \; \ldots \; P[N-1]$
• line 3 + $l$ ($0 \le l < M + Q$):
• To perform a move of type 1: $1 \; K$
• To perform a move of type 2: $2 \; K$
• To perform a move of type 3: $3$
• To perform a move of type 4: $4$
• To ask the position of a dancer: $5 \; D$

The sample grader prints your answers in the following format:

• line 1 + $q$ ($0 \le q < Q$): the values returned by get_position procedure should construct a keycard capable of opening the lock irrespective of its
  initial state.
• This procedure is called exactly once for each test case.

This procedure must call the following procedure exactly once to construct a keycard:

void define_states(int M, int[] B, int[][] T, int j0)

• $M$: the number of internal states of the keycard.
• $B$: array of length $M$ specifying the bits associated with the states of the keycard.
• $T$: array of length $M$ containing arrays of length 2. Specifies the two states associated with
  the states of the keycard.
• $j0$: a number representing the initial state of the keycard.
• This procedure constructs a keycard with $M$ internal states. For each $j$ from $0$ to $M-1$,
  inclusive, bit $B[j]$ and states $T[j][0]$ and $T[j][1]$ are associated with state $j$. The initial state of
  the keycard is set to $j0$.
• This procedure should be called exactly once by the procedure construct_card.

Constraints on the parameters of define_states are given in the Constraints section below.

Example

Consider a lock that has $N = 2$ states. Bit $A[0] = 0$ and states $S[0][0] = 1$ and $S[0][1] = 0$ are
associated with state 0, and bit $A[1] = 1$ and states $S[1][0] = 1$ and $S[1][1] = 0$ are associated with
state 1. For this example, suppose that the value of $K$ is 2.

The procedure construct_card is called the following way.

construct_card(2, [0, 1], [[1, 0], [1, 0]])

First, consider a keycard with $M = 1$ state where $B[0] = 1$, $T[0][0] = T[0][1] = 0$ and the initial
state is $j_0 = 0$.

In the case when the unknown initial state of the lock is 1, the steps of the verification process are
shown in the following table. The states of the lock and the keycard are denoted by $i$ and $j$,
respectively.

Note that the last two columns show the state of the lock and the keycard for the next step.

We see that there is no error in step 0 as we have $A[i] = B[j]$. Following step 0, there is an error in
step 1, as well as in step 2, so the verification fails, and the process terminates. Therefore, this
keycard is not capable of opening the lock.

Consider a keycard with $M = 2$ states and suppose that $B = [0, 1]$ and $T = [[1, 1], [0, 0]]$ and the
initial state is $j_0 = 0$.

If the initial state of the lock is 0, the verification goes as follows.

At this point, we may deduce that the verification process will succeed without errors.

If the initial state of the lock is 1, the verification goes as follows.

At this point, we may deduce that the verification process will succeed without additional errors.

Therefore, this keycard can open the lock irrespective of its initial state. The procedure may call
define_states in the following way.

define_states(2, [0, 1], [[1, 1], [0, 0]], 0)

After define_states completes, procedure construct_card should return.

Constraints

• $2 \le N \le 150$
• $0 \le A[i] \le 1$ (for each $i$ such that $0 \le i < N$)
• $0 \le S[i][0] < N$ and $0 \le S[i][1] < N$ (for each $i$ such that $0 \le i < N$)
• $1 \le M \le 50\,000$
• $0 \le B[j] \le 1$ (for each $j$ such that $0 \le j < M$)
• $0 \le T[j][0] < M$ and $0 \le T[j][1] < M$ (for each $j$ such that $0 \le j < M$)
• $K = N$

Sample Grader

The sample grader reads the input in the following format:

• line 1: $N \; K$
• line 2 + $i$ ($0 \le i < N$): $A[i] \; S[i][0] \; S[i][1]$

If the sample grader detects a protocol violation, the output of the sample grader is Protocol Violation: <MSG>, where <MSG> is one of the error messages:

• missing call: the procedure construct_card returned without making a call to
  define_states.
• too many calls: the procedure construct_card made more than one call to
  define_states.
• invalid number: $M$ is not an integer between 1 and 50 000.
• invalid array: the length of array $B$ or the length of array $T$ is different from $M$, or there
  exists an index $j$ ($0 \le j < M$) such that the length of $T[j]$ is not 2.
• invalid bit: there exists an index $j$ ($0 \le j < M$) such that $B[j]$ is not 0 or 1.
• invalid state: there exists an index $j$ ($0 \le j < M$) such that at least one of $T[j][0]$ and
  $T[j][1]$ is not an integer between 0 and $M-1$.
• invalid initial state: $j0$ is not an integer between 0 and $M-1$.

Otherwise, the sample grader produces two outputs.

First, the sample grader prints the constructed keycard in the following format:

• line 1: $M \; j0$
• line 2 + $j$ ($0 \le j < M$): $B[j] \; T[j][0] \; T[j][1]$

Second, the sample grader writes a file lockpicking.bin in the working directory. This file serves
as the input of the testing tool described in the following section.

Testing Tool

The attachment package for this task contains a file named display.py. When invoked, this
Python script simulates the verification process between a lock and a keycard. For this, the binary
file lockpicking.bin must be present in the working directory.

The initial state of the lock is 0 in the first simulation. After the simulation completes, a simple
graphical interface shows up. The main features are as follows.

• You can see the overall result of the verification (for the current initial state of the lock) at the
  bottom of the window.
• You can browse through the steps of the process by clicking the arrow buttons or pressing
  their hotkeys.
• To set the initial state of the lock, use the Init Lock button.
• The Reload button reloads the configuration file lockpicking.bin. It is useful if the
  contents of lockpicking.bin have changed.

The last two operations automatically rerun the simulation and update the GUI.

To invoke the script, execute the following command.

python3 display.py

Execution limits

Your solution will have 1.0 second(s) execution time and 2048 MB memory limit to solve each test case.

Starting code

Here's your starting code with some skeleton/placeholder functionality:

#include "lockpicking.h"

void construct_card(int N, std::vector<int> A, std::vector<std::vector<int>> S) {
    define_states(2, {0, 1}, {{1, 1}, {0, 0}}, 0);
}

参考函数签名

#include "lockpicking.h"

void construct_card(int N, std::vector<int> A, std::vector<std::vector<int>> S) {
    define_states(2, {0, 1}, {{1, 1}, {0, 0}}, 0);
}

请在 submission.cpp 中实现该函数（可 #include "problem.h" 获取题目提供的声明）。判题时你的代码会与题目提供的 grader 一起编译链接。

本题是函数题，由 grader 调用你实现的函数。

由 grader 打印判定结果，无需自行读写 stdin/stdout。

include "lockpicking.h"

void construct_card(int N, std::vector<int> A, std::vector<std::vector\<int>> S) {
define_states(2, {0, 1}, {{1, 1}, {0, 0}}, 0);
}