2023-open-t1_Ancient_Machine_2 (JOI JOI_open)
Time limit: 2 seconds | Memory limit: 1024 MB | Task type: interactive
Algorithms: finite state automaton, interactive, constructive, state management

![](_page_0_Picture_0.jpeg)

# Ancient Machine 2

Bitaro and Bibako are archaeologists who excavated and investigated the ruin of JOI Kingdom. In the ruin, Bitaro found an old stone slate, and Bibako found an old machine.

From the results of the study, Bitaro found out that a string *S* of length *N* was written on the stone slate. Each character of the string is either '0' or '1'. However, he does not yet know each character of the string *S*.

On the other hand, from the results of the study, Bibako found out how to use the machine. To use it, we put the stone slate on the machine, input an integer *m* and two sequences of integers *a*, *b*, and make a query. Here the integer *m* and the sequences of integers *a*, *b* should satisfy the following conditions:

*   The integer *m* is between 1 and 1002, inclusive.
*   Both of the lengths of the sequences *a*, *b* are equal to *m*.
*   Every element of the sequences *a*, *b* is an integer between 0 and *m* − 1, inclusive.

If we put the stone slate on the machine, input an integer *m* and two sequences of integers *a*, *b*, and make a query, the machine will operate as follows and will show an integer.

1.  The machine sets 0 in the memory area of the machine.
2.  The machine performs the following *N* operations. The (*i* + 1)-th (0 ≤ *i* ≤ *N* − 1) operation proceeds as follows.

    Let *x* be the current integer set in the memory area of the machine. The machine reads the character *S<sub>i</sub>*. Here, *S<sub>i</sub>* is the *i*-th character of the string *S*, if we count the characters of the string *S* so that the first character is the 0-th character.

    *   If *S<sub>i</sub>* is '0', the machine sets *a<sub>x</sub>* in the memory area of the machine. Here, *a<sub>x</sub>* is the *x*-th element of the sequence *a*, if we count the elements of the sequence *a* so that the first element is the 0-th element.
    *   If *S<sub>i</sub>* is '1', the machine sets *b<sub>x</sub>* in the memory area of the machine. Here, *b<sub>x</sub>* is the *x*-th element of the sequence *b*, if we count the elements of the sequence *b* so that the first element is the 0-th element.
3.  The machine shows the integer which is finally set in the memory area.

Using the machine, Bitaro wants to specify the string written on the stone slate. However, since the machine is very fragile, the number of queries cannot exceed 1000. Moreover, the maximum of the integer *m* input to the machine for a query should be as small as possible.

Write a program which, using the machine, specifies the string written on the stone slate.

![](_page_1_Picture_0.jpeg)

## Implementation Details

You need to submit one file.

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

*   `std::string Solve(int N)`

    This function is called only once for each test case. This function should return a string which is the same as the string *S* written on the stone slate.

    *   The parameter *N* is the length *N* of the string *S* written on the stone slate.
    *   This function should return a string of length *N*. If the length is different from *N*, your program is judged as Wrong Answer [1].
    *   Each character of the return value is either `'0'` or `'1'`. If this condition is not satisfied, your program is judged as Wrong Answer [2].
    *   The return value should be the same as the string *S* written on the stone slate. If this condition is not satisfied, your program is judged as Wrong Answer [3].

Your program can call the following function.

*   `int Query(int m, std::vector<int> a, std::vector<int> b)`

    Using this function, your program can make a query.

    *   The parameter *m* is the integer *m* input to the machine.
    *   The parameters *a*, *b* are the two sequences of integers *a*, *b* input to the machine.
    *   The return value is the integer shown by the machine when we put the stone slate on the machine, input the above integer and sequences, and make a query.
    *   The parameter *m* should be between 1 and 1002, inclusive. If this condition is not satisfied, your program is judged as Wrong Answer [4].
    *   Both of the lengths of the parameters *a*, *b* are equal to *m*. If this condition is not satisfied, your program is judged as Wrong Answer [5].
    *   Every element of the parameters *a*, *b* is between 0 and *m* − 1, inclusive. If this condition is not satisfied, your program is judged as Wrong Answer [6].
    *   The function `Query` should not be called more than 1000 times. If it is called more than 1000 times, your program is judged as Wrong Answer [7].

![](_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`, `ancient2.cpp`, `ancient2.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 ancient2.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*  
*S*

### 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 maximum of the parameter *m* of the function `Query` as "Accepted: 22". However, if your program is judged as correct without calling the function `Query`, it outputs "Accepted: 0".
*   If your program is judged as any type of Wrong Answer, the sample grader writes its type as "Wrong

![](_page_3_Picture_0.jpeg)

Answer [4]".

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

## Constraints

All the input data satisfy the following conditions.

*   *N* = 1000.
*   *S* is a string of length *N*.
*   Each character of the string *S* is either `'0'` or `'1'`.

## Notices for Grading

For every test case, the actual grader is not adaptive. This means the grader has a fixed answer in the beginning.

## Grading

If your program is judged as Wrong Answer for any of the test cases, your score for this task is 0.

If your program is judged as correct for all the test cases, your score is calculated by *M*, which is the maximum of the parameter *m* of the function `Query` for all the test cases. However, if your program is judged as correct without calling the function `Query`, your score is calculated by *M* = 0.

*   If 103 ≤ *M* ≤ 1002, your score is 10 + ⌊ (1002−*M*)<sup>2</sup> / 9000 ⌋ points.
*   If 0 ≤ *M* ≤ 102, your score is 100 points.

Here ⌊*x*⌋ is the largest integer not exceeding *x*.

![](_page_4_Picture_0.jpeg)

## Sample Communication

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

|             |                      |                  |                      |                  |
| :---------- | :------------------- | :--------------- | :------------------- | :--------------- |
| Sample Input 1 | Sample Function Calls |                  |                      |                  |
|             | Function Call to Solve | Return Values    | Function Call to Query | Return Values    |
| 3           | `Solve(3)`           |                  |                      |                  |
| `110`         |                      |                  | `Query(4, [3, 3, 2, 2], [2, 2, 1, 0])` | 3                |
|             |                      |                  | `Query(2, [0, 1], [1, 0])` | 0                |
|             |                      |                  | `Query(1, [0], [0])` | 0                |
|             |                      |                  | `Query(3, [1, 1, 1], [1, 1, 1])` | 1                |
|             |                      | "`110`"            |                      |                  |

Assume that the string *S* written on the stone slate is "`110`". If we put the stone slate on the machine, input (*m*, *a*, *b*) = (4, [3, 3, 2, 2], [2, 2, 1, 0]), and make a query, the machine will operate as follows.

1.  The machine sets 0 in the memory area of the machine.
2.  For the first operation, since *S*<sub>0</sub> is '1', the machine sets *b*<sub>0</sub>, i.e. 2, in the memory area of the machine.
3.  For the second operation, since *S*<sub>1</sub> is '1', the machine sets *b*<sub>2</sub>, i.e. 1, in the memory area of the machine.
4.  For the third operation, since *S*<sub>2</sub> is '0', the machine sets *a*<sub>1</sub>, i.e. 3, in the memory area of the machine.
5.  Since the integer which is finally set in the memory area is 3, the machine shows 3.

Note that this sample input does not satisfy the constraint *N* = 1000.

Among the files which can be obtained from the contest webpage, `sample-02.txt` satisfies the constraint.

Starter code:
grader.cpp: #include <cstdio>
#include <cstdlib>

#include "ancient2.h"

namespace {

using std::exit;
using std::fprintf;
using std::printf;
using std::scanf;

constexpr int N_MAX = 1'000;
constexpr int M_MAX = 1'002;
constexpr int Q_MAX = 1'000;

int N;
char S[N_MAX + 1];

int query_count = 0;
int query_m_max = 0;

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

int Query(int m, std::vector<int> a, std::vector<int> b) {
  if (++query_count > Q_MAX) WrongAnswer(7);
  if (!(1 <= m && m <= M_MAX)) WrongAnswer(4);
  if ((int)a.size() != m || (int)b.size() != m) WrongAnswer(5);
  for (int i = 0; i < m; i++) {
    if (!(0 <= a[i] && a[i] <= m - 1) || !(0 <= b[i] && b[i] <= m - 1))
      WrongAnswer(6);
  }
  if (m > query_m_max) query_m_max = m;
  int memory = 0;
  for (int i = 0; i < N; i++) {
    if (S[i] == '0') {
      memory = a[memory];
    }
    if (S[i] == '1') {
      memory = b[memory];
    }
  }
  return memory;
}

int main() {
  if (scanf("%d", &N) != 1) {
    fprintf(stderr, "Error while reading input.\n");
    exit(1);
  }
  if (scanf("%s", S) != 1) {
    fprintf(stderr, "Error while reading input.\n");
    exit(1);
  }
  std::string s = Solve(N);
  if ((int)s.size() != N) WrongAnswer(1);
  for (int i = 0; i < N; i++) {
    if (!(s[i] == '0' || s[i] == '1')) WrongAnswer(2);
  }
  for (int i = 0; i < N; i++) {
    if (s[i] != S[i]) WrongAnswer(3);
  }
  printf("Accepted: %d\n", query_m_max);
  return 0;
}

ancient2.h: #include <string>
#include <vector>

std::string Solve(int N);

int Query(int m, std::vector<int> a, std::vector<int> b);

ancient2.cpp: #include "ancient2.h"

#include <string>
#include <vector>

namespace {

int variable_example = 1;

}  // namespace

std::string Solve(int N) {
  int m = 2;
  std::vector<int> a(m), b(m);
  a[0] = 0;
  a[1] = 1;
  b[0] = 0;
  b[1] = 1;
  variable_example = Query(m, a, b);
  std::string s(N, '0');
  s[0] = '1';
  return s;
}


Grader code:
grader.cpp: #include <cstdio>
#include <cstdlib>

#include "ancient2.h"

namespace {

using std::exit;
using std::fprintf;
using std::printf;
using std::scanf;

constexpr int N_MAX = 1'000;
constexpr int M_MAX = 1'002;
constexpr int Q_MAX = 1'000;

int N;
char S[N_MAX + 1];

int query_count = 0;
int query_m_max = 0;

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

int Query(int m, std::vector<int> a, std::vector<int> b) {
  if (++query_count > Q_MAX) WrongAnswer(7);
  if (!(1 <= m && m <= M_MAX)) WrongAnswer(4);
  if ((int)a.size() != m || (int)b.size() != m) WrongAnswer(5);
  for (int i = 0; i < m; i++) {
    if (!(0 <= a[i] && a[i] <= m - 1) || !(0 <= b[i] && b[i] <= m - 1))
      WrongAnswer(6);
  }
  if (m > query_m_max) query_m_max = m;
  int memory = 0;
  for (int i = 0; i < N; i++) {
    if (S[i] == '0') {
      memory = a[memory];
    }
    if (S[i] == '1') {
      memory = b[memory];
    }
  }
  return memory;
}

int main() {
  if (scanf("%d", &N) != 1) {
    fprintf(stderr, "Error while reading input.\n");
    exit(1);
  }
  if (scanf("%s", S) != 1) {
    fprintf(stderr, "Error while reading input.\n");
    exit(1);
  }
  std::string s = Solve(N);
  if ((int)s.size() != N) WrongAnswer(1);
  for (int i = 0; i < N; i++) {
    if (!(s[i] == '0' || s[i] == '1')) WrongAnswer(2);
  }
  for (int i = 0; i < N; i++) {
    if (s[i] != S[i]) WrongAnswer(3);
  }
  printf("Accepted: %d\n", query_m_max);
  return 0;
}

ancient2.h: #include <string>
#include <vector>
#include <cstdio>

std::string Solve(int N);

int Query(int m, std::vector<int> a, std::vector<int> b)
{
    printf("? %d\n", m);
    for (int i = 0; i < a.size(); i++) printf("%d%c", a[i], " \n"[i + 1 == a.size()]);
    for (int i = 0; i < b.size(); i++) printf("%d%c", b[i], " \n"[i + 1 == b.size()]);
    fflush(stdout);
    int r; scanf("%d", &r);
    return r;
}

int main()
{
    int N;
    scanf("%d", &N);
    printf("! %s\n", Solve(N).c_str());
    return 0;
}

interactor.cpp: #include "testlib.h"

constexpr int Q_MAX = 1'000;
constexpr int M_MAX = 1'002;

int query_count = 0;
int m_max = 0;

int main(int argc, char* argv[])
{
    registerInteraction(argc, argv);
    int N = inf.readInt();
    std::string S = inf.readToken();
    printf("%d\n", N); fflush(stdout);
    while (true)
    {
        std::string opt = ouf.readToken("[?!]", "opt");
        if (opt == "!")
            break;
        ++query_count;
        if (query_count > Q_MAX)
            quitf(_wa, "Wrong Answer [7]");
        int m = ouf.readInt(1, M_MAX, "m");
        if (m > m_max)
            m_max = m;
        std::vector<int> a = ouf.readInts(m, 0, m - 1, "a");
        std::vector<int> b = ouf.readInts(m, 0, m - 1, "b");
        int mem = 0;
        for (int i = 0; i < N; i++)
        {
            if (S[i] == '0')
                mem = a[mem];
            else
                mem = b[mem];
        }
        printf("%d\n", mem); fflush(stdout);
    }
    std::string pans = ouf.readToken("[01]+", "pans");
    quitif(pans.length() != N, _wa, "Wrong Answer [1]");
    quitif(pans != S, _wa, "Wrong Answer [3]");
    quitif(m_max <= 102, _ok, "Accepted");
    int score = (1002 - m_max) * (1002 - m_max) / 9000 + 10;
    quitp(score, "Accepted");
    return 0;
}

Setup script:

Evaluation script: