abc (APIO contest)
Time limit: 10 seconds | Memory limit: 2048 MB | Task type: interactive
Algorithms: multiplexer, bitmask, constructive

# Alice, Bob, and Circuit

![APIO2023 Tasks English (ISC)](_page_0_Picture_0.jpeg)

The Cyberland Circuit Foundation consists of $n$ members. Each member has his/her favorite number and a unique name (the favorite numbers may not be distinct).

$m$ letters have been sent between the members. Each letter has a sender and a recipient, and the content of the letter is the sender's favorite number.

Each member calculates the sum of the contents (senders' favorite numbers) they received and takes the modulo of 65536 (i.e., $2^{16}$) as his/her result number.

Your task is to determine all result numbers.

However, the situation is not as straightforward as it seems. Alice, Bob, and Circuit decide to solve this problem in a slightly more complicated way:

- Alice knows all $n$ members (name and favorite number), but knows no information about letters. She needs to send a binary string to Circuit with a length of no more than $10^5$.
- Bob knows all $m$ letters (sender and recipient's name), but knows no information about members. He needs to send a binary string to Circuit with a length of no more than $10^5$.
- Circuit can receive binary strings sent by Alice and Bob, and subsequently generate a binary string comprising $16n$ bits as output. However, due to its limited computational power, Circuit is only capable of performing basic logical operations (e.g., AND, OR, NOT).

In the following, we will introduce how the circuit works in detail.

### Circuit Details

The gate is the basic element of a circuit. A gate consists of zero or two boolean inputs(depending on the type of gate), and one boolean output. There are two types of gates: input gates and computation gates.

- Input gates have no input and represent the bits from binary strings sent by Alice and Bob.
    - There will be $l_A + l_B$ input gates, labeled from 0 to ($l_A + l_B - 1$), where $l_A$ and $l_B$ are the lengths of the strings from Alice and Bob, respectively.
    - For $0 \le i < l_A$, the output of the $i$-th gate is the $i$-th bit of the string from Alice;
    - For $0 \le i < l_B$, the output of the $(i + l_A)$-th gate is the $i$-th bit of the string from Bob.
- Computation gates have two inputs and represent the computation process.
    - The labels for computation gates start from $(l_A + l_B)$.
- For each computation gate, you should provide labels of two dependent gates for input, and the operation type $p$ (0 ≤ $p$ ≤ 15).
    - To prevent circular dependencies, the labels of the two dependent gates must be smaller than the label of the computation gate.
    - If the outputs of its two dependent gates are $x_0$ and $x_1$ respectively ($x_0, x_1 \in \{0, 1\}$), then the output of the computation gate is:

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

Here are some examples that may be useful for you:

| $x_0$ | $x_1$ | $x_0 \text{ AND } x_1$ <br> $f(8, x_0, x_1)$ | $x_0 \text{ OR } x_1$ <br> $f(14, x_0, x_1)$ | $x_0 \text{ XOR } x_1$ <br> $f(6, x_0, x_1)$ | $\text{NOT } x_0$ <br> $f(5, x_0, x_1)$ |
|-------|-------|-------------------------------------------------|------------------------------------------------|-------------------------------------------------|-------------------------------------------|
| 0     | 0     | 0                                               | 0                                               | 0                                               | 1                                         |
| 1     | 0     | 0                                               | 1                                               | 1                                               | 0                                         |
| 0     | 1     | 0                                               | 1                                               | 1                                               | 1                                         |
| 1     | 1     | 1                                               | 1                                               | 0                                               | 0                                         |

# Implementation Details

Please note:

- All array indices start from 0. For example, if a is an array of length n, then a[0] to a[n-1] are valid data, accessing indices beyond that range may cause an out-of-bounds error.
- All strings are terminated by a null character \0.

You should implement the following procedures:

## Alice

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

| Direction | Value | Length | Meaning                     | Constraint                                                                                                                       |
|-----------|-------|--------|-----------------------------|----------------------------------------------------------------------------------------------------------------------------------|
| Input     | n     | 1      | n                           | $0 \le n \le 700$                                                                                                                |
|           | names | n      | The name of each member.    | All names are distinct, consisting of lowercase English letters only, and have a maximum length of 4 characters.                |
|           | numbers | $n$    | The favorite number of each member.   | Each number is in the range from 0 to 65535.                                                                                      |
| Output    | outputs_alice | $l_A$ | The binary string is sent to Circuit. |                                                                                                                  |
|           | (Return value) | 1      | $l_A$                         | You need to make sure that $l_A$ does not exceed $10^5$ and when $n$ is the same, $l_A$ must be fixed.               |

## Bob

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

| Direction | Value          | Length | Meaning                              | Constraint                                                                   |
|-----------|----------------|--------|--------------------------------------|----------------------------------------------------------------------------|
| Input     | m              | 1      | $m$                                  | $0 \le m \le 1000$                                                           |
|           | senders        | $m$    | The sender's name on each letter.    | All names appear in Alice's input                                            |
|           | recipients     | $m$    | The recipient's name on each letter. |                                                                              |
| Output    | outputs_bob    | $l_B$  | The binary string is sent to Circuit. | You need to make sure that $l_B$ does not exceed $10^5$ and when $m$ is the same, $l_B$ must be fixed. |
|           | (Return value) | 1      | $l_B$                                |                                                                              |

### Circuit

To ensure that the computation process of the Circuit is like a general circuit, you cannot directly obtain the binary strings sent from Alice and Bob to Circuit. You only know the lengths of these two strings and output the circuit structure.

```c++
int circuit(const int la, const int lb, int operations[], int operands[][2], int outputs_circuit[][16]);
```

| Direction | Value           | Length | Meaning                                                                    | Constraint                                                                                                                                                                                          |
|-----------|-----------------|--------|----------------------------------------------------------------------------|------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| Input     | la              | 1      | $l_A$                                                                      |                                                                                                                                                                                                    |
|           | lb              | 1      | $l_B$                                                                      |                                                                                                                                                                                                    |
|           | operations      | $l$    | The type of operation performed by each gate in the circuit.               | An integer from 0 to 15.                                                                                                                                                                           |
|           | operands        | $l$    | The operand used by each gate in the circuit.                              | The number must be less than the label of the current gate.                                                                                                                                        |
| Output    | outputs_circuit | $n$    | The gate label of the circuit output.                                      | `outputs_circuit[i][j]` denotes the *j*-th bit (counting from the least significant bit) of the final result for the *i*-th member. The members are ordered according to Alice's input. |
|           | (Return value)  | 1      | $l$, which represents the total number of gates (including input gates). | You need to ensure that $l \le 2 \times 10^7$                                                                                                                                                      |

Although you can modify the information of gates with indices less than $l_A + l_B$ in the operations and operands arrays, the grader would ignore such modification.

# Example

Consider the following calls:

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

It represents the following scenario:

- Alice knows there are 3 members, the member with the name `alic` has a favorite number 10000, etc. A possible output for alice() is that,
    - The return value of alice() is 2, representing $l_A = 2$.
    - Inside alice() function, set `outputs_alice[0]` = 1, `outputs_alice[1]` = 0, representing that the result binary string is 10.
- Bob knows there are 5 letters, the first letter is from `alic` to `circ`, etc. A possible output for bob() is that,
    - The return value of bob() is 3, representing $l_B = 3$.
    - Inside bob() function, set `outputs_bob[0]` = 1, `outputs_bob[1]` = 1, `outputs_bob[2]` = 0, representing that the result binary string is 110.

Based on previous outputs for alice() and bob(), there will be the following call:

```c++
circuit(2, 3, operations, operands, outputs_circuit);
```

#### A correct output for this function would be

- The return value of circuit() is 7, meaning that we add two computation gates, labeled 5 and 6.
- Inside circuit(), set operations, operands, and outputs_circuit in the following way:
    - operations = {-1, -1, -1, -1, -1, 8, 14}, where 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 a bit long, you can check abc.cpp in the attachments for the full array.

According to the output, the computation procedure is that,

- Add a type 8 computation gate, with input from gate 0 and gate 4. The output of gate 0 is the 0-th bit of the string from Alice, which is 1; The output of gate 4 is the 2-nd bit of the string from Bob, which is 0. So the output for gate 5 is $f(8, 0, 1) = 0 \text{ AND } 1 = 0$.
- Add a type 14 computation gate, with input from gate 2 and gate 5. The output of gate 2 is the 0-th bit of the string from Bob, which is 1; The output of gate 5 is 0. So the output for gate 6 is $f(14, 1, 0) = 1 \text{ OR } 0 = 1$.
- `output_circuit[0]` represents the final result of `alic`, which is (0100111000100000)$_2$ = 20000. Since `alic` only receives a letter from `bob`, the final result of `alic` is 20000.
- The final result of `bob` should be 0, since he receives no letter; The final result of `circ` should be $(10000 + 20000 + 30000 + 30000) \mod 65536 = 24464$.

abc.cpp in the attachments can pass this example, but we do not guarantee that it can pass other test cases.

# Constraints

For all test cases:

- $0 \le n \le 700$, $0 \le m \le 1000$.
- All names are distinct, consisting of lowercase English letters only, and have a maximum length of 4 characters.
- The favorite number of each member is in the range of 0 to 65535.
- The names of all senders and recipients appear in Alice's input array `names`.
- alice() and bob() have a memory limit of 2048 MiB and a time limit of 0.02 seconds, respectively.
- circuit() has a memory limit of 2048 MiB and a time limit of 7 seconds.

**For the final evaluation, alice() and bob() may be called multiple times in a single test case.** The time limit of 0.02 second is for each call.

# Subtasks

Subtask Type A (12 points)

Subtask 1,2,3 are in subtask type A, where $n = 1$.

Each subtask has the following additional constraints:

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

## Subtask Type B (54 points)

Subtask 4,5,6 are in subtask type B, where:

- $0 \le n \le 30$, $\frac{n}{3} \le m \le n^2$.
- There are no two letters with the same sender and recipient.
- All member names appear in Bob's input (i.e., each member either sends at least one letter or receives at least one letter).

Each subtask has the following additional constraints:

- Subtask 4 (24 points): $n = 26$, All members' names are single lowercase letters, and in Alice's input, they appear in order from a to z.
- Subtask 5 (24 points): $n = 26$.
- Subtask 6 (6 points): No special restrictions.

## Subtask Type C (34 points)

Subtask 7,8,9 are in subtask type C, where $0 \le n \le 700$, $0 \le m \le 1000$.

Each subtask has the following additional constraints:

- Subtask 7 (18 points): $n = 676$, all members' names are two lowercase letters, and in Alice's input, they appear in lexicographical order (e.g., aa, ab, ac, ..., az, ba, ..., bz, ca, ..., zz).
- Subtask 8 (10 points): $n = 676$.
- Subtask 9 (6 points): No additional constraints.

# Sample Grader

The sample grader reads the input in the following format:

- Line 1: $n$ $m$
- Line 2 + $i$ (0 ≤ $i$ ≤ $n$ − 1): $names_i$ $numbers_i$
- Line 2 + $n$ + $i$ (0 ≤ $i$ ≤ $m$ − 1): $senders_i$ $recipients_i$.

The sample grader outputs in the following format:

- If the program finishes successfully, the sample grader will output $n$ lines, each containing an integer, representing the final result calculated by functions you implement for each member.
- Otherwise, the grader would output nothing to stdout and prints the error messages to the file abc.log in the directory.
- Additionally, the sample grader will output values of $l_A$, $l_B$, $l$ and the running time of each function to abc.log.

**The sample grader will not check the memory limit and the restriction that for the same $n/m$, $l_A/l_B$ must be equal.**

Starter code:
grader.cpp: #include "abc.h"
#include <chrono>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <sstream>
#include <vector>
using namespace std;

const int MAX_LA = 100000;
const int MAX_LB = 100000;
const int MAX_L = 20000000;

void fatal(const string& msg) {
    cerr << msg << endl;
    exit(1);
}

void ensureImpl(bool condition, const char* conditionStr) {
    if (condition)
        return;
    fatal("Condition does not satisfy: " + string(conditionStr));
}

#define ensure(x...) ensureImpl(x, #x)

template <typename F>
void timed(const string& name, const F& func) {
    cerr << "Running " << name << "..." << endl;
    auto start = chrono::high_resolution_clock::now();
    func();
    auto end = chrono::high_resolution_clock::now();
    auto duration = chrono::duration_cast<chrono::nanoseconds>(end - start);
    cerr << name << " took " << fixed << setprecision(6) << (double) duration.count() / 1e9 << " seconds" << endl;
}

int main() {
    freopen("abc.log", "w", stderr);
    // ==================== Read Input ====================
    int n, m;
    cin >> n >> m;
    ensure(0 <= n && n <= 700);
    ensure(0 <= m && m <= 1000);

    auto readUshort = [&]() {
        string s;
        cin >> s;
        stringstream ss(s);
        unsigned short x;
        ss >> x;
        if (s != to_string(x))
            fatal("Invalid input for unsigned short: " + s);
        return x;
    };
    vector<pair<string, unsigned short>> students;
    map<string, unsigned short> studentsMap;
    for (int i = 0; i < n; i++) {
        string name;
        cin >> name;
        if (name.empty())
            fatal("Expected name");
        if (name.size() > 4)
            fatal("Name too long: " + name);
        bool ok = true;
        for (char c : name)
            if (c < 'a' || c > 'z')
                ok = false;
        if (!ok)
            fatal("Invalid name: " + name);
        unsigned short number = readUshort();
        students.emplace_back(name, number);

        if (studentsMap.count(name))
            fatal("Duplicate name: " + name);
        studentsMap[name] = number;
    }

    auto readExistingName = [&] {
        string name;
        cin >> name;
        if (!studentsMap.count(name))
            fatal("Unknown name in Bob's input: " + name);
        return name;
    };
    vector<pair<string, string>> messages;
    for (int i = 0; i < m; i++) {
        string sender = readExistingName();
        string recipient = readExistingName();
        messages.emplace_back(sender, recipient);
    }

    // ==================== Call Alice ====================
    char (*aliceNames)[5] = new char[n][5];
    memset(aliceNames[0], 0, n * 5);
    unsigned short* aliceNumbers = new unsigned short[n];
    bool* aliceOutputs = new bool[MAX_LA];
    memset(aliceOutputs, 0, MAX_LA);
    for (int i = 0; i < n; i++) {
        strcpy(aliceNames[i], students[i].first.c_str());
        aliceNumbers[i] = students[i].second;
    }
    int la;
    timed("Alice", [&]() {
        la = alice(n, aliceNames, aliceNumbers, aliceOutputs);
    });
    cerr << "la = " << la << endl;
    ensure(0 <= la && la <= MAX_LA);

    // ==================== Call Bob ====================
    char (*bobSenders)[5] = new char[m][5];
    memset(bobSenders[0], 0, m * 5);
    char (*bobRecipients)[5] = new char[m][5];
    memset(bobRecipients[0], 0, m * 5);
    bool* bobOutputs = new bool[MAX_LB];
    memset(bobOutputs, 0, MAX_LB);
    for (int i = 0; i < m; i++) {
        strcpy(bobSenders[i], messages[i].first.c_str());
        strcpy(bobRecipients[i], messages[i].second.c_str());
    }
    int lb;
    timed("Bob", [&]() {
        lb = bob(m, bobSenders, bobRecipients, bobOutputs);
    });
    cerr << "lb = " << lb << endl;
    ensure(0 <= lb && lb <= MAX_LB);

    // ==================== Call Circuit ====================
    int* circuitOperations = new int[MAX_L];
    memset(circuitOperations, 0xff, MAX_L * sizeof(int));
    int (*circuitOperands)[2] = new int[MAX_L][2];
    memset(circuitOperands[0], 0xff, MAX_L * 2 * sizeof(int));
    int (*circuitOutputs)[16] = new int[n][16];
    memset(circuitOutputs[0], 0xff, n * 16 * sizeof(int));
    int l;
    timed("Circuit", [&]() {
        l = circuit(la, lb, circuitOperations, circuitOperands, circuitOutputs);
    });
    cerr << "l = " << l << endl;
    ensure(0 <= l && l <= MAX_L);

    bool* values = new bool[l];
    memcpy(values, aliceOutputs, la * sizeof(bool));
    memcpy(values + la, bobOutputs, lb * sizeof(bool));
    for (int i = la + lb; i < l; i++) {
        int op = circuitOperations[i];
        if (op < 0 || op > 15)
            fatal("Invalid operation: " + to_string(op) + " at Circuit index " + to_string(i));
        int a = circuitOperands[i][0];
        int b = circuitOperands[i][1];
        if (a < 0 || a >= i)
            fatal("Invalid operand 0: " + to_string(a) + " at Circuit index " + to_string(i));
        if (b < 0 || b >= i)
            fatal("Invalid operand 1: " + to_string(b) + " at Circuit index " + to_string(i));
        bool x0 = values[a];
        bool x1 = values[b];
        values[i] = op >> (x0 + 2 * x1) & 1;
    }
    for (int i = 0; i < n; i++)
        for (int j = 0; j < 16; j++)
            if (circuitOutputs[i][j] < 0 || circuitOutputs[i][j] >= l)
                fatal("Invalid output: " + to_string(circuitOutputs[i][j]) + " at Circuit index " + to_string(i) + ", " + to_string(j));
    vector<unsigned short> answers;
    for (int i = 0; i < n; i++) {
        unsigned short ans = 0;
        for (int j = 0; j < 16; j++)
            ans |= (unsigned short) values[circuitOutputs[i][j]] << j;
        answers.push_back(ans);
    }

    // ==================== Calculate Reference Answer ====================
    map<string, unsigned short> referenceMap;
    for (int i = 0; i < m; i++)
        referenceMap[messages[i].second] += studentsMap[messages[i].first];
    bool ok = true;
    for (int i = 0; i < n; i++)
        if (answers[i] != referenceMap[students[i].first]) {
            ok = false;
            cerr << "Wrong answer for " << students[i].first << ": expected " << referenceMap[students[i].first] << ", but got " << answers[i] << endl;
        }
    if (ok)
        cerr << "Your answer seems correct" << endl;

    // ==================== Print Answer ====================
    for (int i = 0; i < n; i++)
        cout << answers[i] << '\n';

    return 0;
}

abc.h: #ifndef ABC_H
#define ABC_H


// Alice
int // returns la
alice(
    /*  in */ const int n,
    /*  in */ const char names[][5],
    /*  in */ const unsigned short numbers[],
    /* out */ bool outputs[]
);


// Bob
int // returns lb
bob(
    /*  in */ const int m,
    /*  in */ const char senders[][5],
    /*  in */ const char recipients[][5],
    /* out */ bool outputs[]
);


// Circuit
int // returns l
circuit(
    /*  in */ const int la,
    /*  in */ const int lb,
    /* out */ int operations[],
    /* out */ int operands[][2],
    /* out */ int outputs[][16]
);


#endif // ABC_H

abc.cpp: #include "abc.h"

// you may find the definitions useful
const int OP_ZERO    = 0;  // f(OP_ZERO,    x0, x1) = 0
const int OP_NOR     = 1;  // f(OP_NOR,     x0, x1) = !(x0 || x1)
const int OP_GREATER = 2;  // f(OP_GREATER, x0, x1) = (x0 > x1)
const int OP_NOT_X1  = 3;  // f(OP_NOT_X1,  x0, x1) = !x1
const int OP_LESS    = 4;  // f(OP_LESS,    x0, x1) = (x0 < x1)
const int OP_NOT_X0  = 5;  // f(OP_NOT_X0,  x0, x1) = !x0
const int OP_XOR     = 6;  // f(OP_XOR,     x0, x1) = (x0 ^ x1)
const int OP_NAND    = 7;  // f(OP_NAND,    x0, x1) = !(x0 && x1)
const int OP_AND     = 8;  // f(OP_AND,     x0, x1) = (x0 && x1)
const int OP_EQUAL   = 9;  // f(OP_EQUAL,   x0, x1) = (x0 == x1)
const int OP_X0      = 10; // f(OP_X0,      x0, x1) = x0
const int OP_GEQ     = 11; // f(OP_GEQ,     x0, x1) = (x0 >= x1)
const int OP_X1      = 12; // f(OP_X1,      x0, x1) = x1
const int OP_LEQ     = 13; // f(OP_LEQ,     x0, x1) = (x0 <= x1)
const int OP_OR      = 14; // f(OP_OR,      x0, x1) = (x0 || x1)
const int OP_ONE     = 15; // f(OP_ONE,     x0, x1) = 1


// Alice
int // returns la
alice(
    /*  in */ const int n,
    /*  in */ const char names[][5],
    /*  in */ const unsigned short numbers[],
    /* out */ bool outputs_alice[]
) {
    outputs_alice[0] = 1;
    outputs_alice[1] = 0;
    return 2;
}


// Bob
int // returns lb
bob(
    /*  in */ const int m,
    /*  in */ const char senders[][5],
    /*  in */ const char recipients[][5],
    /* out */ bool outputs_bob[]
) {
    outputs_bob[0] = 1;
    outputs_bob[1] = 1;
    outputs_bob[2] = 0;
    return 3;
}


// Circuit
int // returns l
circuit(
    /*  in */ const int la,
    /*  in */ const int lb,
    /* out */ int operations[],
    /* out */ int operands[][2],
    /* out */ int outputs_circuit[][16]
) {
    operations[5] = 8;
    operations[6] = 14;
    operands[5][0] = 0; operands[5][1] = 4;
    operands[6][0] = 2; operands[6][1] = 5;
    int final_results[] = {20000, 0, 24464};
    for(int i = 0; i < 3; ++i)
        for(int j = 0; j < 16; ++j)
            outputs_circuit[i][j] = 5 + (final_results[i] >> j & 1);
    return 7;
}


Grader code:
grader.cpp: #include "abc.h"
#include <chrono>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <sstream>
#include <vector>
using namespace std;

const int MAX_LA = 100000;
const int MAX_LB = 100000;
const int MAX_L = 20000000;

void fatal(const string& msg) {
    cerr << msg << endl;
    exit(1);
}

void ensureImpl(bool condition, const char* conditionStr) {
    if (condition)
        return;
    fatal("Condition does not satisfy: " + string(conditionStr));
}

#define ensure(x...) ensureImpl(x, #x)

template <typename F>
void timed(const string& name, const F& func) {
    cerr << "Running " << name << "..." << endl;
    auto start = chrono::high_resolution_clock::now();
    func();
    auto end = chrono::high_resolution_clock::now();
    auto duration = chrono::duration_cast<chrono::nanoseconds>(end - start);
    cerr << name << " took " << fixed << setprecision(6) << (double) duration.count() / 1e9 << " seconds" << endl;
}

int main() {
    freopen("abc.log", "w", stderr);
    // ==================== Read Input ====================
    int n, m;
    cin >> n >> m;
    ensure(0 <= n && n <= 700);
    ensure(0 <= m && m <= 1000);

    auto readUshort = [&]() {
        string s;
        cin >> s;
        stringstream ss(s);
        unsigned short x;
        ss >> x;
        if (s != to_string(x))
            fatal("Invalid input for unsigned short: " + s);
        return x;
    };
    vector<pair<string, unsigned short>> students;
    map<string, unsigned short> studentsMap;
    for (int i = 0; i < n; i++) {
        string name;
        cin >> name;
        if (name.empty())
            fatal("Expected name");
        if (name.size() > 4)
            fatal("Name too long: " + name);
        bool ok = true;
        for (char c : name)
            if (c < 'a' || c > 'z')
                ok = false;
        if (!ok)
            fatal("Invalid name: " + name);
        unsigned short number = readUshort();
        students.emplace_back(name, number);

        if (studentsMap.count(name))
            fatal("Duplicate name: " + name);
        studentsMap[name] = number;
    }

    auto readExistingName = [&] {
        string name;
        cin >> name;
        if (!studentsMap.count(name))
            fatal("Unknown name in Bob's input: " + name);
        return name;
    };
    vector<pair<string, string>> messages;
    for (int i = 0; i < m; i++) {
        string sender = readExistingName();
        string recipient = readExistingName();
        messages.emplace_back(sender, recipient);
    }

    // ==================== Call Alice ====================
    char (*aliceNames)[5] = new char[n][5];
    memset(aliceNames[0], 0, n * 5);
    unsigned short* aliceNumbers = new unsigned short[n];
    bool* aliceOutputs = new bool[MAX_LA];
    memset(aliceOutputs, 0, MAX_LA);
    for (int i = 0; i < n; i++) {
        strcpy(aliceNames[i], students[i].first.c_str());
        aliceNumbers[i] = students[i].second;
    }
    int la;
    timed("Alice", [&]() {
        la = alice(n, aliceNames, aliceNumbers, aliceOutputs);
    });
    cerr << "la = " << la << endl;
    ensure(0 <= la && la <= MAX_LA);

    // ==================== Call Bob ====================
    char (*bobSenders)[5] = new char[m][5];
    memset(bobSenders[0], 0, m * 5);
    char (*bobRecipients)[5] = new char[m][5];
    memset(bobRecipients[0], 0, m * 5);
    bool* bobOutputs = new bool[MAX_LB];
    memset(bobOutputs, 0, MAX_LB);
    for (int i = 0; i < m; i++) {
        strcpy(bobSenders[i], messages[i].first.c_str());
        strcpy(bobRecipients[i], messages[i].second.c_str());
    }
    int lb;
    timed("Bob", [&]() {
        lb = bob(m, bobSenders, bobRecipients, bobOutputs);
    });
    cerr << "lb = " << lb << endl;
    ensure(0 <= lb && lb <= MAX_LB);

    // ==================== Call Circuit ====================
    int* circuitOperations = new int[MAX_L];
    memset(circuitOperations, 0xff, MAX_L * sizeof(int));
    int (*circuitOperands)[2] = new int[MAX_L][2];
    memset(circuitOperands[0], 0xff, MAX_L * 2 * sizeof(int));
    int (*circuitOutputs)[16] = new int[n][16];
    memset(circuitOutputs[0], 0xff, n * 16 * sizeof(int));
    int l;
    timed("Circuit", [&]() {
        l = circuit(la, lb, circuitOperations, circuitOperands, circuitOutputs);
    });
    cerr << "l = " << l << endl;
    ensure(0 <= l && l <= MAX_L);

    bool* values = new bool[l];
    memcpy(values, aliceOutputs, la * sizeof(bool));
    memcpy(values + la, bobOutputs, lb * sizeof(bool));
    for (int i = la + lb; i < l; i++) {
        int op = circuitOperations[i];
        if (op < 0 || op > 15)
            fatal("Invalid operation: " + to_string(op) + " at Circuit index " + to_string(i));
        int a = circuitOperands[i][0];
        int b = circuitOperands[i][1];
        if (a < 0 || a >= i)
            fatal("Invalid operand 0: " + to_string(a) + " at Circuit index " + to_string(i));
        if (b < 0 || b >= i)
            fatal("Invalid operand 1: " + to_string(b) + " at Circuit index " + to_string(i));
        bool x0 = values[a];
        bool x1 = values[b];
        values[i] = op >> (x0 + 2 * x1) & 1;
    }
    for (int i = 0; i < n; i++)
        for (int j = 0; j < 16; j++)
            if (circuitOutputs[i][j] < 0 || circuitOutputs[i][j] >= l)
                fatal("Invalid output: " + to_string(circuitOutputs[i][j]) + " at Circuit index " + to_string(i) + ", " + to_string(j));
    vector<unsigned short> answers;
    for (int i = 0; i < n; i++) {
        unsigned short ans = 0;
        for (int j = 0; j < 16; j++)
            ans |= (unsigned short) values[circuitOutputs[i][j]] << j;
        answers.push_back(ans);
    }

    // ==================== Calculate Reference Answer ====================
    map<string, unsigned short> referenceMap;
    for (int i = 0; i < m; i++)
        referenceMap[messages[i].second] += studentsMap[messages[i].first];
    bool ok = true;
    for (int i = 0; i < n; i++)
        if (answers[i] != referenceMap[students[i].first]) {
            ok = false;
            cerr << "Wrong answer for " << students[i].first << ": expected " << referenceMap[students[i].first] << ", but got " << answers[i] << endl;
        }
    if (ok)
        cerr << "Your answer seems correct" << endl;

    // ==================== Print Answer ====================
    for (int i = 0; i < n; i++)
        cout << answers[i] << '\n';

    return 0;
}

abc.h: #ifndef ABC_H
#define ABC_H


// Alice
int // returns la
alice(
    /*  in */ const int n,
    /*  in */ const char names[][5],
    /*  in */ const unsigned short numbers[],
    /* out */ bool outputs[]
);


// Bob
int // returns lb
bob(
    /*  in */ const int m,
    /*  in */ const char senders[][5],
    /*  in */ const char recipients[][5],
    /* out */ bool outputs[]
);


// Circuit
int // returns l
circuit(
    /*  in */ const int la,
    /*  in */ const int lb,
    /* out */ int operations[],
    /* out */ int operands[][2],
    /* out */ int outputs[][16]
);


#endif // ABC_H

manager.cpp: #include <bits/stdc++.h>
#include <signal.h>
using namespace std;

void report_result(double score, string report_message){
	cout << score << endl;
	cerr << report_message << endl;
	exit(0);
}

static constexpr int TESTCASE = 60;
static constexpr int MAX_LA = 100000;
static constexpr int MAX_LB = 100000;
static constexpr char CIRCUIT_WORKING_CORRECT_OUTPUT[] = "Circuit Output Finished.\n";
static constexpr char CIRCUIT_SCORING_CORRECT_OUTPUT[] = "235fc77fd78da210d6b5a61b92603c4f\n";
static char buffer[10000003];
struct CONTENT{
	vector < string > content; bool aliceorbob;
	CONTENT(vector < string > _cont = vector < string > {}, bool f = 0){content = _cont; aliceorbob = f;}
	int numofline(){return content.size();}
	CONTENT split(int L , int R){
		if(L < 0 || R > numofline() || L > R)
			report_result(0, "Grader Error: split() argument invalid. Please Contact Admin.");
		return CONTENT(vector < string > (content.begin() + L, content.begin() + R));
	}
	void write(FILE* file){
		for(auto t : content){
            assert(t.back() == '\n');
            // fprintf(file, t.c_str());
            fputs(t.c_str(), file);
            // cerr << "Manager: written " << t << flush;
        }
		fflush(file);
	}
	void read(FILE* file, int line, bool check_for_binary_output = false){
		for(int i = 0 ; i < line ; ++i){
			char* res = fgets(buffer, 1e7, file);
			if(res == NULL)
				report_result(0, (string("Cannot get output from ") + (aliceorbob ? "Bob" : "Alice") + ". Possible problems: segmential fault / manual exit(0)").c_str());
			string str(res);
            // cerr << "Manager: read line " << str << flush;
			if(str.back() != '\n')
				report_result(0, "Grader Error: there exists a line longer than 10^7. If you do not print anything to stdout, please contact admin.");
            if(check_for_binary_output && i){
				bool binary = 1;
				for(int i = 0 ; i < (int)str.size() - 1 ; ++i)
					binary &= str[i] == '0' || str[i] == '1';
				if(!binary){
					// This line reports an error.
					report_result(0, str);
				}
			}
            if(check_for_binary_output && !i) {
                if (strncmp(res, "235fc77fd78da210d6b5a61b92603c4f", 32))
					report_result(0, str);
            }
			content.push_back(str);
		}
	}
	bool checkSameLength(){
        assert (content.size() >= 2);
        for (int i = 1; i < content.size(); ++i)
            if (content[i].size() != content[1].size())
                return false;
        return true;
	}
};

struct FIFO{
	FILE *USERTOMANAGER, *MANAGERTOUSER;
	void InitializePipe(char* UserToManagerFile, char* ManagerToUserFile){
		MANAGERTOUSER = fopen(ManagerToUserFile, "w");
		USERTOMANAGER = fopen(UserToManagerFile, "r");
		if(USERTOMANAGER == NULL || MANAGERTOUSER == NULL)
			report_result(0, "Grader Error: Cannot open pipe. Please Contact Admin.");
	}
	void Initialize(){
        fputs("Hello\n", MANAGERTOUSER);
		fflush(MANAGERTOUSER);
	}
    ~FIFO() {
        fputs("Goodbye\n", MANAGERTOUSER);
        fflush(MANAGERTOUSER);
        fclose(MANAGERTOUSER);
        fclose(USERTOMANAGER);
    }
	FILE* write_file(){return MANAGERTOUSER;}
	FILE* read_file(){return USERTOMANAGER;}
}Alice, Bob, Circuit;

int main(int argc, char** argv){
    signal(SIGPIPE, SIG_IGN);
    //cerr << "Manager: Hello world!" << endl;
	if(argc != 7){report_result(0, "Grader Error: argc should be 7 but get " + to_string(argc));}
	Alice.InitializePipe(argv[1], argv[2]);
	Bob.InitializePipe(argv[3], argv[4]);
	Circuit.InitializePipe(argv[5], argv[6]);
    //cerr << "Manager: initialize FIFO ok" << endl;
	
	CONTENT InputFile; InputFile.read(stdin, 2 * (TESTCASE + 1));
    //cerr << "Manager: read input ok" << endl;
	CONTENT AliceIn = InputFile.split(0, TESTCASE + 1), BobIn = InputFile.split(TESTCASE + 1 , 2 * (TESTCASE + 1));
	Alice.Initialize(); AliceIn.write(Alice.write_file()); 
	Bob.Initialize(); BobIn.write(Bob.write_file());
   // cerr << "Manager: write input to Alice and Bob ok" << endl;
	
	CONTENT AliceOut, BobOut; BobOut.aliceorbob = 1;
    //cerr << "Manager: before read from Alice" << endl;
	AliceOut.read(Alice.read_file(), TESTCASE + 1, true);
    //cerr << "Manager: read from Alice ok" << endl;
	BobOut.read(Bob.read_file(), TESTCASE + 1, true);
    //cerr << "Manager: read from Bob ok" << endl;

// final_grader_middle rephrase
	if(!AliceOut.checkSameLength())
		report_result(0, "Alice lengths are not all equal.");
	if(!BobOut.checkSameLength())
		report_result(0, "Bob lengths are not all equal.");
	int aliceLength = AliceOut.content[1].size() - 1, bobLength = BobOut.content[1].size() - 1;
	if(aliceLength < 0 || aliceLength > MAX_LA)
		report_result(0, "Alice Length exceeds " + to_string(MAX_LA));
	if(bobLength < 0 || bobLength > MAX_LB)
		report_result(0, "Bob Length exceeds " + to_string(MAX_LB));

	Circuit.Initialize();
	fprintf(Circuit.write_file(), "%d\n%d\n", aliceLength, bobLength);
    fflush(Circuit.write_file());

    //cerr << "Manager: write to Circuit ok" << endl;
	char* circuit_work_res = fgets(buffer, 1e7, Circuit.read_file());
	if(circuit_work_res == NULL || strcmp(circuit_work_res, CIRCUIT_WORKING_CORRECT_OUTPUT) != 0){
		// Circuit returns an error.
		report_result(0, circuit_work_res == NULL ? "Cannot get output from circuit. Possible problems: segmential fault / manual exit(0)" : circuit_work_res);
	}
    //cerr << "Manager: read from Circuit middle output ok" << endl;
	AliceIn.write(Circuit.write_file()); BobIn.write(Circuit.write_file());
	AliceOut.write(Circuit.write_file()); BobOut.write(Circuit.write_file());
    //cerr << "Manager: write everything to Circuit ok" << endl;

	char* scoring_res = fgets(buffer, 1e7, Circuit.read_file());
    int score = 0;
    if (scoring_res != NULL && !strcmp(scoring_res, CIRCUIT_SCORING_CORRECT_OUTPUT)) {
        score = 1;
        scoring_res = fgets(buffer, 1e7, Circuit.read_file());
    }
	report_result(score, scoring_res == NULL ? "Grader Error: Scoring Segmential Fault. Please Contact Admin." : scoring_res);
}
stub.cpp: /*

stub.cpp

Compile: g++ stub.cpp abc.cpp -std=c++11 -o stub -O2
Run as alice: ./stub 0
Run as bob: ./stub 1
Run as circuit: ./stub 2

*/

#include "abc.h"
#include <bits/stdc++.h>
using namespace std;

static constexpr int T = 60;
static constexpr int MAX_N = 700;
static constexpr int MAX_M = 1000;
static constexpr int MAX_LA = 100000;
static constexpr int MAX_LB = 100000;
static constexpr int MAX_L = 20000000;
static constexpr double TL_PER_ALICE = 0.02;
static constexpr double TL_PER_BOB = 0.02;
static constexpr double TL_PER_CIRCUIT = 7;
static constexpr char CIRCUIT_WORKING_CORRECT_OUTPUT[] = "Circuit Output Finished.\n";

// you may find the definitions useful
const int OP_ZERO    = 0;  // f(OP_ZERO,    x0, x1) = 0
const int OP_NOR     = 1;  // f(OP_NOR,     x0, x1) = !(x0 || x1)
const int OP_GREATER = 2;  // f(OP_GREATER, x0, x1) = (x0 > x1)
const int OP_NOT_X1  = 3;  // f(OP_NOT_X1,  x0, x1) = !x1
const int OP_LESS    = 4;  // f(OP_LESS,    x0, x1) = (x0 < x1)
const int OP_NOT_X0  = 5;  // f(OP_NOT_X0,  x0, x1) = !x0
const int OP_XOR     = 6;  // f(OP_XOR,     x0, x1) = (x0 ^ x1)
const int OP_NAND    = 7;  // f(OP_NAND,    x0, x1) = !(x0 && x1)
const int OP_AND     = 8;  // f(OP_AND,     x0, x1) = (x0 && x1)
const int OP_EQUAL   = 9;  // f(OP_EQUAL,   x0, x1) = (x0 == x1)
const int OP_X0      = 10; // f(OP_X0,      x0, x1) = x0
const int OP_GEQ     = 11; // f(OP_GEQ,     x0, x1) = (x0 >= x1)
const int OP_X1      = 12; // f(OP_X1,      x0, x1) = x1
const int OP_LEQ     = 13; // f(OP_LEQ,     x0, x1) = (x0 <= x1)
const int OP_OR      = 14; // f(OP_OR,      x0, x1) = (x0 || x1)
const int OP_ONE     = 15; // f(OP_ONE,     x0, x1) = 1

using BS = uint64_t;

static BS operator""_bs(unsigned long long x) {
    return x;
}

struct WAException : public runtime_error {
    WAException(const string& msg) : runtime_error(msg) { }
};

struct TLEException : public runtime_error {
    TLEException(const string& msg) : runtime_error(msg) { }
};

struct FailException : public runtime_error {
    FailException(const string& msg) : runtime_error(msg) { }
};

template <typename F>
static int grader_entry(const F& f) {
    try {
        // ios::sync_with_stdio(false);
        // cin.tie(nullptr);
        stringstream fout;
        f(fout);
        // cerr << "Stub: grader_entry() finished, output:\n" << fout.str() << flush;
        cout << "235fc77fd78da210d6b5a61b92603c4f\n" << fout.str() << flush;
        return 0;
    } catch (WAException& e) {
        cout << "WA " << e.what() << endl;
        return 0;
    } catch (TLEException& e) {
        cout << "TLE " << e.what() << endl;
        return 0;
    } catch (FailException& e) {
        cout << "FAIL " << e.what() << endl;
        return 0;
    } catch (exception& e) {
        cout << "FAIL " << "unexpected exception: " << e.what() << endl;
        return 0;
    } catch (...) {
        cout << "FAIL " << "unknown exception" << endl;
        return 0;
    }
};

static bool isValidName(const string& s) {
    if (s.empty() || s.size() > 4)
        return false;
    for (char c : s)
        if (c < 'a' || c > 'z')
            return false;
    return true;
}

static void readOkOrThrow() {
    string s;
    cin >> s;
    if (s == "235fc77fd78da210d6b5a61b92603c4f")
        return;
    char c; cin.get(c);
    if (c != '\n')
        throw FailException("Expected newline after verdict");
    string msg;
    getline(cin, msg);
    if (s == "WA")
        throw WAException(msg);
    if (s == "TLE")
        throw TLEException(msg);
    if (s == "FAIL")
        throw FailException(msg);
    throw FailException("Unknown verdict: " + s + " " + msg);
}


static int alice() {
    cerr << "Stub: alice()" << endl;
    return grader_entry([&](stringstream& fout) {
        int n; cin >> n;
        cerr << "Stub: alice n=" << n << endl;
        if (n < 0 || n > MAX_N)
            throw FailException("Out of range N=" + to_string(n) + ". Please contact admin.");

        auto names = new char[n][5];
        auto numbers = new unsigned short[n];
        auto outputs = new bool[MAX_LA];

        for (int _ = 0; _ < T; _++) {
            memset(names, 0, n * 5);
            memset(numbers, 0, n * sizeof(unsigned short));
            memset(outputs, 0, MAX_LA);

            set<string> allNames;

            for (int i = 0; i < n; i++) {
                string name; unsigned short number;
                cin >> name >> number;
                // cerr << "Stub: alice read name=" << name << " number=" << number << endl;
                if (!isValidName(name))
                    throw FailException("Invalid name [" + name + "]. Please contact admin.");
                if (allNames.count(name))
                    throw FailException("Duplicate name [" + name + "]. Please contact admin.");
                allNames.insert(name);

                strcpy(names[i], name.c_str());
                numbers[i] = number;
            }

            auto start = clock();
            int la = alice(n, names, numbers, outputs);
            auto end = clock();

            if (la < 0 || la > MAX_LA)
                throw WAException("l_A (return value of alice()) out of range");

            double seconds = (end - start) / (double) CLOCKS_PER_SEC;
            if (seconds > TL_PER_ALICE)
                throw TLEException("alice() exceeds time limit");
            
            for (int i = 0; i < la; i++)
                fout << "01"[outputs[i]];
            fout << '\n';
        }
    });
}

static int bob() {
    cerr << "Stub: bob()" << endl;
    return grader_entry([&](stringstream& fout) {
        int m; cin >> m;
        cerr << "Stub: bob m=" << m << endl;
        if (m < 0 || m > MAX_M)
            throw FailException("Out of range M=" + to_string(m) + ". Please contact admin.");
        
        auto senders = new char[m][5];
        auto recipients = new char[m][5];
        auto outputs = new bool[MAX_LB];

        for (int _ = 0; _ < T; _++) {
            memset(senders, 0, m * 5);
            memset(recipients, 0, m * 5);
            memset(outputs, 0, MAX_LB);

            for (int i = 0; i < m; i++) {
                string sender, recipient;
                cin >> sender >> recipient;
                // cerr << "Stub: bob reads sender=" << sender << " recipient=" << recipient << endl;
                if (!isValidName(sender))
                    throw FailException("Invalid sender [" + sender + "]. Please contact admin.");
                if (!isValidName(recipient))
                    throw FailException("Invalid recipient [" + recipient + "]. Please contact admin.");

                strcpy(senders[i], sender.c_str());
                strcpy(recipients[i], recipient.c_str());
            }

            auto start = clock();
            int lb = bob(m, senders, recipients, outputs);
            auto end = clock();

            if (lb < 0 || lb > MAX_LB)
                throw WAException("l_B (return value of bob()) out of range");
            
            double seconds = (end - start) / (double) CLOCKS_PER_SEC;
            if (seconds > TL_PER_BOB)
                throw TLEException("bob() exceeds time limit");
            
            for (int i = 0; i < lb; i++)
                fout << "01"[outputs[i]];
            fout << '\n';
        }
    });
}

static int circuit() {
    cerr << "Stub: circuit()" << endl;
    return grader_entry([&](stringstream& fout) {
        int la, lb; cin >> la >> lb;
        cerr << "Stub: circuit la=" << la << " lb=" << lb << endl;
        if (la < 0 || la > MAX_LA)
            throw WAException("l_A (return value of alice()) out of range");
        if (lb < 0 || lb > MAX_LB)
            throw WAException("l_B (return value of bob()) out of range");
        
        auto operations = new int[MAX_L];
        auto operands = new int[MAX_L][2];
        auto outputs = new int[MAX_N][16];

        auto start = clock();
        int l = circuit(la, lb, operations, operands, outputs);
        auto end = clock();

        if (l < 0 || l > MAX_L)
            throw WAException("l (return value of circuit()) out of range");
        
        if (l < la + lb)
            throw WAException("Too small l (return value of circuit()), less than la + lb");
        
        double seconds = (end - start) / (double) CLOCKS_PER_SEC;
        if (seconds > TL_PER_CIRCUIT)
            throw TLEException("circuit() exceeds time limit");
        
        for (int i = la + lb; i < l; i++) {
            if (operations[i] < 0 || operations[i] > 15)
                throw WAException("circuit() returns invalid operation (<0 or >15)");
            if (operands[i][0] < 0 || operands[i][0] >= i)
                throw WAException("circuit() returns invalid operand (<0 or >=current label)");
            if (operands[i][1] < 0 || operands[i][1] >= i)
                throw WAException("circuit() returns invalid operand (<0 or >=current label)");
        }
        

        cout << CIRCUIT_WORKING_CORRECT_OUTPUT << flush;

        
        int n; cin >> n;
        if (n < 0 || n > MAX_N)
            throw FailException("Out of range N=" + to_string(n) + ". Please contact admin.");
        
        vector<vector<pair<string, unsigned short>>> alice_input;
        vector<set<string>> allNames(T);
        for (int _ = 0; _ < T; _++) {
            vector<pair<string, unsigned short>> input;
            set<string>& names = allNames[_];
            for (int i = 0; i < n; i++) {
                string name; unsigned short number;
                cin >> name >> number;
                if (!isValidName(name))
                    throw FailException("Invalid name [" + name + "]. Please contact admin.");
                if (names.count(name))
                    throw FailException("Duplicate name [" + name + "]. Please contact admin.");
                names.insert(name);
                input.emplace_back(name, number);
            }
            alice_input.push_back(input);
        }

        int m; cin >> m;
        if (m < 0 || m > MAX_M)
            throw FailException("Out of range M=" + to_string(m) + ". Please contact admin.");
        
        vector<vector<pair<string, string>>> bob_input;
        for (int _ = 0; _ < T; _++) {
            vector<pair<string, string>> input;
            set<string>& names = allNames[_];
            for (int i = 0; i < m; i++) {
                string sender, recipient;
                cin >> sender >> recipient;
                if (!names.count(sender))
                    throw FailException("Unknown sender [" + sender + "]. Please contact admin.");
                if (!names.count(recipient))
                    throw FailException("Unknown recipient [" + recipient + "]. Please contact admin.");
                input.emplace_back(sender, recipient);
            }
            bob_input.push_back(input);
        }

        readOkOrThrow();
        char c; cin.get(c);
        if (c != '\n')
            throw FailException("Expected newline. Please contact admin.");
        vector<string> alice_output;
        for (int _ = 0; _ < T; _++) {
            string s; getline(cin, s);
            // cerr << "Stub: circuit read alice_output=" << s << endl;
            if (s.size() > MAX_LA)
                throw WAException("l_A (return value of alice()) out of range");
            for (char c : s)
                if (c != '0' && c != '1')
                    throw FailException("Invalid Alice output. Please contact admin.");
            if (_ && s.size() != alice_output[0].size())
                throw WAException("l_A (return value of alice()) is not fixed when n is fixed");
            alice_output.push_back(s);
        }

        readOkOrThrow();
        cin.get(c);
        if (c != '\n')
            throw FailException("Expected newline. Please contact admin.");
        vector<string> bob_output;
        for (int _ = 0; _ < T; _++) {
            string s; getline(cin, s);
            // cerr << "Stub: circuit read bob_output=" << s << endl;
            if (s.size() > MAX_LB)
                throw WAException("l_B (return value of bob()) out of range");
            for (char c : s)
                if (c != '0' && c != '1')
                    throw FailException("Invalid Bob output. Please contact admin.");
            if (_ && s.size() != bob_output[0].size())
                throw WAException("l_B (return value of bob()) is not fixed when m is fixed");
            bob_output.push_back(s);
        }
        
        for (int i = la + lb; i < l; i++) {
            if (operations[i] < 0 || operations[i] > 15)
                throw WAException("circuit() returns invalid operation (<0 or >15)");
            if (operands[i][0] < 0 || operands[i][0] >= i)
                throw WAException("circuit() returns invalid operand (<0 or >=current label)");
            if (operands[i][1] < 0 || operands[i][1] >= i)
                throw WAException("circuit() returns invalid operand (<0 or >=current label)");
        }
        for (int i = 0; i < n; i++)
            for (int j = 0; j < 16; j++)
                if (outputs[i][j] < 0 || outputs[i][j] >= l)
                    throw WAException("circuit() returns invalid circuit_output (<0 or >=l)");

        auto values = new BS[l];
        for (int i = 0; i < la; i++) {
            BS bs = 0_bs;
            for (int j = 0; j < T; j++)
                bs |= (BS(alice_output[j][i] - '0') << j);
            values[i] = bs;
        }
        for (int i = 0; i < lb; i++) {
            BS bs = 0_bs;
            for (int j = 0; j < T; j++)
                bs |= (BS(bob_output[j][i] - '0') << j);
            values[la + i] = bs;
        }
        for (int i = la + lb; i < l; i++) {
            BS bs0 = values[operands[i][0]];
            BS bs1 = values[operands[i][1]];
            BS& bs = values[i];
            switch (operations[i]) {
                case OP_ZERO:
                    bs = 0_bs;
                    break;
                case OP_NOR:
                    bs = ~(bs0 | bs1);
                    break;
                case OP_GREATER:
                    bs = bs0 & ~bs1;
                    break;
                case OP_NOT_X1:
                    bs = ~bs1;
                    break;
                case OP_LESS:
                    bs = ~bs0 & bs1;
                    break;
                case OP_NOT_X0:
                    bs = ~bs0;
                    break;
                case OP_XOR:
                    bs = bs0 ^ bs1;
                    break;
                case OP_NAND:
                    bs = ~(bs0 & bs1);
                    break;
                case OP_AND:
                    bs = bs0 & bs1;
                    break;
                case OP_EQUAL:
                    bs = ~(bs0 ^ bs1);
                    break;
                case OP_X0:
                    bs = bs0;
                    break;
                case OP_GEQ:
                    bs = ~(~bs0 & bs1);
                    break;
                case OP_X1:
                    bs = bs1;
                    break;
                case OP_LEQ:
                    bs = ~(bs0 & ~bs1);
                    break;
                case OP_OR:
                    bs = bs0 | bs1;
                    break;
                case OP_ONE:
                    bs = (1_bs << T) - 1_bs;
                    break;
                default:
                    throw WAException("circuit() returns invalid operation (<0 or >15)");
            }
        }

        vector<vector<unsigned short>> circuit_output(T, vector<unsigned short>(n));
        for (int i = 0; i < n; i++)
            for (int j = 0; j < 16; j++)
                for (int k = 0; k < T; k++) {
                    circuit_output[k][i] |= (unsigned short) ((values[outputs[i][j]] >> k) & 1_bs) << j;
                }
        
        vector<vector<unsigned short>> reference_output;
        for (int _ = 0; _ < T; _++) {
            vector<unsigned short> output(n);
            auto& alice = alice_input[_];
            auto& bob = bob_input[_];
            map<string, unsigned short> values;
            map<string, unsigned short> answer;
            for (const auto& p : alice)
                values[p.first] = p.second;
            for (const auto& p : bob)
                answer[p.second] += values[p.first];
            for (int i = 0; i < n; i++)
                output[i] = answer[alice[i].first];
            reference_output.push_back(output);
        }

        auto vector_to_string = [&](const vector<unsigned short>& v) {
            string s;
            for (int i = 0; i < n; i++)
                s += to_string(v[i]) + " ";
            return s;
        };

        for (int _ = 0; _ < T; _++)
            if (circuit_output[_] != reference_output[_])
                throw WAException("Your functions alice(), bob(), circuit() finished successfully, but the final output binary string is incorrect.");
        
        fout << "Correct!\n";
    });
}

int main(int argc, char** argv) {
    if (argc != 2) {
        cerr << "Usage: " << argv[0] << " [0|1|2]" << endl;
        return 0;
    }
    string s; cin >> s;
    if (s != "Hello") {
        if(s == "Goodbye") cerr << "Fail in previous run, exit now" << endl;
        else cout << "FAIL\nDid not receive Hello from manager" << endl;
        return 0;
    }
    int mode = atoi(argv[1]);
    switch (mode) {
        case 0:
            return alice();
            break;
        case 1:
            return bob();
            break;
        case 2:
            return circuit();
            break;
        default:
            cerr << "Usage: " << argv[0] << " [0|1|2]" << endl;
            return 0;
    }
    cin >> s;
    if (s != "Goodbye") {
        cout << "FAIL\nDid not receive Goodbye from manager" << endl;
        return 0;
    }
    return 0;
}


Setup script:
#!/bin/bash
set -e # Exit immediately if a command fails

echo "--- Setup Script (Alice/Bob/Circuit Problem) ---"

# --- Fixed Files (Problem Specific) ---
STUB_CPP="stub.cpp"          # Stub for the problem
MANAGER_CPP="manager.cpp"    # Manager for the problem
HEADER="abc.h"               # Header for the problem

# --- Argument Parsing ---
# Expect exactly one argument: solution_file
if [ "$#" -ne 1 ]; then
    echo "Usage: $0 <path/to/solution.cpp>" >&2
    exit 1
fi
SOLUTION_CPP="$1" # Get solution file from first argument

# --- File Checks (Compilation Prerequisites) ---
check_file() { if [ ! -f "$1" ]; then echo "ERROR: File not found: $1" >&2; exit 1; fi }
check_tool() { if ! command -v "$1" &> /dev/null; then echo "ERROR: Command not found: $1" >&2; exit 1; fi }

echo "Checking required files and tools for compilation..."
check_file "$SOLUTION_CPP"
check_file "$STUB_CPP"
check_file "$MANAGER_CPP"
check_tool "g++"
check_tool "mkfifo" # Need mkfifo for evaluation, check here too.
echo "Checks passed."
echo "Setup for Solution: $SOLUTION_CPP"

# --- Handle abc.h ---
ABC_H_COMP="$HEADER" # Default to the provided header name
if [ ! -f "$HEADER" ]; then
    echo "Warning: $HEADER not found. Creating a placeholder for compilation."
    # Use a different name to avoid overwriting a user's file silently if they create it later
    ABC_H_COMP="${HEADER}.generated"
    cat <<EOF > "$ABC_H_COMP"
#ifndef ABC_H_GENERATED
#define ABC_H_GENERATED

// Placeholder declarations for compilation
extern "C" {
    int alice(int n, char names[][5], unsigned short numbers[], bool outputs[]);
    int bob(int m, char senders[][5], char recipients[][5], bool outputs[]);
    int circuit(int la, int lb, int operations[], int operands[][2], int outputs[][16]);
}

#endif // ABC_H_GENERATED
EOF
    echo "Placeholder header created: $ABC_H_COMP"
fi


# --- Dynamic Naming (Executables) ---
SOLUTION_BASENAME=$(basename "$SOLUTION_CPP" .cpp)
# Executable that contains the user's alice/bob/circuit functions linked with the stub
USER_CODE_EXE="./${SOLUTION_BASENAME}_user_code_exe"
# Fixed manager executable name
MANAGER_EXE="./abc_manager_exe"

# --- Compile User Code (Solution + Stub) ---
if [ ! -f "$USER_CODE_EXE" ]; then
    echo "Compiling user code ($SOLUTION_CPP + $STUB_CPP) into $USER_CODE_EXE ..."
    # Compile solution and stub together, linking with the header
    g++ -std=c++17 -O2 -Wall "$SOLUTION_CPP" "$STUB_CPP" "$ABC_H_COMP" -o "$USER_CODE_EXE"
    if [ $? -ne 0 ]; then
        echo "ERROR: User code compilation failed." >&2
        # Clean up generated header if compilation fails
        if [ "$ABC_H_COMP" != "$HEADER" ]; then rm -f "$ABC_H_COMP"; fi
        exit 1
    fi
    echo "User code compiled successfully."
else
    echo "Using existing user code executable: $USER_CODE_EXE"
fi

# --- Compile Manager ---
if [ ! -f "$MANAGER_EXE" ]; then
    echo "Compiling manager ($MANAGER_CPP) into $MANAGER_EXE ..."
    g++ -std=c++17 -O2 -Wall "$MANAGER_CPP" -o "$MANAGER_EXE"
    if [ $? -ne 0 ]; then
        echo "ERROR: Manager compilation failed." >&2
        # Optional: remove user code exe if manager fails?
        # rm -f "$USER_CODE_EXE"
        # Clean up generated header if compilation fails
        if [ "$ABC_H_COMP" != "$HEADER" ]; then rm -f "$ABC_H_COMP"; fi
        exit 1
    fi
    echo "Manager compiled successfully."
else
    echo "Using existing manager executable: $MANAGER_EXE"
fi

# Clean up generated header if it was created and compilation was successful
if [ "$ABC_H_COMP" != "$HEADER" ] && [ -f "$USER_CODE_EXE" ] && [ -f "$MANAGER_EXE" ]; then
    echo "Removing temporary generated header: $ABC_H_COMP"
    rm -f "$ABC_H_COMP"
fi


echo "Setup complete. Executables ready:"
echo "  Manager: $MANAGER_EXE"
echo "  User Code (Alice/Bob/Circuit): $USER_CODE_EXE"

exit 0


Evaluation script:
#!/bin/bash
set -e # Exit immediately if a command fails

echo "--- Evaluation Script (Alice/Bob/Circuit Problem) ---"

# --- Argument Parsing ---
# Expect exactly two arguments: solution_file and input_file
if [ "$#" -ne 2 ]; then
    echo "Usage: $0 <path/to/solution.cpp> <path/to/input.txt>" >&2
    echo "Note: Run setup.sh <path/to/solution.cpp> first to compile." >&2
    exit 1
fi
SOLUTION_CPP="$1" # Get solution file from first argument
INPUT_TXT="$2"    # Get input file from second argument

# --- File & Tool Checks ---
check_file() { if [ ! -f "$1" ]; then echo "ERROR: File not found: $1" >&2; exit 1; fi }
check_tool() { if ! command -v "$1" &> /dev/null; then echo "ERROR: Command not found: $1" >&2; exit 1; fi; } # Exit on missing tool

echo "Checking required files and tools for evaluation..."
check_file "$INPUT_TXT"
check_tool "/usr/bin/time" # Check for the time command specifically
check_tool "mkfifo"
echo "Checks passed."
echo "Using Solution: $SOLUTION_CPP"
echo "Using Input:    $INPUT_TXT"

# --- Dynamic Naming (Consistent with setup.sh) ---
SOLUTION_BASENAME=$(basename "$SOLUTION_CPP" .cpp)
INPUT_BASENAME=$(basename "$INPUT_TXT" .in) # Assuming .txt extension for inputs
# Executable names derived from solution basename (must match setup.sh)
USER_CODE_EXE="./${SOLUTION_BASENAME}_user_code_exe"
# Fixed manager executable name (must match setup.sh)
MANAGER_EXE="./abc_manager_exe"

# Log files for capturing output
MANAGER_STDOUT_LOG="${INPUT_BASENAME}_${SOLUTION_BASENAME}_manager_stdout.log"
MANAGER_STDERR_LOG="${INPUT_BASENAME}_${SOLUTION_BASENAME}_manager_stderr.log"
ALICE_LOG="${INPUT_BASENAME}_${SOLUTION_BASENAME}_alice.log"
BOB_LOG="${INPUT_BASENAME}_${SOLUTION_BASENAME}_bob.log"
CIRCUIT_LOG="${INPUT_BASENAME}_${SOLUTION_BASENAME}_circuit.log"

# Results file for the final score
RESULTS_TXT="${INPUT_BASENAME}_${SOLUTION_BASENAME}.results.txt"

# FIFO names (Named Pipes) - Must match the order expected by Manager.cpp
# Arg1: AliceToManager (Alice writes, Manager reads)
# Arg2: ManagerToAlice (Manager writes, Alice reads)
# Arg3: BobToManager   (Bob writes, Manager reads)
# Arg4: ManagerToBob   (Manager writes, Bob reads)
# Arg5: CircuitToManager (Circuit writes, Manager reads)
# Arg6: ManagerToCircuit (Manager writes, Circuit reads)
ALICE_TO_MANAGER="alice_out_fifo_${SOLUTION_BASENAME}_${INPUT_BASENAME}" # Make FIFO names unique per run
MANAGER_TO_ALICE="alice_in_fifo_${SOLUTION_BASENAME}_${INPUT_BASENAME}"
BOB_TO_MANAGER="bob_out_fifo_${SOLUTION_BASENAME}_${INPUT_BASENAME}"
MANAGER_TO_BOB="bob_in_fifo_${SOLUTION_BASENAME}_${INPUT_BASENAME}"
CIRCUIT_TO_MANAGER="circuit_out_fifo_${SOLUTION_BASENAME}_${INPUT_BASENAME}"
MANAGER_TO_CIRCUIT="circuit_in_fifo_${SOLUTION_BASENAME}_${INPUT_BASENAME}"

# Check if executables exist (created by setup.sh)
echo "Checking for compiled executables..."
check_file "$USER_CODE_EXE"
check_file "$MANAGER_EXE"
echo "Executables found."

# Initialize exit codes
MANAGER_EXIT_CODE=-1
ALICE_EXIT_CODE=-1
BOB_EXIT_CODE=-1
CIRCUIT_EXIT_CODE=-1

# --- Cleanup Function ---
# This function will be called on script exit (normal or error)
cleanup() {
    local script_exit_code=$?
    echo "Cleaning up evaluation run (Exit Code: $script_exit_code)..."
    # Kill any background processes started by this script
    # Use 2>/dev/null to suppress "No such process" errors if processes already exited
    # Note: This might not always catch processes if they've already exited or are stuck.
    # A more robust approach might involve tracking PIDs and explicitly killing them.
    # For this setup, killing jobs started in the background is usually sufficient.
    kill $(jobs -p) 2>/dev/null

    # Remove FIFOs
    rm -f "$ALICE_TO_MANAGER" "$MANAGER_TO_ALICE" \
          "$BOB_TO_MANAGER" "$MANAGER_TO_BOB" \
          "$CIRCUIT_TO_MANAGER" "$MANAGER_TO_CIRCUIT"

    # Log files and results file are kept for inspection

    echo "Cleanup finished."
    # Exit with the original exit code that triggered the trap
    exit $script_exit_code
}
# Register the cleanup function to run on EXIT, INT, TERM signals
trap cleanup EXIT INT TERM

# --- Create FIFOs ---
echo "Creating FIFOs..."
mkfifo "$ALICE_TO_MANAGER"
mkfifo "$MANAGER_TO_ALICE"
mkfifo "$BOB_TO_MANAGER"
mkfifo "$MANAGER_TO_BOB"
mkfifo "$CIRCUIT_TO_MANAGER"
mkfifo "$MANAGER_TO_CIRCUIT"
echo "FIFOs created."

# --- Run User Code Processes (Alice, Bob, Circuit) in Background ---
echo "Running user code processes (Alice, Bob, Circuit) in background..."

# Alice: runs with argument 0, reads from MANAGER_TO_ALICE, writes to ALICE_TO_MANAGER
"$USER_CODE_EXE" 0 < "$MANAGER_TO_ALICE" > "$ALICE_TO_MANAGER" 2> "$ALICE_LOG" &
ALICE_PID=$!
echo "  Alice (PID $ALICE_PID) started. Logging stderr to $ALICE_LOG."

# Bob: runs with argument 1, reads from MANAGER_TO_BOB, writes to BOB_TO_MANAGER
"$USER_CODE_EXE" 1 < "$MANAGER_TO_BOB" > "$BOB_TO_MANAGER" 2> "$BOB_LOG" &
BOB_PID=$!
echo "  Bob (PID $BOB_PID) started. Logging stderr to $BOB_LOG."

# Circuit: runs with argument 2, reads from MANAGER_TO_CIRCUIT, writes to CIRCUIT_TO_MANAGER
"$USER_CODE_EXE" 2 < "$MANAGER_TO_CIRCUIT" > "$CIRCUIT_TO_MANAGER" 2> "$CIRCUIT_LOG" &
CIRCUIT_PID=$!
echo "  Circuit (PID $CIRCUIT_PID) started. Logging stderr to $CIRCUIT_LOG."

# Give background processes a moment to start and open FIFOs
sleep 0.1

# --- Run Manager ---
echo "Running Manager with input $INPUT_TXT (measuring resources)..."
# Manager reads test case from stdin.
# Manager takes FIFO paths as command-line arguments in the specific order.
# Use /usr/bin/time to measure the manager process
# Use '|| true' temporarily to prevent set -e exit if manager fails, so we can capture its exit code
/usr/bin/time -f "Manager CPU Time (User+Sys): %U + %S seconds\nManager Max Memory: %M KB" \
              -o "${INPUT_BASENAME}_${SOLUTION_BASENAME}.time.txt" \
              "$MANAGER_EXE" \
              "$ALICE_TO_MANAGER" "$MANAGER_TO_ALICE" \
              "$BOB_TO_MANAGER" "$MANAGER_TO_BOB" \
              "$CIRCUIT_TO_MANAGER" "$MANAGER_TO_CIRCUIT" \
              < "$INPUT_TXT" > "$MANAGER_STDOUT_LOG" 2> "$MANAGER_STDERR_LOG" || true

MANAGER_EXIT_CODE=$? # Capture manager's exit code
echo "Manager finished with exit code $MANAGER_EXIT_CODE."

# Wait for background processes to finish. They should exit when the manager closes pipes.
# Use 2>/dev/null in case a process already finished.
wait $ALICE_PID 2>/dev/null || true
ALICE_EXIT_CODE=$?
wait $BOB_PID 2>/dev/null || true
BOB_EXIT_CODE=$?
wait $CIRCUIT_PID 2>/dev/null || true
CIRCUIT_EXIT_CODE=$?

echo "Background processes finished."

# --- Extract Score and Write to Results File ---
echo "Extracting score from $MANAGER_STDOUT_LOG and writing to $RESULTS_TXT..."
if [ -r "$MANAGER_STDOUT_LOG" ]; then
    # Extract the first line (the score) and write it to the results file
    head -n 1 "$MANAGER_STDOUT_LOG" > "$RESULTS_TXT"
    echo "Score extracted and written to $RESULTS_TXT."
else
    echo "WARNING: Manager STDOUT log '$MANAGER_STDOUT_LOG' not found or not readable. Cannot extract score." >&2
    echo "N/A" > "$RESULTS_TXT" # Write N/A to results file if log is missing
fi


# --- Report Results ---
echo ""
echo "--- Evaluation Results ---"

# Read the score from the results file
if [ -r "$RESULTS_TXT" ]; then
    SCORE=$(cat "$RESULTS_TXT")
    echo "Final Score (from $RESULTS_TXT): ${SCORE:-N/A (Results file empty)}" # Print N/A if score is empty
else
    echo "ERROR: Results file '$RESULTS_TXT' not found or not readable." >&2
    SCORE="ERROR" # Indicate error
fi

# Read the full message from the stderr log
if [ -r "$MANAGER_STDERR_LOG" ]; then
    MESSAGE=$(cat "$MANAGER_STDERR_LOG")
    echo "Full Message (from $MANAGER_STDERR_LOG):"
    echo "$MESSAGE"
else
    echo "ERROR: Manager STDERR log '$MANAGER_STDERR_LOG' not found or not readable." >&2
    MESSAGE="ERROR" # Indicate error
fi

echo "--- End Results ---"

# --- Show Resource Usage ---
echo ""
echo "--- Resource Usage (Manager Process) ---"
TIME_OUTPUT_FILE="${INPUT_BASENAME}_${SOLUTION_BASENAME}.time.txt" # Redefine for clarity
if [ -r "$TIME_OUTPUT_FILE" ]; then
    cat "$TIME_OUTPUT_FILE"
else
     if [ $MANAGER_EXIT_CODE -ne 0 ]; then
         echo "Manager process did not complete normally; resource usage may be incomplete or unavailable." >&2
     else
         echo "ERROR: Time output file '$TIME_OUTPUT_FILE' not found or not readable." >&2
     fi
fi
echo "-----------------------------------------"

# --- Show Process Exit Codes ---
echo ""
echo "--- Process Exit Codes ---"
echo "Manager Exit Code:           $MANAGER_EXIT_CODE"
echo "Alice Process Exit Code:     $ALICE_EXIT_CODE"
echo "Bob Process Exit Code:       $BOB_EXIT_CODE"
echo "Circuit Process Exit Code:   $CIRCUIT_EXIT_CODE"
# Add warnings for non-zero exit codes
if [ $MANAGER_EXIT_CODE -ne 0 ]; then
    echo "Warning: Manager process exited with non-zero status ($MANAGER_EXIT_CODE)" >&2
fi
if [ $ALICE_EXIT_CODE -ne 0 ]; then
    echo "Warning: Alice process exited with non-zero status ($ALICE_EXIT_CODE). Check $ALICE_LOG" >&2
fi
if [ $BOB_EXIT_CODE -ne 0 ]; then
    echo "Warning: Bob process exited with non-zero status ($BOB_EXIT_CODE). Check $BOB_LOG" >&2
fi
if [ $CIRCUIT_EXIT_CODE -ne 0 ]; then
    echo "Warning: Circuit process exited with non-zero status ($CIRCUIT_EXIT_CODE). Check $CIRCUIT_LOG" >&2
fi
echo "--------------------------"

echo "--- Evaluation Complete ---"

# Exit the script with the manager's exit code as the primary indicator of success/failure
# The 'trap cleanup EXIT' will run before the script finally terminates
exit $MANAGER_EXIT_CODE