Note: Currently the partial scoring for this problem is not working.
Monster City has a large park consisting of several attractions and one-way roads connecting these locations. There are $v$ attractions in total, numbered $1, 2, \dots, v$. These attractions include $n$ entrances and $1$ exit; attractions numbered $1, 2, \dots, n$ are entrances, and the attraction numbered $v$ is the exit. There are $e$ roads in the park, where the $i$-th road starts at attraction $a_i$ and ends at attraction $b_i$.
Each attraction $i$ has a flag $s_i$, which is either & or |. Similarly, each road $i$ has a flag $t_i$, which is one of &, |, ~, <, or >. If $t_i$ is not ~, the road $i$ also has a weight $l_i$.
Every day, a wave of $n$ monsters enters the park. On day $i$, $n$ monsters with initial health values $h_{i,1}, h_{i,2}, \dots, h_{i,n}$ enter the $n$ entrances $1, 2, \dots, n$ simultaneously, and then these monsters roam through the park. In each minute, every monster splits into $k$ monsters (where $k$ is the number of roads starting from the attraction where the monster is currently located), each with the same health as before, and they move forward along the $k$ roads starting from that attraction.
A monster takes exactly $1$ minute to traverse a road. After a monster with health $h$ traverses road $i$, its health changes to $h'$. The table below shows the transformation rules.
| $t_i=$ | $h'=$ | Description |
|---|---|---|
& |
$h\ \mathrm{AND}\ l_i$ | Bitwise AND of $h$ and $l_i$ |
| |
$h\ \mathrm{OR}\ l_i$ | Bitwise OR of $h$ and $l_i$ |
~ |
$\mathrm{NOT}\ h$ | Bitwise NOT of $h$ |
< |
$h\ \mathrm{SHL}\ l_i$ | Bitwise left shift of $h$ by $l_i$ bits, filling with $0$s |
> |
$h\ \mathrm{SHR}\ l_i$ | Bitwise right shift of $h$ by $l_i$ bits, filling with $0$s |
In the table, $\mathrm{AND}, \mathrm{OR}, \mathrm{NOT}, \mathrm{SHL}, \mathrm{SHR}$ correspond to bitwise AND, OR, NOT, left shift, and right shift, respectively. $h, l_i$, and $h'$ are all $32$-bit unsigned integers. For $\mathrm{AND}$ and $\mathrm{OR}$ operations, $0 \le l_i < 2^{32}$. For $\mathrm{SHL}$ and $\mathrm{SHR}$ operations, $0 \le l_i < 32$.
When multiple monsters with health $h_1, h_2, \dots, h_c$ meet at the same attraction $i$, they merge into one monster with health $h'$, which is the result of applying the $s_i$ operation to $h_1, h_2, \dots, h_c$. That is: if $s_i$ is &, the merged health $h' = h_1\ \mathrm{AND}\ h_2\ \mathrm{AND}\ \dots\ \mathrm{AND}\ h_c$; if $s_i$ is |, the merged health $h' = h_1\ \mathrm{OR}\ h_2\ \mathrm{OR}\ \dots\ \mathrm{OR}\ h_c$. Subsequently, if this monster is at the park's exit, it leaves the park. In each wave of monsters, the first monster to leave the park is called the Winner. The initial health values of all monsters and the health of the Winner when it leaves the park are recorded.
A monster dies if and only if one of the following conditions is met (a dead monster will never move or participate in merging):
There are no roads starting from the attraction where the monster is located, and the monster is not at the exit.
The monster's health is $0$. This means the monster may die on a road or immediately after merging.
The time elapsed since all monsters entered the park exceeds $k$ minutes, where $k$ is the lifespan of the monsters.
You may assume that by day $i+1$, all monsters that entered on day $i$ have either left the park or died.
However, after $m$ days, a natural disaster severely damaged the park. Monster City hopes to reconstruct the park based on these $m$ days of records, but this is difficult, so they have asked for your help—of course, you only need to design any scheme that satisfies all $m$ days of records.
Input
The input files rebuild1.in ~ rebuild10.in are available for download.
The first line contains $3$ integers $n, m, k$, representing the number of monsters entering each day, the number of days, and the lifespan of the monsters, respectively.
The next $2m$ lines contain the records for $m$ days. For each day $i$ ($1 \le i \le m$), the $(2i-1)$-th line contains $n$ integers $h_{i,1}, h_{i,2}, \dots, h_{i,n}$, representing the initial health of the $n$ monsters entering the park on day $i$. The $(2i)$-th line contains $1$ integer $w_i$, representing the health of the Winner on day $i$ when it leaves the park. It is guaranteed that a Winner exists every day.
Output
For the given $10$ input files rebuild1.in ~ rebuild10.in, you need to submit your output files rebuild1.out ~ rebuild10.out, respectively.
The first line contains $2$ integers $v$ and $e$, representing the number of attractions and the number of roads, where $n < v \le 100$ and $0 \le e \le 500$.
The second line contains a string $s$ of length $v$, where the $i$-th character $s_i$ is either & or |, representing the flag of the $i$-th attraction.
From the $3$-rd line to the $e+2$-th line, each line describes a road. The $i+2$-th line contains four values (numbers or characters) $a_i, b_i, t_i, l_i$, representing the start, end, flag, and weight of the $i$-th road, respectively. $1 \le a_i, b_i \le v$, and the flag is one of &, |, ~, <, >. Specifically, when $t_i$ is ~, $l_i$ is not provided. Multiple roads between two attractions are allowed, and roads with the same start and end points are also allowed.
You may output any valid scheme. It is guaranteed that such a scheme exists.
Examples
Input 1
2 4 2 11 1 20 11 2 18 11 3 16 18 12 12
Output 1
4 4 ||&& 1 3 | 0 2 3 ~ 2 4 & 12 3 4 < 1
Note 1
The sample output is one possible reconstruction of the park. Taking the monsters on day $1$ as an example:
Initially, there are $2$ monsters located at attractions $1$ and $2$ with health $11$ and $1$, respectively.
In the $1$-st minute, the monster at attraction $1$ moves along the road to attraction $3$, and its health becomes $11\ \mathrm{OR}\ 0 = 11$. The monster at attraction $2$ splits into $2$ monsters: one moves along the road to attraction $3$, and its health becomes $\mathrm{NOT}\ 1 = 4294967294$; the other moves along the road to attraction $4$, and its health becomes $1\ \mathrm{AND}\ 12 = 0$, so this split monster dies before entering the attraction. Subsequently, the $2$ monsters at attraction $3$ merge into $1$ monster with health $11\ \mathrm{AND}\ 4294967294 = 10$. At this point, only attraction $3$ has $1$ monster.
In the $2$-nd minute, the monster at attraction $3$ moves along the road to attraction $4$. Attraction $4$ is the exit, so the monster leaves the park and becomes the Winner.
Therefore, the Winner's health for this group of monsters is $20$.
Subtasks
We provide $10$ scoring files rebuild1.ans ~ rebuild10.ans. Each scoring file contains $10$ lines, with each line $i$ containing a scoring parameter $a_i$, the meaning of which is explained below.
Each test case is scored individually. For each test case, if the output format is invalid, you receive $0$ points. If the output is valid but only some of the $m$ records are satisfied, you may still receive partial points.
In your scheme, if the number of satisfied records is $x_{user}$, your score is given by the table below:
| Score | Condition | Score | Condition |
|---|---|---|---|
| $10$ | $x_{user} \ge a_{10}$ | $5$ | $x_{user} \ge a_5$ |
| $9$ | $x_{user} \ge a_9$ | $4$ | $x_{user} \ge a_4$ |
| $8$ | $x_{user} \ge a_8$ | $3$ | $x_{user} \ge a_3$ |
| $7$ | $x_{user} \ge a_7$ | $2$ | $x_{user} \ge a_2$ |
| $6$ | $x_{user} \ge a_6$ | $1$ | $x_{user} \ge a_1$ |
If none of the conditions in the table are met, you receive $0$ points; if multiple conditions are met, you receive the highest possible score.
Implementation Details
To test your output, first navigate to the problem directory in your terminal (for Windows users, please use cmd). (Assume you have placed the input/output files and the checker in a folder named rebuild)
cd rebuild
We provide a tool called checker to test whether your output file is acceptable. To use this tool, run the following in your terminal:
./checker_linux64 <case_no>
where <case_no> is the number of the test data. For example:
./checker_linux64 3
will test if rebuild3.out is acceptable. (Windows users should use checker_win32 3. If you are on Windows 64-bit, it can run 32-bit applications.)
We also provide a Linux 32-bit version: checker_linux32. If Linux users find they cannot run the program, please try executing chmod +x checker_linux64 or chmod +x checker_linux32 and try again.
After you run this program, the checker will provide the test results based on your output file.
Please do not modify the input files to prevent unpredictable errors in the checker.
Additionally, you can use the following command in the terminal:
./checker_linux64 –w <case_no>
to output the positions and health values of the monsters during their progression each day for test case <case_no> into a file named report.log. Note that report.log may be very large; in extreme cases, the file size can be approximately $150\texttt{MB}$.