2023-sp_Belt_Conveyor (JOI JOI_spring)
Time limit: 5 seconds | Memory limit: 1024 MB | Task type: interactive
Algorithms: bitmask, graph theory, interactive, tree

![](_page_0_Picture_0.jpeg)

The 22nd Japanese Olympiad in Informatics (JOI 2022/2023)
Spring Training/Qualifying Trial
March 18–22, 2023 (Komaba, Tokyo)

Contest 2 - Belt Conveyor

## Belt Conveyor

In the factory of JOI Co., Ltd., there are *N* tables, numbered from 0 to *N* − 1. In the factory, there are *N* − 1 belt conveyors, numbered from 0 to *N* − 2. The belt conveyor *i* (0 ≤ *i* ≤ *N* − 2) connects the table *A<sub>i</sub>* and the table *B<sub>i</sub>*. It transports products from one table to the other table. However, we cannot see the direction of transportation. If we ignore the directions of the belt conveyors, every pair of tables is connected by a number of belt conveyors.

IOI-kun is the director of the factory. Since he forgets the direction of transportation of every belt conveyor, he will perform the following sequential operations several times.

1. He chooses a number of belt conveyors, and reverses the directions of transportation of the chosen belt conveyors.
2. He chooses a number of tables, and puts a product on each chosen table.
3. For every table where a product is put, one of the following happens simultaneously.
   - If there is no belt conveyor transporting products from it, nothing happens.
   - If there are belt conveyors transporting products from it, the product on the table is transported by one of such belt conveyors. The product stops at the destination of the belt conveyor. The product will not move anymore.
4. IOI-kun confirms whether there are one or more products on each table. If there are products on a table, IOI-kun takes all of them.
5. For every belt conveyor whose direction is reversed in the operation 1., IOI-kun reverts its direction. Its direction becomes the original direction.

IOI-kun wants to specify the original direction of every belt conveyor by performing the above sequential operations at most 30 times.

Write a program which, given information of the tables connected by the belt conveyors, implements IOI-kun's strategy to specify the original direction of every belt conveyor by performing the above sequential operations at most 30 times.

### Implementation Details

You need to submit one file.

The file is `conveyor.cpp`. It should implement the following function. The program should include `conveyor.h` using the preprocessing directive `#include`.

In `conveyor.cpp`, the following function should be implemented.

![](_page_1_Picture_0.jpeg)

```cpp
void Solve(int N, std::vector<int> A, std::vector<int> B)
```

This function is called only once for each test case.

*   The parameter `N` is the number of tables *N*.
*   The parameters `A`, `B` are arrays of length *N*−1, describing the tables connected by the belt conveyors. Your program can call the following function.

```cpp
std::vector<int> Query(std::vector<int> x, std::vector<int> y)
```

Using this function, IOI-kun performs the operations in the factory.

*   The parameter `x` is an array of length *N* − 1. For 0 ≤ *i* ≤ *N* − 2, IOI-kun reverses the direction of the belt conveyor *i* if `x[i]` = 1, and does not reverse the direction of the belt conveyor *i* if `x[i]` = 0.
*   The parameter `y` is an array of length *N*. For 0 ≤ *j* ≤ *N* −1, IOI-kun puts a product on the table *j* if `y[j]` = 1, and does not put a product on the table *j* if `y[j]` = 0.
*   Let `z` be the return value of this function. It is an array of length *N*. For 0 ≤ *j* ≤ *N* − 1, there are one or more products on the table *j* if `z[j]` = 1, and there is no product on the table *j* if `z[j]` = 0.
*   The length of the array `x` should be equal to *N*-1. If this condition is not satisfied, your program is judged as **Wrong Answer [1]**.
*   Every element of the array `x` should be 0 or 1. If this condition is not satisfied, your program is judged as **Wrong Answer [2]**.
*   The length of the array `y` should be equal to *N*. If this condition is not satisfied, your program is judged as **Wrong Answer [3]**.
*   Every element of the array `y` should be 0 or 1. If this condition is not satisfied, your program is judged as **Wrong Answer [4]**.
*   The function `Query` should not be called more than 30 times. If it is called more than 30 times, your program is judged as **Wrong Answer [5]**.

```cpp
void Answer(std::vector<int> a)
```

Using this function, IOI-kun reports the original direction of each belt conveyor.

*   The parameter `a` is an array of length *N* − 1. For 0 ≤ *i* ≤ *N* − 2, the belt conveyor *i* transports products from *A<sub>i</sub>* to *B<sub>i</sub>* if `a[i]` = 0, and it transports products from *B<sub>i</sub>* to *A<sub>i</sub>* if `a[i]` = 1.
*   The length of the array `a` should be equal to *N*-1. If this condition is not satisfied, your program is judged as **Wrong Answer [6]**.
*   Every element of the array `a` should be 0 or 1. If this condition is not satisfied, your program is judged as **Wrong Answer [7]**.
*   If IOI-kun reports wrong direction of a belt conveyor, your program is judged as **Wrong Answer [8]**.
*   The function `Answer` should be called exactly once. If the function `Answer` is called more than once, your program is judged as **Wrong Answer [9]**. When the function `Solve` terminates, if the function `Answer` is not called, your program is judged as **Wrong Answer [10]**.

![](_page_2_Picture_0.jpeg)

### Important Notices

*   Your program can implement other functions for internal use, or use global variables.
*   Your program must not use the standard input and the standard output. Your program must not communicate with other files by any methods. However, your program may output debugging information to the standard error.

## Compilation and Test Run

You can download an archive file from the contest webpage which contains the sample grader to test your program. The archive file also contains a sample source file of your program.

The sample grader is the file `grader.cpp`. In order to test your program, put `grader.cpp`, `conveyor.cpp`, `conveyor.h` in the same directory, and run the following command to compile your programs. Instead, you may run `compile.sh` contained in the archive file.

```bash
g++ -std=gnu++17 -O2 -o grader grader.cpp conveyor.cpp
```

When the compilation succeeds, the executable file `grader` is generated.

Note that the actual grader is different from the sample grader. The sample grader will be executed as a single process, which will read input data from the standard input and write the results to the standard output.

### Input for the Sample Grader

The sample grader reads the following data from the standard input.

```
N
A0 A1 ... AN-2
B0 B1 ... BN-2
C0 C1 ... CN-2
```

For 0 ≤ *i* ≤ *N* − 2, we have *C<sub>i</sub>* = 0 if the belt conveyor *i* transports products from the table *A<sub>i</sub>* to the table *B<sub>i</sub>*.

![](_page_3_Picture_0.jpeg)

Otherwise, we have *C<sub>i</sub>* = 1.

#### Output of the Sample Grader

The sample grader outputs the following information to the standard output (quotes for clarity).

*   If your program is judged as correct, it reports the number of function calls to `Query` as "Accepted: 22".
*   If your program is judged as any type of Wrong Answer, the sample grader writes its type as "Wrong Answer [4]".

If your program satisfies the conditions of several types of Wrong Answer, the sample grader reports only one of them.

In the sample grader, among the belt conveyors transporting products from the table where a product is put, the belt conveyor transporting the product is chosen uniformly and randomly determined by pseudorandom numbers whose results do not change for different executions. In order to change the seed of pseudorandom numbers, run the sample grader with the first integer argument as follows.

```bash
./grader 2023
```

### Notices for Grading

For some of the test cases, the actual grader is adaptive. This means the grader does not have a fixed answer in the beginning, and responds according to previous function calls to `Query`. It is guaranteed that there is at least one answer which does not contradict all the responses of the the grader.

## Constraints

All the input data satisfy the following conditions.

*   0 ≤ *A<sub>i</sub>* ≤ *N* − 1 (0 ≤ *i* ≤ *N* − 2).
*   0 ≤ *B<sub>i</sub>* ≤ *N* − 1 (0 ≤ *i* ≤ *N* − 2).
*   If we ignore the directions of the belt conveyors, every pair of tables is connected by a number of belt conveyors.

![](_page_4_Picture_0.jpeg)

## Subtasks

1.  (1 point) *N* = 2.
2.  (14 points) *N* = 30.
3.  (10 points) *N* = 100 000, *A<sub>i</sub>* = *i* (0 ≤ *i* ≤ *N* − 2), *B<sub>i</sub>* = *i* + 1 (0 ≤ *i* ≤ *N* − 2).
4.  (75 points) *N* = 100 000.

# Sample Communication

Here is a sample input for the sample grader and corresponding function calls.

| Sample Input 1 | Sample Function Calls    | Return Values |
| :------------- | :----------------------- | :------------ |
| 3              | `Solve(3, [0, 2], [2, 1])` |               |
| 0 2            | `Query([0, 0], [0, 0, 1])` | `[1, 0, 0]`   |
| 2 1            | `Query([1, 0], [1, 0, 1])` | `[0, 1, 1]`   |
| 1 0            | `Query([1, 1], [0, 0, 1])` | `[0, 0, 1]`   |
|                | `Query([0, 1], [1, 1, 1])` | `[1, 0, 1]`   |
|                | `Answer([1, 0])`         |               |

For the first function call to `Query`, another possible return value is `[0, 1, 0]` other than `[1, 0, 0]`.

For the second function call to `Query`, the product on the table 0 is transported to the table 2 by passing through the belt conveyor 0, and stops there. Note that this product will not be transported to the table 1 by passing through the belt conveyor 1.

Note that this sample input does not satisfy the constraints of any subtask.

Among the files which can be obtained from the contest webpage, `sample-02.txt` satisfies the constraints of Subtask 1, and `sample-03.txt` satisfies the constraints of Subtask 2.

Starter code:
grader.cpp: #include "conveyor.h"

#include <cstdio>
#include <cstdlib>
#include <random>
#include <utility>
#include <vector>

namespace {

const int INVALID_X_LENGTH = 1;
const int INVALID_X_RANGE = 2;
const int INVALID_Y_LENGTH = 3;
const int INVALID_Y_RANGE = 4;
const int QUERY_LIMIT_EXCEEDED = 5;
const int INVALID_A_LENGTH = 6;
const int INVALID_A_RANGE = 7;
const int WRONG_A = 8;
const int ANSWER_TWICE = 9;
const int NO_ANSWER = 10;

const int QUERY_LIMIT = 30;

int N;
std::vector<int> A, B, C;

int query_count = 0;
bool answered = false;

void WrongAnswer(int code) {
  printf("Wrong Answer [%d]\n", code);
  exit(0);
}

std::mt19937 rng(0);

int random_select(const std::vector<int> &v) {
  return v[std::uniform_int_distribution<int>(0, v.size() - 1)(rng)];
}

} // namespace

std::vector<int> Query(std::vector<int> x, std::vector<int> y) {
  if (int(x.size()) != N - 1) {
    WrongAnswer(INVALID_X_LENGTH);
  }
  for (int i = 0; i < N - 1; i++) {
    if (x[i] != 0 && x[i] != 1) {
      WrongAnswer(INVALID_X_RANGE);
    }
  }
  if (int(y.size()) != N) {
    WrongAnswer(INVALID_Y_LENGTH);
  }
  for (int i = 0; i < N; i++) {
    if (y[i] != 0 && y[i] != 1) {
      WrongAnswer(INVALID_Y_RANGE);
    }
  }
  query_count++;
  if (query_count > QUERY_LIMIT) {
    WrongAnswer(QUERY_LIMIT_EXCEEDED);
  }
  std::vector<int> z(N, 0);
  std::vector<std::vector<int>> t(N);
  for (int i = 0; i < N - 1; i++) {
    int a = A[i], b = B[i];
    if (x[i] ^ C[i]) {
      std::swap(a, b);
    }
    t[a].push_back(b);
  }
  for (int i = 0; i < N; i++) {
    if (y[i]) {
      if (t[i].empty()) {
        z[i] = 1;
      } else {
        z[random_select(t[i])] = 1;
      }
    }
  }
  return z;
}

void Answer(std::vector<int> a) {
  if (answered) {
    WrongAnswer(ANSWER_TWICE);
  }
  answered = true;
  if (int(a.size()) != N - 1) {
    WrongAnswer(INVALID_A_LENGTH);
  }
  for (int i = 0; i < N - 1; i++) {
    if (a[i] != 0 && a[i] != 1) {
      WrongAnswer(INVALID_A_RANGE);
    }
  }
  if (a != C) {
    WrongAnswer(WRONG_A);
  }
}

int main(int argc, char **argv) {
  if (argc >= 2) {
    long long seed = atoll(argv[1]);
    rng.seed(seed);
  }

  if (scanf("%d", &N) != 1) {
    fprintf(stderr, "Error while reading input.\n");
    exit(1);
  }
  A.resize(N - 1);
  B.resize(N - 1);
  C.resize(N - 1);
  for (int i = 0; i < N - 1; i++) {
    if (scanf("%d", &A[i]) != 1) {
      fprintf(stderr, "Error while reading input.\n");
      exit(1);
    }
  }
  for (int i = 0; i < N - 1; i++) {
    if (scanf("%d", &B[i]) != 1) {
      fprintf(stderr, "Error while reading input.\n");
      exit(1);
    }
  }
  for (int i = 0; i < N - 1; i++) {
    if (scanf("%d", &C[i]) != 1) {
      fprintf(stderr, "Error while reading input.\n");
      exit(1);
    }
  }
  Solve(N, A, B);
  if (!answered) {
    WrongAnswer(NO_ANSWER);
  }
  printf("Accepted: %d\n", query_count);
  return 0;
}
conveyor.cpp: #include "conveyor.h"

#include <vector>

void Solve(int N, std::vector<int> A, std::vector<int> B) {
  std::vector<int> x(N - 1, 0), y(N, 0), z, a(N - 1, 0);
  x[0] = 1;
  y[1] = 1;
  z = Query(x, y);
  a[0] = 1;
  Answer(a);
}

conveyor.h: #include <vector>

void Solve(int N, std::vector<int> A, std::vector<int> B);

std::vector<int> Query(std::vector<int> x, std::vector<int> y);
void Answer(std::vector<int> a);


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

#include <cstdio>
#include <cstdlib>
#include <random>
#include <utility>
#include <vector>

namespace {

const int INVALID_X_LENGTH = 1;
const int INVALID_X_RANGE = 2;
const int INVALID_Y_LENGTH = 3;
const int INVALID_Y_RANGE = 4;
const int QUERY_LIMIT_EXCEEDED = 5;
const int INVALID_A_LENGTH = 6;
const int INVALID_A_RANGE = 7;
const int WRONG_A = 8;
const int ANSWER_TWICE = 9;
const int NO_ANSWER = 10;

const int QUERY_LIMIT = 30;

int N;
std::vector<int> A, B, C;

int query_count = 0;
bool answered = false;

void WrongAnswer(int code) {
  printf("Wrong Answer [%d]\n", code);
  exit(0);
}

std::mt19937 rng(0);

int random_select(const std::vector<int> &v) {
  return v[std::uniform_int_distribution<int>(0, v.size() - 1)(rng)];
}

} // namespace

std::vector<int> Query(std::vector<int> x, std::vector<int> y) {
  if (int(x.size()) != N - 1) {
    WrongAnswer(INVALID_X_LENGTH);
  }
  for (int i = 0; i < N - 1; i++) {
    if (x[i] != 0 && x[i] != 1) {
      WrongAnswer(INVALID_X_RANGE);
    }
  }
  if (int(y.size()) != N) {
    WrongAnswer(INVALID_Y_LENGTH);
  }
  for (int i = 0; i < N; i++) {
    if (y[i] != 0 && y[i] != 1) {
      WrongAnswer(INVALID_Y_RANGE);
    }
  }
  query_count++;
  if (query_count > QUERY_LIMIT) {
    WrongAnswer(QUERY_LIMIT_EXCEEDED);
  }
  std::vector<int> z(N, 0);
  std::vector<std::vector<int>> t(N);
  for (int i = 0; i < N - 1; i++) {
    int a = A[i], b = B[i];
    if (x[i] ^ C[i]) {
      std::swap(a, b);
    }
    t[a].push_back(b);
  }
  for (int i = 0; i < N; i++) {
    if (y[i]) {
      if (t[i].empty()) {
        z[i] = 1;
      } else {
        z[random_select(t[i])] = 1;
      }
    }
  }
  return z;
}

void Answer(std::vector<int> a) {
  if (answered) {
    WrongAnswer(ANSWER_TWICE);
  }
  answered = true;
  if (int(a.size()) != N - 1) {
    WrongAnswer(INVALID_A_LENGTH);
  }
  for (int i = 0; i < N - 1; i++) {
    if (a[i] != 0 && a[i] != 1) {
      WrongAnswer(INVALID_A_RANGE);
    }
  }
  if (a != C) {
    WrongAnswer(WRONG_A);
  }
}

int main(int argc, char **argv) {
  if (argc >= 2) {
    long long seed = atoll(argv[1]);
    rng.seed(seed);
  }

  if (scanf("%d", &N) != 1) {
    fprintf(stderr, "Error while reading input.\n");
    exit(1);
  }
  A.resize(N - 1);
  B.resize(N - 1);
  C.resize(N - 1);
  for (int i = 0; i < N - 1; i++) {
    if (scanf("%d", &A[i]) != 1) {
      fprintf(stderr, "Error while reading input.\n");
      exit(1);
    }
  }
  for (int i = 0; i < N - 1; i++) {
    if (scanf("%d", &B[i]) != 1) {
      fprintf(stderr, "Error while reading input.\n");
      exit(1);
    }
  }
  for (int i = 0; i < N - 1; i++) {
    if (scanf("%d", &C[i]) != 1) {
      fprintf(stderr, "Error while reading input.\n");
      exit(1);
    }
  }
  Solve(N, A, B);
  if (!answered) {
    WrongAnswer(NO_ANSWER);
  }
  printf("Accepted: %d\n", query_count);
  return 0;
}
conveyor.h: #include <algorithm>
#include <vector>
#include <csignal>
#include <cstdio>
#include <cstdlib>
#include <utility>
#include <vector>
void Solve(int N, std::vector<int> A, std::vector<int> B);

std::vector<int> Query(std::vector<int> x, std::vector<int> y);
void Answer(std::vector<int> a);

namespace {

FILE *in, *out;
int N;

const int INVALID_X_LENGTH = 1;
const int INVALID_X_RANGE = 2;
const int INVALID_Y_LENGTH = 3;
const int INVALID_Y_RANGE = 4;
const int QUERY_LIMIT_EXCEEDED = 5;
const int INVALID_A_LENGTH = 6;
const int INVALID_A_RANGE = 7;
const int WRONG_A = 8;
const int ANSWER_TWICE = 9;
const int NO_ANSWER = 10;

} // namespace

std::vector<int> Query(std::vector<int> x, std::vector<int> y) {
  if (int(x.size()) != N - 1) {
    fprintf(out, "%d\n", INVALID_X_LENGTH);
    fflush(out);
    exit(0);
  }
  for (const int &v : x) {
    if (v < 0 || 1 < v) {
      fprintf(out, "%d\n", INVALID_X_RANGE);
      fflush(out);
      exit(0);
    }
  }

  if (int(y.size()) != N) {
    fprintf(out, "%d\n", INVALID_Y_LENGTH);
    fflush(out);
    exit(0);
  }
  for (const int &v : y) {
    if (v < 0 || 1 < v) {
      fprintf(out, "%d\n", INVALID_Y_RANGE);
      fflush(out);
      exit(0);
    }
  }

  fprintf(out, "Q\n");
  for (int i = 0; i < N - 1; i++) {
    fprintf(out, "%d%c", x[i], " \n"[i + 1 == N - 1]);
  }
  for (int i = 0; i < N; i++) {
    fprintf(out, "%d%c", y[i], " \n"[i + 1 == N]);
  }
  fflush(out);

  std::vector<int> ret(N);
  for (int i = 0; i < N; i++) {
    if (fscanf(in, "%d", &ret[i]) != 1) {
      fprintf(stderr, "data not sent from manager.\n");
      exit(1);
    }
    if (i == 0 && ret[i] == -1) {
      exit(0);
    }
    if (ret[i] < 0 || 1 < ret[i]) {
      fprintf(stderr, "wrong data.\n");
      exit(1);
    }
  }
  return ret;
}

void Answer(std::vector<int> a) {
  if (int(a.size()) != N - 1) {
    fprintf(out, "%d\n", INVALID_A_LENGTH);
    fflush(out);
    exit(0);
  }
  for (const int &v : a) {
    if (v < 0 || 1 < v) {
      fprintf(out, "%d\n", INVALID_A_RANGE);
      fflush(out);
      exit(0);
    }
  }

  fprintf(out, "A\n");
  for (int i = 0; i < N - 1; i++) {
    fprintf(out, "%d%c", a[i], " \n"[i + 1 == N - 1]);
  }
  fflush(out);

  int ret;
  if (fscanf(in, "%d", &ret) != 1) {
    fprintf(stderr, "data not sent from manager.\n");
    exit(1);
  }
  if (ret != 0) {
    exit(0);
  }
}

int main(int argc, char **argv) {
  out = stdout;
  in = stdin;

  if (fscanf(in, "%d", &N) != 1) {
    fprintf(stderr, "data not sent from manager.\n");
    return 1;
  }
  std::vector<int> A(N - 1), B(N - 1);
  for (int i = 0; i < N - 1; i++) {
    if (fscanf(in, "%d", &A[i]) != 1) {
      fprintf(stderr, "data not sent from manager.\n");
      return 1;
    }
  }
  for (int i = 0; i < N - 1; i++) {
    if (fscanf(in, "%d", &B[i]) != 1) {
      fprintf(stderr, "data not sent from manager.\n");
      return 1;
    }
  }
  Solve(N, std::move(A), std::move(B));
  fprintf(out, "F\n");
  fflush(out);
  return 0;
}

interactor.cpp: #include "testlib.h"
#ifndef JOI_CONVEYOR_STRATEGY_BASE
#define JOI_CONVEYOR_STRATEGY_BASE

#include <utility>
#include <vector>

struct strategy_base {
  int N;
  std::vector<int> A, B;

  virtual std::vector<int> Query(std::vector<int> x, std::vector<int> y) = 0;
  virtual bool Answer(std::vector<int> a) = 0;

  bool is_tree() {
    std::vector<int> c(N, -1);
    const auto find = [&](int x) {
      while (c[x] >= 0)
        x = c[x];
      return x;
    };
    for (int i = 0; i < N - 1; i++) {
      if (A[i] < 0 || N <= A[i] || B[i] < 0 || N <= B[i]) {
        return false;
      }
      int a = find(A[i]), b = find(B[i]);
      if (a == b)
        return false;
      if (-c[a] < -c[b])
        std::swap(a, b);
      c[a] += c[b];
      c[b] = a;
    }
    return true;
  }
};

#endif


#include <cstdio>
#include <vector>

// xrand1.h - An implementation of xorshift random number generator.
// See the description of class XRand for its usage.
// Version 1.1.1

// Copyright (c) 2013 - 2018  Yui Hosaka (hos@hos.ac)
//
// This software is provided 'as-is', without any express or implied
// warranty. In no event will the authors be held liable for any damages
// arising from the use of this software.
//
// Permission is granted to anyone to use this software for any purpose,
// including commercial applications, and to alter it and redistribute it
// freely, subject to the following restrictions:
//
//    1. The origin of this software must not be misrepresented; you must not
//    claim that you wrote the original software. If you use this software
//    in a product, an acknowledgment in the product documentation would be
//    appreciated but is not required.
//
//    2. Altered source versions must be plainly marked as such, and must not be
//    misrepresented as being the original software.
//
//    3. This notice may not be removed or altered from any source
//    distribution.

#ifndef XRAND1_H_
#define XRAND1_H_

#include <assert.h>
#include <math.h>
#include <stdint.h>
#include <stdlib.h>
#include <algorithm>

#define rand _DO_NOT_USE_RAND_
#define srand _DO_NOT_USE_SRAND_
#define random_shuffle _DO_NOT_USE_RANDOM_SHUFFLE_

class XRand {
 public:
  // Initializes with the given seed.
  explicit XRand(uint64_t seed = 0);
  void Reset(uint64_t seed);

  // Generates the next random number, changing the state of the generator.
  // NextULong() calls NextUInt() twice.
  uint32_t NextUInt();
  uint64_t NextULong();

  // Returns an integer, uniformly distributed in [0, m).
  // It must hold that m != 0.
  // The expected number of calls to NextUInt() is at most two for UInt and four
  // for ULong.
  uint32_t NextUInt(uint32_t m);
  uint64_t NextULong(uint64_t m);

  // Returns an integer, uniformly distributed in [a, b].
  // It must hold that a <= b.
  // The expected number of calls to NextUInt() is at most two for Int and four
  // for Long.
  int32_t NextInt(int32_t a, int32_t b);
  int64_t NextLong(int64_t a, int64_t b);

  // Returns a double, uniformly distributed in [0.0, 1.0).
  // Calls NextUInt() twice.
  double NextDouble();

  // Returns a double, normally distributed with expectation 0 and variance 1.
  // Calls NextUInt() four times.
  double NextGaussian();

  // Shuffles the interval [first, last).
  // Calls NextUInt() (last - first) times.
  template <class RandomAccessIterator>
  void Shuffle(RandomAccessIterator first, RandomAccessIterator last);

 private:
  uint32_t x_, y_, z_, w_;
};

XRand::XRand(uint64_t seed) {
  Reset(seed);
}

void XRand::Reset(uint64_t seed) {
  // Uses MINSTD (Park, Miller and Stockmeyer, 1993) for initial values.
  static constexpr uint64_t kMinstdM = 2147483647;
  static constexpr uint64_t kMinstdA = 48271;
  uint64_t s = 1 + seed % (kMinstdM - 1);
  auto minstd = [&s]() -> uint64_t { return s = s * kMinstdA % kMinstdM; };
  x_ = minstd();
  y_ = minstd();
  z_ = minstd() ^ static_cast<uint32_t>(seed >> 32);
  w_ = minstd() ^ static_cast<uint32_t>(seed);
}

uint32_t XRand::NextUInt() {
  const uint32_t t = x_ ^ x_ << 11;
  x_ = y_;
  y_ = z_;
  z_ = w_;
  return w_ = w_ ^ w_ >> 19 ^ t ^ t >> 8;
}

uint64_t XRand::NextULong() {
  const uint64_t high = NextUInt();
  const uint64_t low = NextUInt();
  return high << 32 | low;
}

uint32_t XRand::NextUInt(uint32_t m) {
  assert(m != 0);
  if (m & (m - 1)) {
    const uint32_t limit = UINT32_MAX / m * m;
    for (; ; ) {
      const uint32_t value = NextUInt();
      if (value < limit) {
        return value % m;
      }
    }
  } else {
    return NextUInt() & (m - 1);
  }
}

uint64_t XRand::NextULong(uint64_t m) {
  assert(m != 0);
  if (m & (m - 1)) {
    const uint64_t limit = UINT64_MAX / m * m;
    for (; ; ) {
      const uint64_t value = NextULong();
      if (value < limit) {
        return value % m;
      }
    }
  } else {
    return NextULong() & (m - 1);
  }
}

int32_t XRand::NextInt(int32_t a, int32_t b) {
  assert(a <= b);
  const uint32_t m = static_cast<uint32_t>(b) - static_cast<uint32_t>(a) + 1;
  return a + (m ? NextUInt(m) : NextUInt());
}

int64_t XRand::NextLong(int64_t a, int64_t b) {
  assert(a <= b);
  const uint64_t m = static_cast<uint64_t>(b) - static_cast<uint64_t>(a) + 1;
  return a + (m ? NextULong(m) : NextULong());
}

double XRand::NextDouble() {
  static constexpr uint64_t kNumValues = 1ULL << 53;
  return static_cast<double>(NextULong() & (kNumValues - 1)) / kNumValues;
}

double XRand::NextGaussian() {
  // Uses Box-Muller transform.
  static const double kPi = acos(-1.0);
  const double value1 = NextDouble();
  const double value2 = NextDouble();
  return sqrt(-2.0 * log1p(-value1)) * cos(2.0 * kPi * value2);
}

template <class RandomAccessIterator>
void XRand::Shuffle(RandomAccessIterator first, RandomAccessIterator last) {
  for (RandomAccessIterator iter = first; iter != last; ++iter) {
    std::iter_swap(first + NextUInt(iter - first + 1), iter);
  }
}

#endif  // XRAND1_H_


struct priority : public strategy_base {
  std::vector<int> p, C;

  priority() : p(), C() {
    N = inf.readInt();
    A.resize(N - 1);
    B.resize(N - 1);
    p.resize(N - 1);
    C.resize(N - 1, -1);
    for (int i = 0; i < N - 1; i++) {
      A[i] = inf.readInt();
    }
    for (int i = 0; i < N - 1; i++) {
      B[i] = inf.readInt();
    }
    for (int i = 0; i < N - 1; i++) {
      p[i] = inf.readInt();
    }
  }

  std::vector<int> Query(std::vector<int> x, std::vector<int> y) override {
    std::vector<std::vector<int>> g(N);
    for (int i = 0; i < N - 1; i++) {
      int a = A[i];
      int b = B[i];
      g[a].push_back(i);
      g[b].push_back(i);
    }
    std::vector<int> z(N, 0);
    for (int i = 0; i < N; i++) {
      if (!y[i])
        continue;
      int e = -1;
      for (int t : g[i]) {
        if (C[t] == -1) {
          if (e == -1 || (C[e] == -1 && p[e] < p[t])) {
            e = t;
          }
        } else {
          int a = A[t], b = B[t];
          if (C[t] ^ x[t]) {
            std::swap(a, b);
          }
          if (a == i) {
            if (e == -1 || C[e] == -1 || p[e] < p[t]) {
              e = t;
            }
          }
        }
      }
      if (e == -1) {
        z[i] = 1;
      } else {
        z[A[e] ^ B[e] ^ i] = 1;
        if (C[e] == -1) {
          C[e] = x[e] ^ (A[e] != i);
        }
      }
    }
    return z;
  }

  bool Answer(std::vector<int> a) override { return a == C; }
};

// あらかじめ答えを固定。移動先はランダムに決める。
// 1 回も製品が通っていないかつ、両端の製品が停止したことがない、ようなコンベアがあったら無条件に WA にする。

#include <cstdio>
#include <utility>
#include <vector>
#include <iostream>

struct random1 : public strategy_base {
  XRand rnd;
  std::vector<int> C;
  std::vector<int> passed;

  random1() : rnd(), C(), passed() {
    N = inf.readInt();
    A.resize(N - 1);
    B.resize(N - 1);
    C.resize(N - 1);
    passed.resize(N - 1, false);
    for (int i = 0; i < N - 1; i++) {
      A[i] = inf.readInt();
    }
    for (int i = 0; i < N - 1; i++) {
      B[i] = inf.readInt();
    }
    for (int i = 0; i < N - 1; i++) {
      C[i] = inf.readInt();
    }

    std::string str = inf.readToken();
    char ss[256];
    sprintf(ss, "%s", str.c_str());
    unsigned long long seed = 0;
    sscanf(ss, " 0x%llX", &seed);
    rnd.Reset(seed);
  }

  std::vector<int> Query(std::vector<int> x, std::vector<int> y) override {
    struct edge {
      int to, id;
    };
    std::vector<std::vector<edge>> g(N), rev(N);
    for (int i = 0; i < N - 1; i++) {
      int a = A[i], b = B[i];
      if (C[i] ^ x[i]) {
        std::swap(a, b);
      }
      g[a].push_back({b, i});
      rev[b].push_back({a, i});
    }
    std::vector<int> z(N, 0);
    for (int i = 0; i < N; i++) {
      if (y[i]) {
        if (g[i].empty()) {
          z[i] = 1;
          for (const auto &[to, id] : rev[i]) {
            passed[id] = true;
          }
        } else {
          const auto [to, id] = g[i][rnd.NextInt(0, g[i].size() - 1)];
          z[to] = 1;
          passed[id] = true;
        }
      }
    }
    return z;
  }

  bool Answer(std::vector<int> a) override {
    for (int i = 0; i < N - 1; i++)
      if (!passed[i])
        return false;
    return a == C;
  }
};

#include <climits>
#include <csignal>
#include <cstdio>
#include <cstdlib>
#include <vector>

const int INVALID_X_LENGTH = 1;
const int INVALID_X_RANGE = 2;
const int INVALID_Y_LENGTH = 3;
const int INVALID_Y_RANGE = 4;
const int QUERY_LIMIT_EXCEEDED = 5;
const int INVALID_A_LENGTH = 6;
const int INVALID_A_RANGE = 7;
const int WRONG_A = 8;
const int ANSWER_TWICE = 9;
const int NO_ANSWER = 10;

const std::vector<int> WA_FROM_STUB = {
    INVALID_X_LENGTH, INVALID_X_RANGE,  INVALID_Y_LENGTH,
    INVALID_Y_RANGE,  INVALID_A_LENGTH, INVALID_A_RANGE,
};

const int QUERY_LIMIT = 30;

FILE *in, *out;

void wrong(const int num) {
  quitf(_wa, "translate:wrong\nWrong Answer [%d]\n", num);
  if (num)
    exit(0);
}

void ok() {
  quitf(_ok, "translate:success\nAccepted\n");
}

std::vector<int> read01seq(const int len) {
  std::vector<int> ret(len);
  for (int i = 0; i < len; i++) {
    if (fscanf(out, "%d", &ret[i]) != 1 || (ret[i] < 0 || 1 < ret[i])) {
      wrong(0);
      fprintf(stderr, "wrong format from stub.\n");
      exit(0);
    }
  }
  return ret;
}

int main(int argc, char **argv) {
  registerInteraction(argc, argv);

  std::string strategy_name = inf.readToken();
  strategy_base *strategy_ = nullptr;
  if (strategy_name == "random1") {
    strategy_ = new random1();
  } else if (strategy_name == "priority") {
    strategy_ = new priority();
  } else {
    wrong(0);
    fprintf(stderr, "unknown strategy.\n");
    return 0;
  }
  strategy_base &strategy = *strategy_;

  out = stdin;
  in = stdout;

  const int N = strategy.N;
  if (!strategy.is_tree()) {
    wrong(0);
    fprintf(stderr, "not tree.\n");
    return 0;
  }

  fprintf(in, "%d ", N);
  for (int i = 0; i < N - 1; i++) {
    fprintf(in, "%d ", strategy.A[i]);
  }
  for (int i = 0; i < N - 1; i++) {
    fprintf(in, "%d%c", strategy.B[i], " \n"[i + 1 == N - 1]);
  }
  fflush(in);

  int query_count = 0;
  bool answered = false;
  while (true) {
    char c;
    if (fscanf(out, " %c", &c) != 1) {
      wrong(0);
      fprintf(stderr, "data not sent from stub.\n");
      return 0;
    }
    if (c == 'Q') {
      query_count++;
      if (query_count > QUERY_LIMIT) {
        fprintf(in, "-1\n");
        fflush(in);
        wrong(QUERY_LIMIT_EXCEEDED);
      }
      std::vector<int> x = read01seq(N - 1);
      std::vector<int> y = read01seq(N);
      std::vector<int> ret = strategy.Query(x, y);
      for (int i = 0; i < N; i++) {
        fprintf(in, "%d%c", ret[i], " \n"[i + 1 == N]);
      }
      fflush(in);
    } else if (c == 'A') {
      if (answered) {
        fprintf(in, "1\n");
        fflush(in);
        wrong(ANSWER_TWICE);
      }
      answered = true;
      std::vector<int> a = read01seq(N - 1);
      if (!strategy.Answer(a)) {
        fprintf(in, "1\n");
        fflush(in);
        wrong(WRONG_A);
      }
      fprintf(in, "0\n");
      fflush(in);
    } else if (c == 'F') {
      break;
    } else {
      for (const int e : WA_FROM_STUB) {
        if (c == '0' + e) {
          wrong(e);
        }
      }
      wrong(0);
      fprintf(stderr, "wrong character: %c\n", c);
      return 0;
    }
  }
  if (!answered) {
    wrong(NO_ANSWER);
  }
  ok();
  return 0;
}

Setup script:

Evaluation script: