longesttrip (IOI contest)
Time limit: 1 seconds | Memory limit: 2048 MB | Task type: interactive
Algorithms: ad-hoc, graph theory, binary search

# Longest Trip

The IOI 2023 organizers are in big trouble! They forgot to plan the trip to Ópusztaszer for the upcoming day. 
But maybe it is not yet too late ...

There are $N$ landmarks at Ópusztaszer indexed from $0$ to $N-1$. 
Some pairs of these landmarks are connected by *bidirectional* **roads**.
Each pair of landmarks is connected by at most one road.
The organizers *don't know* which landmarks are connected by roads.

We say that the **density** of the road network at Ópusztaszer is **at least** $\delta$ if every $3$ distinct landmarks have at least $\delta$ roads among them.
In other words, for each triplet of landmarks $(u, v, w)$ such that $0 \le u \lt v \lt w \lt N$, among the pairs of landmarks $(u,v), (v,w)$ and $(u,w)$ at least $\delta$ pairs are connected by a road.

The organizers *know* a positive integer $D$ such that the density of the road network is at least $D$.
Note that the value of $D$ cannot be greater than $3$.

The organizers can make **calls** to the phone dispatcher at Ópusztaszer to gather information about the road connections between certain landmarks.
In each call, two nonempty arrays of landmarks $[A[0], \ldots, A[P-1]]$ and $[B[0], \ldots, B[R-1]]$ must be specified.
The landmarks must be pairwise distinct, that is,
* $A[i] \neq A[j]$ for each $i$ and $j$ such that $0 \le i \lt j \lt P$;
* $B[i] \neq B[j]$ for each $i$ and $j$ such that $0 \le i \lt j \lt R$;
* $A[i] \neq B[j]$ for each $i$ and $j$ such that $0 \le i \lt P$ and $0\le j \lt R$.

For each call, the dispatcher reports whether there is a road connecting a landmark from $A$ and a landmark from $B$.
More precisely, the dispatcher iterates over all pairs $i$ and $j$ such that $0 \le i \lt P$ and $0\le j \lt R$.
If, for any of them, the landmarks $A[i]$ and $B[j]$ are connected by a road, the dispatcher returns `true`.
Otherwise, the dispatcher returns `false`.

A **trip** of length $l$ is a sequence of *distinct* landmarks $t[0], t[1], \ldots, t[l-1]$, 
where for each $i$ between $0$ and $l-2$, inclusive, landmark $t[i]$ and landmark $t[i+1]$ are connected by a road.
A trip of length $l$ is called a **longest trip** if there does not exist any trip of length at least $l+1$.

Your task is to help the organizers to find a longest trip at Ópusztaszer by making calls to the dispatcher.

## Implementation Details

You should implement the following procedure:

```
int[] longest_trip(int N, int D)
```

* $N$: the number of landmarks at Ópusztaszer.
* $D$: the guaranteed minimum density of the road network.
* This procedure should return an array $t = [t[0], t[1], \ldots, t[l-1]]$, representing a longest trip.
* This procedure may be called **multiple times** in each test case.

The above procedure can make calls to the following procedure:

```
bool are_connected(int[] A, int[] B)
```

* $A$: a nonempty array of distinct landmarks.
* $B$: a nonempty array of distinct landmarks.
* $A$ and $B$ should be disjoint.
* This procedure returns `true` if there is a landmark from $A$ and a landmark from $B$ connected by a road. Otherwise, it returns `false`.
* This procedure can be called at most $32\,640$ times in each invocation of `longest_trip`, and at most $150\,000$ times in total.
* The total length of arrays $A$ and $B$ passed to this procedure over all of its invocations cannot exceed $1\,500\,000$.

The grader is **not adaptive**. Each submission is graded on the same set of test cases. That is, the values of $N$ and $D$, as well as the pairs of landmarks connected by roads, are fixed for each call of `longest_trip` within each test case.

## Examples

### Example 1

Consider a scenario in which $N = 5$, $D = 1$, and the road connections are as shown in the following figure:

![Example1](longesttrip-ex1.png "200")

The procedure `longest_trip` is called in the following way:
```
longest_trip(5, 1)
```

The procedure may make calls to `are_connected` as follows.

