Background

This is a communication problem and cannot be judged for now.

Problem Description

The Cyberland Circuit Society has a total of $n$ members. Each member has a favorite number and a unique name that is different from everyone else’s name. (It is not guaranteed that everyone’s favorite number is different.)

In total, these members have sent $m$ letters to each other. Each letter contains a sender and a recipient. The content of the letter is exactly the sender’s favorite number.

After all letters are sent, each member will compute the sum of the numbers contained in the letters they received (the senders’ favorite numbers), take this sum modulo $65536$ ($2^{16}$), and use the result as their final stored number.

Your task is to determine the final stored number for each person.

However, things are not as simple as they look. Alice, Bob, and Circuit plan to solve this problem in a slightly more complex way. Specifically:

• Alice knows all information about the $n$ members (their names and their favorite numbers), but Alice does not know anything about the $m$ letters. She needs to send Circuit a binary string of length at most $10^5$.

• Bob knows all information about the $m$ letters (the names of the sender and recipient of each letter), but Bob does not know anything about the $n$ members. He needs to send Circuit a binary string of length at most $10^5$.

• Circuit is a circuit that can receive the binary strings sent by Alice and Bob, and then produce a binary string of $16n$ bits as its output. However, its computing power is limited: Circuit can only perform basic logical operations (such as AND, OR, NOT).

Below, we describe the working mechanism of the circuit in detail.

Circuit operation details

A gate is the basic component of the circuit. A gate has either zero or two boolean signals as input, and one boolean signal as output. There are two types of gates in the circuit: input gates and computation gates.

• Input gates have no input boolean signals, and are used to represent one bit of the binary strings input by Alice and Bob.
  • There are a total of $l_A + l_B$ input gates, numbered from $0$ to $l_A + l_B - 1$ in order. Here $l_A, l_B$ are the lengths of the binary strings provided by Alice and Bob, respectively.
  • For any $0\leq i < l_A$, the output of gate $i$ is the $i$-th bit of the binary string provided by Alice.
  • For any $0\leq i < l_B$, the output of gate $i + l_A$ is the $i$-th bit of the binary string provided by Bob.
• Computation gates have two inputs and are used for computation.
  • The numbering of computation gates starts from $l_A + l_B$.
  • For each computation gate, you need to provide the indices of two related gates, which represent the boolean signal inputs of this computation gate; and a number $p$ ($0\leq p\leq 15$), which represents the type of this computation gate.
    • To avoid circular dependencies, the two indices used as inputs must be smaller than the index of this computation gate.
    • Suppose the outputs of the two related gates are $x_0, x_1$, then the output of this computation gate is:

$$f(p,x_0,x_1)=\left \lfloor \frac{p}{2^{x_0+2x_1}} \right \rfloor \bmod 2$$

Here are some examples that may be useful:

$x_0$	$x_1$	$x_0$ AND $x_1$（$f(8,x_0,x_1)$）	$x_0$ OR $x_1$（$f(14,x_0,x_1)$）	$x_0$ XOR $x_1$（$f(6,x_0,x_1)$）	NOT $x_0$（$f(5,x_0,x_1)$）
$0$	$0$	$0$	$0$		$1$
$1$			$1$	$1$	$0$
$0$	$1$				$1$
$1$		$1$		$0$

Implementation details

Please note:

• All array indices start from $0$. For example, if a is an array of length n, then a[0] through a[n-1] are valid elements of the array. Accessing an index outside this range may cause an out-of-bounds error.
• All strings end with the null character \0.

You should implement the following procedures:

Alice

int alice(const int n, const char names[][5],
          const unsigned short numbers[], bool outputs_alice[]);

Type	Value	Length	Meaning	Constraints
Input	n	$1$	$n$	$0\leq n\leq 700$
	names	$n$	The name of each member.	All member names are distinct. Names contain only lowercase English letters and have length at most $4$.
	numbers		Each member’s favorite number.	Favorite numbers are integers from $0$ to $65535$.
Output	outputs_alice	$l_A$	The binary string sent to Circuit.
	(return value)	$1$	$l_A$	You must ensure $l_A$ does not exceed $10^5$. Also, when $n$ is the same, $l_A$ must be the same.

Bob

int bob(const int m, const char senders[][5], 
        const char recipients[][5], bool outputs_bob[]);

Type	Value	Length	Meaning	Constraints
Input	m	$1$	$m$	$0\leq m\leq 1000$
	senders	$m$	The sender name of each letter.	All names must appear in Alice’s input.
	recipients		The recipient name of each letter.
Output	outputs_bob	$l_B$	The binary string sent to Circuit.
	(return value)	$1$	$l_B$	You must ensure $l_B$ does not exceed $10^5$. Also, when $m$ is the same, $l_B$ must be the same.

Circuit

To make Circuit’s computation process the same as a normal circuit, you cannot directly access the binary strings that Alice and Bob send to Circuit. You only need to know the lengths of these two strings, and output the circuit structure based on the lengths.

Type	Value	Length	Meaning	Constraints
Input	la	$1$	$l_A$
	lb		$l_B$
Output	operations	$l$	The operation type executed by each gate in the circuit.	Each element is an integer from $0$ to $15$.
	operands		The indices of the gates providing boolean signal inputs for each computation gate.	Input gate indices are guaranteed to be smaller than the current computation gate index.
	outputs_circuit	$n$	The indices of the circuit’s output gates.	outputs_circuit[i][j] represents the $j$-th bit (counting from the least significant bit) of the final stored number of member $i$. Members are indexed in the order of Alice’s input.
	(return value)	$1$	$l$, representing the number of gates used in the circuit (including input gates).	You must ensure $l\leq 2\times 10^7$.

Although you may modify the information of gates with indices smaller than $l_A+l_B$ in the operations and operands arrays, the interactive library will ignore such modifications.

Example

Consider the following sample call sequence:

alice(3, {"alic", "bob", "circ"}, {10000, 20000, 30000}, outputs_alice); 
bob(5, {"alic", "bob", "bob", "circ", "circ"}, 
    {"circ", "circ", "alic", "circ", "circ"}, outputs_bob);

This sample represents the following scenario:

• Alice knows that there are $3$ members. The member named alic has favorite number $10000$, and so on. A possible output of alice() is:

  • The return value of alice() is $2$, meaning $l_A=2$.
  • In alice(), set outputs_alice[0] = 1, outputs_alice[1] = 0, meaning the binary string returned by Alice is $10$.

• Bob knows that there are $5$ letters. The first letter is sent from alic and received by circ, and so on. A possible output of bob() is:

  • The return value of bob() is $3$, meaning $l_B=3$.
  • In bob(), set outputs_bob[0] = 1, outputs_bob[1] = 1, outputs_bob[2] = 0, meaning the binary string returned by Bob is $110$.

Based on the previous outputs of alice() and bob(), the interactive library will call:

circuit(2, 3, operations, operands, outputs_circuit);

One correct output of circuit() is:

• The return value of circuit() is $7$, meaning we added two computation gates, labeled $5$ and $6$.
• In circuit(), set the operations, operands, and outputs_circuit arrays as follows:
  • operations = {-1, -1, -1, -1, -1, 8, 14}. Here we use -1 to represent ignored information from input gates.
  • operands = {{-1, -1}, {-1, -1}, {-1, -1}, {-1, -1}, {-1, -1}, {0, 4}, {2，5}}.
  • outputs_circuit = {{5, 5, 5, 5, 5, 6, 5, 5, 5, 6, 6, 6, 5, 5, 6, 5}, ...} . The array is long; see abc.cpp in the attachment for the full array.

According to the output of circuit(), Circuit’s computation process is:

• Add a computation gate of type $8$, numbered $5$, whose inputs come from input gate $0$ and input gate $4$. The output of gate $0$ is the $0$-th bit of Alice’s string, i.e. $1$; the output of gate $4$ is the $2$-nd bit of Bob’s string, i.e. $0$. So the output of computation gate $5$ is $f(8,0,1)=0 \operatorname{AND} 1=0$.
• Add a computation gate of type $14$, numbered $6$, whose inputs come from input gate $2$ and computation gate $5$. The output of gate $2$ is the $0$-th bit of Bob’s string, i.e. $1$; the output of gate $5$ is $0$. So the output of computation gate $6$ is $f(14,1,0)= 1 \operatorname{OR} 0=1$.
• output_circuit[0] represents the final stored number of alic, i.e. $(0100111000100000)_2 = 20000$. Since alic received only one letter from bob, alic’s final result is $20000$.
• bob’s final stored number should be $0$ because he did not receive any letters; circ’s final stored number should be $(10000 + 20000 + 30000 + 30000) \bmod 65536 = 24464$.

The attached abc.cpp can pass this sample, but we do not guarantee that it can pass other test cases.

Constraints

For all test cases:

• $0\leq n\leq 700,0\leq m\leq 1000$.
• All member names are distinct, have maximum length $4$, and consist only of lowercase English letters.
• Each member’s favorite number is an integer between $0$ and $65535$.
• All sender and recipient names appear in Alice’s input array names.
• The memory limit for both alice() and bob() is $2048$ MiB, and the time limit for both is $0.02$ seconds.
• The memory limit for circuit() is $2048$ MiB, and the time limit is $7$ seconds.

In the final test, alice() and bob() may be called multiple times in a single test case. The time limit for each call is $0.02$ seconds.

Subtasks

Subtask Type A (12 points)

Subtasks 1, 2, 3 are of Type A. Type A guarantees:

• $n=1$.

Each subtask has the following additional constraints:

• Subtask 1 (4 points): $m=0$.
• Subtask 2 (4 points): $0\leq m\leq 1$.
• Subtask 3 (4 points): $0\leq m\leq 1000$.

Subtask Type B (54 points)

Subtasks 4, 5, 6 are of Type B. Type B guarantees:

• $0\leq n\leq 30,\frac{n}{2}\leq m\leq n^2$.
• There do not exist two letters with the same sender and recipient.
• All member names appear in Bob’s input (that is, each member either sent at least one letter or received at least one letter).

Each subtask has the following additional constraints:

• Subtask 4 (24 points): $n = 26$. All member names are single English letters, and in Alice’s input, the member names are in order from a to z.
• Subtask 5 (24 points): $n = 26$.
• Subtask 6 (6 points): No additional constraints.

Subtask Type C (34 points)

Subtasks 7, 8, 9 are of Type C. Type C guarantees:

• $0\leq n\leq 700,0\leq m\leq 1000$.

Each subtask has the following additional constraints:

• Subtask 7 (18 points): $n=676$. All member names are exactly two English letters, and in Alice’s input, member names are sorted in increasing lexicographical order (in other words, in the order aa, ab, ac, ..., az, ba, ..., bz, ca, ..., zz).
• Subtask 8 (10 points): $n = 676$.
• Subtask 9 (6 points): No additional constraints.

Sample

Sample grader program

The sample grader program reads input in the following format:

• Line $1$: $n\quad m$.
• Line $2+i$ ($0\leq i\leq n-1$): $names_i\quad numbers_i$.
• Line $2+n+i$ ($0\leq i\leq m-1$): $senders_i\quad recipients_i$.

The sample grader program prints your answer in the following format:

• If the program terminates successfully, the sample interactor will output $n$ lines, each containing one integer, representing the final stored number computed by your circuit for each member.
• Otherwise, the sample interactor will not output anything to standard output, and will write an error message to the file abc.log in the directory.
• In addition, the sample interactor will output the values of $l_A, l_B, l$ and the running time of each function to abc.log.

The sample grader program will not check the memory limit, and will not check the constraint that when $n$ / $m$ are the same, $l_A$ / $l_B$ must be the same.

Hint

Translated by ChatGPT 5