Call                               | Pairs connected by a road |  Return value
:---------------------------------:|:-------------------------:|:--------------:
`are_connected([0], [1, 2, 4, 3])` | $(0,1)$ and $(0,2)$       | `true`
`are_connected([2], [0])`          | $(2,0)$                   | `true`
`are_connected([2], [3])`          | $(2,3)$                   | `true`
`are_connected([1, 0], [4, 3])`    | none                      | `false`

After the fourth call, it turns out that *none* of the pairs $(1,4)$, $(0,4)$, $(1,3)$ and $(0,3)$ is connected by a road.
As the density of the network is at least $D = 1$, we see that from the triplet $(0, 3, 4)$, the pair $(3,4)$ must be connected by a road.
Similarly to this, landmarks $0$ and $1$ must be connected.

At this point, it can be concluded that $t = [1, 0, 2, 3, 4]$ is a trip of length $5$, and that there does not exist a trip of length greater than $5$.
Therefore, the procedure `longest_trip` may return $[1, 0, 2, 3, 4]$.

Consider another scenario in which $N = 4$, $D = 1$, and the roads between the landmarks are as shown in the following figure:

![Example2](longesttrip-ex2.png "200")

The procedure `longest_trip` is called in the following way:
```
longest_trip(4, 1)
```

In this scenario, the length of a longest trip is $2$. Therefore, after a few calls to procedure `are_connected`, the procedure `longest_trip` may return one of $[0, 1]$, $[1, 0]$, $[2, 3]$ or $[3, 2]$.

### Example 2

Subtask 0 contains an additional example test case with $N=256$ landmarks.
This test case is included in the attachment package that you can download from the contest system.

## Constraints

* $3 \le N \le 256$
* The sum of $N$ over all calls to `longest_trip` does not exceed $1\,024$ in each test case.
* $1 \le D \le 3$


## Subtasks

1. (5 points) $D = 3$
1. (10 points) $D = 2$
1. (25 points) $D = 1$. Let $l^\star$ denote the length of a longest trip. Procedure `longest_trip` does not have to return a trip of length $l^\star$. Instead, it should return a trip of length at least $\left\lceil \frac{l^\star}{2} \right\rceil$.
1. (60 points) $D = 1$

In subtask 4 your score is determined based on the number of calls to procedure `are_connected` over a single invocation of `longest_trip`.
Let $q$ be the maximum number of calls among all invocations of `longest_trip` over every test case of the subtask.
Your score for this subtask is calculated according to the following table:

Condition                  |  Points
:-------------------------:|:----------------------:
$2\,750 \lt q \le 32\,640$ |  $20$
$550 \lt q \le 2\,750$     |  $30$
$400 \lt q \le 550$        |  $45$
$q \le 400$                |  $60$

If, in any of the test cases, the calls to the procedure `are_connected` do not conform to the constraints described in Implementation Details, or the array returned by `longest_trip` is incorrect, the score of your solution for that subtask will be $0$.

## Sample Grader

Let $C$ denote the number of scenarios, that is, the number of calls to `longest_trip`.
The sample grader reads the input in the following format:

* line $1$: $C$

The descriptions of $C$ scenarios follow.

The sample grader reads the description of each scenario in the following format:

* line $1$: $N \; D$
* line $1 + i$ ($1 \le i \lt N$): $U_i[0] \; U_i[1] \; \ldots \; U_i[i-1]$

Here, each $U_i$ ($1 \le i \lt N$) is an array of size $i$, describing which pairs of landmarks are connected by a road.
For each $i$ and $j$ such that $1 \le i \lt N$ and $0 \le j \lt i$:
* if landmarks $j$ and $i$ are connected by a road, then the value of $U_i[j]$ should be $1$;
* if there is no road connecting landmarks $j$ and $i$, then the value of $U_i[j]$ should be $0$.

<!-- IMPORTANT NOTE TO TRANSLATORS: THE FOLLOWING MESSAGES (IN BACKTICKS) SHOULD NOT BE TRANSLATED -->

In each scenario, before calling `longest_trip`, the sample grader checks whether the density of the road network is at least $D$.
If this condition is not met, it prints the message `Insufficient Density` and terminates.

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

* `invalid array`: in a call to `are_connected`, at least one of arrays $A$ and $B$
    - is empty, or
    - contains an element that is not an integer between $0$ and $N-1$, inclusive, or
    - contains the same element at least twice.
* `non-disjoint arrays`: in a call to `are_connected`, arrays $A$ and $B$ are not disjoint.
* `too many calls`: the number of calls made to `are_connected` exceeds $32\,640$ over the current invocation of `longest trip`, or exceeds $150\,000$ in total.
* `too many elements`: the total number of landmarks passed to `are_connected` over all calls exceeds $1\,500\,000$.


Otherwise, let the elements of the array returned by `longest_trip` in a scenario be $t[0], t[1], \ldots, t[l - 1]$ for some nonnegative $l$.
The sample grader prints three lines for this scenario in the following format:

* line $1$: $l$
* line $2$: $t[0] \; t[1] \; \ldots \; t[l-1]$
* line $3$: the number of calls to `are_connected` over this scenario

Finally, the sample grader prints:

* line $1 + 3 \cdot C$: the maximum number of calls to `are_connected` over all calls to `longest_trip`


Starter code:
longesttrip.cpp: #include "longesttrip.h"

std::vector<int> longest_trip(int N, int D)
{
    return {};
}

grader.cpp: #include "longesttrip.h"

#include <cassert>
#include <cstdio>
#include <string>
#include <vector>

static inline constexpr int maxNumberOfCalls = 32640;
static inline constexpr int maxTotalNumberOfCalls = 150000;
static inline constexpr int maxTotalNumberOfLandmarksInCalls = 1500000;
static int call_counter = 0;
static int total_call_counter = 0;
static int landmark_counter = 0;

static int C, N, D;
static std::vector<std::vector<int>> U;
static std::vector<bool> present;

static inline void protocol_violation(std::string message)
{
    printf("Protocol Violation: %s\n", message.c_str());
    exit(0);
}

bool are_connected(std::vector<int> A, std::vector<int> B)
{
    ++call_counter;
    ++total_call_counter;
    if (call_counter > maxNumberOfCalls || total_call_counter > maxTotalNumberOfCalls)
    {
        protocol_violation("too many calls");
    }

    int nA = A.size(), nB = B.size();
    landmark_counter += nA + nB;
    if (landmark_counter > maxTotalNumberOfLandmarksInCalls)
    {
        protocol_violation("too many elements");
    }

    if (nA == 0 || nB == 0)
    {
        protocol_violation("invalid array");
    }
    for (int i = 0; i < nA; ++i)
    {
        if (A[i] < 0 || N <= A[i])
        {
            protocol_violation("invalid array");
        }
        if (present[A[i]])
        {
            protocol_violation("invalid array");
        }
        present[A[i]] = true;
    }
    for (int i = 0; i < nA; ++i)
    {
        present[A[i]] = false;
    }
    for (int i = 0; i < nB; ++i)
    {
        if (B[i] < 0 || N <= B[i])
        {
            protocol_violation("invalid array");
        }
        if (present[B[i]])
        {
            protocol_violation("invalid array");
        }
        present[B[i]] = true;
    }
    for (int i = 0; i < nB; ++i)
    {
        present[B[i]] = false;
    }

    for (int i = 0; i < nA; ++i)
    {
        for (int j = 0; j < nB; ++j)
        {
            if (A[i] == B[j])
            {
                protocol_violation("non-disjoint arrays");
            }
        }
    }

    for (int i = 0; i < nA; ++i)
    {
        for (int j = 0; j < nB; ++j)
        {
            if (U[std::max(A[i], B[j])][std::min(A[i], B[j])] == 1)
            {
                return true;
            }
        }
    }

    return false;
}

int main()
{
    assert(1 == scanf("%d", &C));
    int maximumCalls = 0;
    for (int c = 0; c < C; ++c)
    {
        call_counter = 0;
        assert(2 == scanf("%d %d", &N, &D));

        present.assign(N, false);
        U.resize(N);
        for (int i = 1; i < N; ++i)
        {
            U[i].resize(i);
            for (int j = 0; j < i; ++j)
            {
                assert(1 == scanf("%d", &U[i][j]));
            }
        }

        for (int i = 2; i < N; ++i)
        {
            for (int j = 1; j < i; ++j)
            {
                for (int k = 0; k < j; ++k)
                {
                    if (U[i][j] + U[i][k] + U[j][k] < D)
                    {
                        printf("Insufficient Density\n");
                        exit(0);
                    }
                }
            }
        }

        std::vector<int> t = longest_trip(N, D);
        int l = t.size();
        printf("%d\n", l);
        for (int i = 0; i < l; ++i)
        {
            printf(i == 0 ? "%d" : " %d", t[i]);
        }
        printf("\n");
        printf("%d\n", call_counter);

        maximumCalls = std::max(maximumCalls, call_counter);
        call_counter = 0;
    }
    printf("%d\n", maximumCalls);

    return 0;
}

longesttrip.h: #include <vector>

std::vector<int> longest_trip(int N, int D);

bool are_connected(std::vector<int> A, std::vector<int> B);


Grader code:
grader.cpp: #include "longesttrip.h"

#include <cassert>
#include <cstdio>
#include <string>
#include <vector>

static inline constexpr int maxNumberOfCalls = 32640;
static inline constexpr int maxTotalNumberOfCalls = 150000;
static inline constexpr int maxTotalNumberOfLandmarksInCalls = 1500000;
static int call_counter = 0;
static int total_call_counter = 0;
static int landmark_counter = 0;

static int C, N, D;
static std::vector<std::vector<int>> U;
static std::vector<bool> present;

static inline void protocol_violation(std::string message)
{
    printf("Protocol Violation: %s\n", message.c_str());
    exit(0);
}

bool are_connected(std::vector<int> A, std::vector<int> B)
{
    ++call_counter;
    ++total_call_counter;
    if (call_counter > maxNumberOfCalls || total_call_counter > maxTotalNumberOfCalls)
    {
        protocol_violation("too many calls");
    }

    int nA = A.size(), nB = B.size();
    landmark_counter += nA + nB;
    if (landmark_counter > maxTotalNumberOfLandmarksInCalls)
    {
        protocol_violation("too many elements");
    }

    if (nA == 0 || nB == 0)
    {
        protocol_violation("invalid array");
    }
    for (int i = 0; i < nA; ++i)
    {
        if (A[i] < 0 || N <= A[i])
        {
            protocol_violation("invalid array");
        }
        if (present[A[i]])
        {
            protocol_violation("invalid array");
        }
        present[A[i]] = true;
    }
    for (int i = 0; i < nA; ++i)
    {
        present[A[i]] = false;
    }
    for (int i = 0; i < nB; ++i)
    {
        if (B[i] < 0 || N <= B[i])
        {
            protocol_violation("invalid array");
        }
        if (present[B[i]])
        {
            protocol_violation("invalid array");
        }
        present[B[i]] = true;
    }
    for (int i = 0; i < nB; ++i)
    {
        present[B[i]] = false;
    }

    for (int i = 0; i < nA; ++i)
    {
        for (int j = 0; j < nB; ++j)
        {
            if (A[i] == B[j])
            {
                protocol_violation("non-disjoint arrays");
            }
        }
    }

    for (int i = 0; i < nA; ++i)
    {
        for (int j = 0; j < nB; ++j)
        {
            if (U[std::max(A[i], B[j])][std::min(A[i], B[j])] == 1)
            {
                return true;
            }
        }
    }

    return false;
}

int main()
{
    assert(1 == scanf("%d", &C));
    int maximumCalls = 0;
    for (int c = 0; c < C; ++c)
    {
        call_counter = 0;
        assert(2 == scanf("%d %d", &N, &D));

        present.assign(N, false);
        U.resize(N);
        for (int i = 1; i < N; ++i)
        {
            U[i].resize(i);
            for (int j = 0; j < i; ++j)
            {
                assert(1 == scanf("%d", &U[i][j]));
            }
        }

        for (int i = 2; i < N; ++i)
        {
            for (int j = 1; j < i; ++j)
            {
                for (int k = 0; k < j; ++k)
                {
                    if (U[i][j] + U[i][k] + U[j][k] < D)
                    {
                        printf("Insufficient Density\n");
                        exit(0);
                    }
                }
            }
        }

        std::vector<int> t = longest_trip(N, D);
        int l = t.size();
        printf("%d\n", l);
        for (int i = 0; i < l; ++i)
        {
            printf(i == 0 ? "%d" : " %d", t[i]);
        }
        printf("\n");
        printf("%d\n", call_counter);

        maximumCalls = std::max(maximumCalls, call_counter);
        call_counter = 0;
    }
    printf("%d\n", maximumCalls);

    return 0;
}

longesttrip.h: #include <vector>

std::vector<int> longest_trip(int N, int D);

bool are_connected(std::vector<int> A, std::vector<int> B);

manager.cpp: #include "testlib.h"

#include <cassert>
#include <csignal>
#include <cstdio>

#include <algorithm>
#include <memory>
#include <string>
#include <vector>
#include <queue>
#include <deque>

inline FILE *openFile(const char *name, const char *mode)
{
    FILE *file = fopen(name, mode);
    if (!file)
    {
        quitf(_fail, "Could not open file '%s' with mode '%s'", name, mode);
    }
    return file;
}

static inline constexpr int maxNumberOfCalls = 32640;
static inline constexpr int maxTotalNumberOfCalls = 150000;
static inline constexpr int maxTotalNumberOfLandmarksInCalls = 1500000;
static int call_counter = 0;
static int total_call_counter = 0;
static int landmark_counter = 0;

int calculateLMax(int N, const std::vector<std::vector<int>> &U)
{
    std::deque<int> line1;
    line1.clear();
    std::deque<int> line2;
    line2.clear();

    line1.push_back(0);

    for (int i = 1; i < N; i++)
    {
        if (U[i][line1.back()] == 1)
        {
            line1.push_back(i);
        }
        else if (!line2.empty() && U[i][line2.back()])
        {
            line2.push_back(i);
        }
        else
        {
            while (!line2.empty())
            {
                line1.push_back(line2.back());
                line2.pop_back();
            }
            line2.push_back(i);
        }
    }

    if (line1.size() < line2.size())
        swap(line1, line2);

    for (int i : line1)
    {
        for (int j : line2)
        {
            if (U[std::max(i, j)][std::min(i, j)] == 1)
                return N;
        }
    }
    return line1.size();
}

int main(int argc, char *argv[])
{
    testlibMode = _checker;
    ouf.mode = _output;

    if (argc < 3)
    {
        quit(_fail, "Insufficient number of args for manager of 'longesttrip'");
    }

    { // Keep alive on broken pipes
        struct sigaction sa;
        sa.sa_handler = SIG_IGN;
        sigaction(SIGPIPE, &sa, NULL);
    }

    FILE *fout = openFile(argv[2], "a");
    FILE *fin = openFile(argv[1], "r");

    char subtask[10];
    int C;
    assert(2 == scanf("%s %d", subtask, &C));

    fprintf(fout, "%d\n", C);
    fflush(fout);

    int maximumCalls = 0;
    for (int c = 0; c < C; ++c)
    {
        int N, D;
        assert(2 == scanf("%d %d", &N, &D));

        std::vector<bool> present(N, false);
        std::vector<std::vector<int>> U(N);
        for (int i = 1; i < N; ++i)
        {
            U[i].resize(i);
            for (int j = 0; j < i; ++j)
            {
                assert(1 == scanf("%d", &U[i][j]));
            }
        }

        int lMax = calculateLMax(N, U);

        fprintf(fout, "%d %d\n", N, D);
        fflush(fout);

        while (true)
        {
            {
                std::string input_secret = "3kC2Ia2048BfyJVGojMUKKtilctlZKcB";
                char secret[1000];
                if (fscanf(fin, "%s", secret) != 1)
                {
                    quit(_pv, "Could not read secret (possibly, an unexpected termination"
                              " of the program).");
                }
                if (std::string(secret) != input_secret)
                {
                    quit(_pv, "Secret mismatch (possible tampering with the output).");
                }
            }

            int op;
            if (fscanf(fin, "%d", &op) != 1)
            {
                quit(_fail, "Could not read op.");
            }

            if (op == 0)
            {
                ++call_counter, ++total_call_counter;
                if (call_counter > maxNumberOfCalls || total_call_counter > maxTotalNumberOfCalls)
                {
                    quit(_pv, "too many calls");
                }

                int nA, nB;
                if (fscanf(fin, "%d %d", &nA, &nB) != 2)
                {
                    quit(_fail, "Could not read arrays.");
                }

                landmark_counter += nA + nB;
                if (landmark_counter > maxTotalNumberOfLandmarksInCalls)
                {
                    quit(_pv, "too many elements");
                }

                if (nA <= 0 || nB <= 0 || nA + nB > N)
                {
                    quit(_pv, "invalid array");
                }

                std::vector<int> A(nA);
                for (int i = 0; i < nA; ++i)
                {
                    if (fscanf(fin, "%d", &A[i]) != 1)
                    {
                        quit(_fail, "Could not read array A.");
                    }
                    if (A[i] < 0 || N <= A[i])
                    {
                        quit(_pv, "invalid array");
                    }
                    if (present[A[i]])
                    {
                        quit(_pv, "invalid array");
                    }
                    present[A[i]] = true;
                }
                for (int i = 0; i < nA; ++i)
                {
                    present[A[i]] = false;
                }
                std::vector<int> B(nB);
                for (int i = 0; i < nB; ++i)
                {
                    if (fscanf(fin, "%d", &B[i]) != 1)
                    {
                        quit(_fail, "Could not read array B.");
                    }
                    if (B[i] < 0 || N <= B[i])
                    {
                        quit(_pv, "invalid array");
                    }
                    if (present[B[i]])
                    {
                        quit(_pv, "invalid array");
                    }
                    present[B[i]] = true;
                }
                for (int i = 0; i < nB; ++i)
                {
                    present[B[i]] = false;
                }

                for (int i = 0; i < nA; ++i)
                {
                    for (int j = 0; j < nB; ++j)
                    {
                        if (A[i] == B[j])
                        {
                            quit(_pv, "non-disjoint arrays");
                        }
                    }
                }

                bool connected = false;
                for (int i = 0; i < nA && !connected; ++i)
                {
                    for (int j = 0; j < nB && !connected; ++j)
                    {
                        if (U[std::max(A[i], B[j])][std::min(A[i], B[j])] == 1)
                        {
                            connected = true;
                        }
                    }
                }

                fprintf(fout, "%d\n", connected);
                fflush(fout);
            }
            else if (op == 1)
            {
                int l;
                if (fscanf(fin, "%d", &l) != 1)
                {
                    quit(_fail, "Could not read answer.");
                }

                if (l < 0 || N < l)
                {
                    quit(_wa);
                }

                std::vector<int> answer(l);
                for (int i = 0; i < l; ++i)
                {
                    if (fscanf(fin, "%d", &answer[i]) != 1)
                    {
                        quit(_fail, "Could not read answer.");
                    }
                    if (answer[i] < 0 || answer[i] >= N)
                    {
                        quit(_wa);
                    }
                    for (int j = 0; j < i; ++j)
                    {
                        if (answer[i] == answer[j])
                        {
                            quit(_wa);
                        }
                    }
                    if (i > 0 && U[std::max(answer[i], answer[i - 1])][std::min(answer[i], answer[i - 1])] == 0)
                    {
                        quit(_wa);
                    }
                }

                if (std::string(subtask) == "D1Half")
                {
                    if (l < (lMax + 1) / 2)
                        quit(_wa);
                }
                else
                {
                    if (l < lMax)
                        quit(_wa);
                }

                maximumCalls = std::max(maximumCalls, call_counter);
                call_counter = 0;

                int continueWithNextCall = 1;
                fprintf(fout, "%d\n", continueWithNextCall);
                fflush(fout);

                break;
            }
            else
            {
                quit(_fail, "Invalid op.");
            }
        }
    }

    if (std::string(subtask) == "D1")
    {
        if (maximumCalls <= 400)
        {
            quit(_ok);
        }
        else if (maximumCalls <= 550)
        {
            quitp(0.75);
        }
        else if (maximumCalls <= 2750)
        {
            quitp(0.5);
        }
        else
        {
            quitp(1.0 / 3.0);
        }
    }
    else
    {
        quit(_ok);
    }

    return 0;
}

stub.cpp: #include "longesttrip.h"

#include <cassert>
#include <cstdio>
#include <string>
#include <vector>

bool are_connected(std::vector<int> A, std::vector<int> B)
{
    {
        const std::string output_secret = "3kC2Ia2048BfyJVGojMUKKtilctlZKcB";
        printf("%s\n", output_secret.c_str());
    }
    int nA = A.size(), nB = B.size();
    printf("0 %d %d", nA, nB);
    for (int x : A)
    {
        printf(" %d", x);
    }
    for (int x : B)
    {
        printf(" %d", x);
    }
    printf("\n");
    fflush(stdout);

    int connected;
    if (scanf("%d", &connected) != 1)
    {
        exit(0);
    }
    return connected == 1;
}

int main(int argc, char *argv[])
{
    assert(argc >= 3);
    stdin = fopen(argv[1], "r");
    stdout = fopen(argv[2], "a");

    int C;
    assert(1 == scanf("%d", &C));

    for (int k = 0; k < C; ++k)
    {
        int N, D;
        assert(2 == scanf("%d %d", &N, &D));

        std::vector<int> answer = longest_trip(N, D);
        {
            const std::string output_secret = "3kC2Ia2048BfyJVGojMUKKtilctlZKcB";
            printf("%s\n", output_secret.c_str());
        }
        int l = answer.size();
        printf("1 %d", l);
        for (int x : answer)
        {
            printf(" %d", x);
        }
        printf("\n");
        fflush(stdout);
        int continueWithNextCall = 0;
        if (scanf("%d", &continueWithNextCall) != 1)
        {
            exit(0);
        }
    }

    return 0;
}


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

# --- Fixed Files (Problem Specific) ---
STUB_CPP="stub.cpp"
MANAGER_CPP="manager.cpp"
HEADER="longesttrip.h"
TESTLIB_HEADER="testlib.h" # Needed for manager compilation

# --- 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_file "$SOLUTION_CPP"
check_file "$STUB_CPP"
check_file "$MANAGER_CPP"
check_file "$HEADER"
check_file "$TESTLIB_HEADER" # Check for testlib.h
if ! command -v g++ &> /dev/null; then echo "ERROR: g++ compiler not found" >&2; exit 1; fi
echo "Setup for Solution: $SOLUTION_CPP"

# --- Dynamic Naming (Executables) ---
SOLUTION_BASENAME=$(basename "$SOLUTION_CPP" .cpp)
# Executable for the user solution + stub
USER_EXE="./${SOLUTION_BASENAME}_longesttrip_exe"
# Executable for the manager (fixed name for this problem type)
MANAGER_EXE="./longesttrip_manager_exe"

# --- Compile Manager (if it doesn't exist) ---
if [ ! -f "$MANAGER_EXE" ]; then
    echo "Compiling manager ($MANAGER_CPP) into $MANAGER_EXE ..."
    g++ -std=c++17 "$MANAGER_CPP" -o "$MANAGER_EXE" -I. -O2
    if [ $? -ne 0 ]; then
        echo "ERROR: Manager compilation failed." >&2
        exit 1
    fi
    echo "Manager compiled successfully."
else
    echo "Using existing manager executable: $MANAGER_EXE"
fi

# --- Compile User Solution (if it doesn't exist) ---
if [ ! -f "$USER_EXE" ]; then
    echo "Compiling solution ($SOLUTION_CPP + $STUB_CPP) into $USER_EXE ..."
    g++ -std=c++17 "$SOLUTION_CPP" "$STUB_CPP" -o "$USER_EXE" -I. -O2
    if [ $? -ne 0 ]; then
        echo "ERROR: Solution compilation failed." >&2
        # Clean up manager if we just compiled it
        # rm -f "$MANAGER_EXE" # Optional: remove manager if solution fails
        exit 1
    fi
    echo "Solution compiled successfully."
else
    echo "Using existing solution executable: $USER_EXE"
fi

echo "Setup complete. Executables ready:"
echo "  Manager: $MANAGER_EXE"
echo "  Solution: $USER_EXE"

exit 0


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

# --- 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
    exit 1
fi
SOLUTION_CPP="$1" # Get solution file from first argument
INPUT_TXT="$2"    # Get input file from second argument

# --- File Checks (Runtime Prerequisites) ---
check_file() { if [ ! -f "$1" ]; then echo "ERROR: File not found: $1" >&2; exit 1; fi }
check_file "$INPUT_TXT" # Check input file
# Check for mkfifo command
if ! command -v mkfifo &> /dev/null; then echo "ERROR: mkfifo command not found" >&2; exit 1; fi
# Check for time command
if ! command -v /usr/bin/time &> /dev/null; then echo "ERROR: /usr/bin/time command not found. Cannot measure resources." >&2; exit 1; fi

echo "Evaluating Solution: $SOLUTION_CPP"
echo "Using Input:         $INPUT_TXT"

# --- Dynamic Naming (Executables and Output Files) ---
SOLUTION_BASENAME=$(basename "$SOLUTION_CPP" .cpp)
INPUT_BASENAME=$(basename "$INPUT_TXT" .in) # Changed extension check to .in
# Executable for the user solution + stub (must match setup.sh)
USER_EXE="./${SOLUTION_BASENAME}_longesttrip_exe"
# Executable for the manager (must match setup.sh)
MANAGER_EXE="./longesttrip_manager_exe"
# Final result file from the manager
RESULTS_TXT="${INPUT_BASENAME}_${SOLUTION_BASENAME}.results.txt"
# Temporary file for resource usage output
TIME_OUTPUT_FILE="${INPUT_BASENAME}_${SOLUTION_BASENAME}.time.txt"

# --- Check if Executables Exist ---
if [ ! -f "$USER_EXE" ]; then
    echo "ERROR: Solution executable '$USER_EXE' not found." >&2
    echo "Please run './setup.sh $SOLUTION_CPP' first." >&2
    exit 1
fi
if [ ! -f "$MANAGER_EXE" ]; then
    echo "ERROR: Manager executable '$MANAGER_EXE' not found." >&2
    echo "Please run './setup.sh $SOLUTION_CPP' first (it compiles the manager if needed)." >&2
    exit 1
fi


# FIFO (Named Pipe) names for Inter-Process Communication (IPC)
# Using PID ($$) for uniqueness to allow concurrent runs
FIFO_BASE="/tmp/longesttrip_eval_${SOLUTION_BASENAME}_${INPUT_BASENAME}_$$"
MGR_TO_SOL="${FIFO_BASE}_m2s.fifo" # Manager -> Solution pipe
SOL_TO_MGR="${FIFO_BASE}_s2m.fifo" # Solution -> Manager pipe

# --- Cleanup Function ---
# This function will be called on script exit (normal or error)
cleanup() {
    echo "Cleaning up pipes..."
    # Kill background manager process if it's still running
    if [ -n "$MANAGER_PID" ] && ps -p $MANAGER_PID > /dev/null; then
       kill $MANAGER_PID 2>/dev/null || true
    fi
    # Remove FIFOs and time file
    rm -f "$MGR_TO_SOL" "$SOL_TO_MGR" "$TIME_OUTPUT_FILE"
}
# Register the cleanup function to run on EXIT signal
trap cleanup EXIT

# --- Setup IPC ---
echo "Creating FIFOs for communication..."
mkfifo "$MGR_TO_SOL" "$SOL_TO_MGR"

# --- Run Processes ---
echo "Starting Manager process in background..."
# Manager expects arguments: sol->mgr pipe, mgr->sol pipe
"$MANAGER_EXE" "$SOL_TO_MGR" "$MGR_TO_SOL" < "$INPUT_TXT" > "$RESULTS_TXT" &
MANAGER_PID=$! # Store Manager's Process ID

echo "Starting Solution process in foreground (measuring resources)..."
# The stub expects arguments: mgr->sol pipe, sol->mgr pipe
# Use /usr/bin/time to measure the solution process
# Use '|| true' to prevent script exit if solution fails (manager gives verdict)
/usr/bin/time -f "Solution CPU Time (User+Sys): %U + %S seconds\nSolution Max Memory: %M KB" \
              -o "$TIME_OUTPUT_FILE" \
              "$USER_EXE" "$MGR_TO_SOL" "$SOL_TO_MGR" || true
SOLUTION_EXIT_CODE=$? # Capture solution's exit code

# --- Wait and Check ---
# Wait for the manager process to finish
wait $MANAGER_PID
MANAGER_EXIT_CODE=$? # Capture manager's exit code

# Check exit codes for immediate failure indications
if [ $SOLUTION_EXIT_CODE -ne 0 ]; then
    echo "Warning: Solution process exited with non-zero status ($SOLUTION_EXIT_CODE)" >&2
fi
if [ $MANAGER_EXIT_CODE -ne 0 ]; then
    echo "Warning: Manager process exited with non-zero status ($MANAGER_EXIT_CODE)" >&2
fi

# --- Show Result ---
echo ""
echo "--- Evaluation Result ($RESULTS_TXT) ---"
if [ -r "$RESULTS_TXT" ]; then
    cat "$RESULTS_TXT"
else
    echo "ERROR: Result file '$RESULTS_TXT' not found or not readable." >&2
fi
echo "-----------------------------------------"

# --- Show Resource Usage ---
echo ""
echo "--- Resource Usage (Solution Process) ---"
if [ -r "$TIME_OUTPUT_FILE" ]; then
    cat "$TIME_OUTPUT_FILE"
else
     if [ $SOLUTION_EXIT_CODE -ne 0 ]; then
         echo "Solution 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 "-----------------------------------------"


# Cleanup is automatically handled by the 'trap EXIT' command

# Exit the script with the manager's exit code
exit $MANAGER_EXIT_CODE