Coreputer

Coreputer, the brand new computing machine has $N$ cores numbered from $0$ to $N-1$. Recent
maintenance revealed that some of the cores are malfunctioning. It is unknown which specific
cores are malfunctioning, but there is at least one malfunctioning core.

To find the malfunctioning cores, Coreputer can run diagnostic scans. In each scan, the user tags
a (possibly empty) group of distinct cores $T[0], \ldots, T[l-1]$ for some $0 \le l \le N$. The rest of the
cores are untagged. Coreputer then benchmarks the tagged cores and the untagged ones. Finally,
it reports which of the two groups contains a greater number of malfunctioning cores, or that the
two groups contain an equal number of malfunctioning cores. Note that an empty group contains
$0$ malfunctioning cores.

Your task is to find the malfunctioning cores by running diagnostic scans on Coreputer.

Implementation Details

You should implement the following procedure.

int[] malfunctioning_cores(int N)

• $N$: the number of cores.
• This procedure should return an array $c = [c[0], c[1], \ldots, c[N-1]]$, where for each $i$ from $0$
  to $N-1$, inclusive, $c[i] = 1$ if core $i$ is malfunctioning, and $c[i] = 0$ otherwise.
• This procedure is called exactly once for each test case.

The above procedure can make calls to the following procedure:

int run_diagnostic(int[] T)

• $T$: an array of distinct cores.
• This procedure returns
• $1$ if there are more tagged cores than untagged cores which are malfunctioning;
• $0$ if the number of tagged and untagged malfunctioning cores are equal;
• $-1$ if there are fewer tagged cores than untagged cores which are malfunctioning.
• This procedure can be called at most 32 times in each test case.

The grader is not adaptive, meaning that the set of malfunctioning cores is fixed before a call to
malfunctioning_cores is made.

Example

Consider a scenario when there are $N = 4$ cores, and only core 2 is malfunctioning.

Procedure malfunctioning_cores is called the following way:

malfunctioning_cores(4)

The procedure may call run_diagnostic as follows.

In the first call, there are no malfunctioning tagged cores, and one untagged core is
malfunctioning, so the procedure returns $-1$.

After the third call returns 1, it is clear that at least one tagged core (that is, core 2) is
malfunctioning. But then, the number of untagged malfunctioning cores must be zero, so we
conclude that no other core is malfunctioning.

Therefore, the procedure malfunctioning_cores should return $[0, 0, 1, 0]$.

Constraints

• $2 \le N \le 16$

In this subtask, you can obtain a partial score based on the number of calls to run_diagnostic:
* 50% of points if $24 < q \le 32$ calls
* 75% of points if $18 < q \le 24$ calls
* 100% of points if $q \le 18$ calls

If the calls to the procedure run_diagnostic do not conform to the constraints described in Implementation Details, or the return value of malfunctioning_cores is incorrect, the score of your solution for that subtask will be 0.

Sample Grader

The sample grader reads the input in the following format:

• line 1: $N$
• line 2: $M[0] \; M[1] \; \ldots \; M[N-1]$

where for each $i$ from $0$ to $N-1$, inclusive, $M[i] = 1$ if core $i$ is malfunctioning, and $M[i] = 0$
otherwise.

Before calling malfunctioning_cores, the sample grader checks whether there is at least one
malfunctioning core. If this condition is not met, it prints the message No Malfunctioning Cores 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 error messages:

• invalid array: in a call to run_diagnostic, array $T$
• has more than $N$ elements, or
• contains an element that is not an integer between $0$ and $N-1$, inclusive, or
• contains the same element at least twice.
• too many calls: the number of calls made to run_diagnostic exceeds 32.

Otherwise, let the elements of the array returned by malfunctioning_cores be
$c[0], c[1], \ldots, c[n-1]$ for some nonnegative $n$. The output of the sample grader is in the following
format:

• line 1: $c[0] \; c[1] \; \ldots \; c[n-1]$
• line 2: the number of calls to run_diagnostic

You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution, then provide a complete implementation in C++17. You should correctly implement the routine(s) described in Implementation Details, without reading or writing anything directly from stdin or to stdout, as input and output are passed through the implemented routines. Assume your code will be run on the OFFICIAL grader, and do not add a main, a sample grader, or any other functionality unless it has been explicitly requested.
Put your final solution within a single code block: cpp <your code here>

Problem statement (Coreputer)

Coreputer, the brand new computing machine has $N$ cores numbered from $0$ to $N-1$. Recent
maintenance revealed that some of the cores are malfunctioning. It is unknown which specific
cores are malfunctioning, but there is at least one malfunctioning core.

To find the malfunctioning cores, Coreputer can run diagnostic scans. In each scan, the user tags
a (possibly empty) group of distinct cores $T[0], \ldots, T[l-1]$ for some $0 \le l \le N$. The rest of the
cores are untagged. Coreputer then benchmarks the tagged cores and the untagged ones. Finally,
it reports which of the two groups contains a greater number of malfunctioning cores, or that the
two groups contain an equal number of malfunctioning cores. Note that an empty group contains
$0$ malfunctioning cores.

Your task is to find the malfunctioning cores by running diagnostic scans on Coreputer.

Implementation Details

You should implement the following procedure.

int[] malfunctioning_cores(int N)

• $N$: the number of cores.
• This procedure should return an array $c = [c[0], c[1], \ldots, c[N-1]]$, where for each $i$ from $0$
  to $N-1$, inclusive, $c[i] = 1$ if core $i$ is malfunctioning, and $c[i] = 0$ otherwise.
• This procedure is called exactly once for each test case.

The above procedure can make calls to the following procedure:

int run_diagnostic(int[] T)

• $T$: an array of distinct cores.
• This procedure returns
• $1$ if there are more tagged cores than untagged cores which are malfunctioning;
• $0$ if the number of tagged and untagged malfunctioning cores are equal;
• $-1$ if there are fewer tagged cores than untagged cores which are malfunctioning.
• This procedure can be called at most 32 times in each test case.

The grader is not adaptive, meaning that the set of malfunctioning cores is fixed before a call to
malfunctioning_cores is made.

Example

Consider a scenario when there are $N = 4$ cores, and only core 2 is malfunctioning.

Procedure malfunctioning_cores is called the following way:

malfunctioning_cores(4)

The procedure may call run_diagnostic as follows.

In the first call, there are no malfunctioning tagged cores, and one untagged core is
malfunctioning, so the procedure returns $-1$.

After the third call returns 1, it is clear that at least one tagged core (that is, core 2) is
malfunctioning. But then, the number of untagged malfunctioning cores must be zero, so we
conclude that no other core is malfunctioning.

Therefore, the procedure malfunctioning_cores should return $[0, 0, 1, 0]$.

Constraints

• $2 \le N \le 16$

In this subtask, you can obtain a partial score based on the number of calls to run_diagnostic:
* 50% of points if $24 < q \le 32$ calls
* 75% of points if $18 < q \le 24$ calls
* 100% of points if $q \le 18$ calls

If the calls to the procedure run_diagnostic do not conform to the constraints described in Implementation Details, or the return value of malfunctioning_cores is incorrect, the score of your solution for that subtask will be 0.

Sample Grader

The sample grader reads the input in the following format:

• line 1: $N$
• line 2: $M[0] \; M[1] \; \ldots \; M[N-1]$

where for each $i$ from $0$ to $N-1$, inclusive, $M[i] = 1$ if core $i$ is malfunctioning, and $M[i] = 0$
otherwise.

Before calling malfunctioning_cores, the sample grader checks whether there is at least one
malfunctioning core. If this condition is not met, it prints the message No Malfunctioning Cores 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 error messages:

• invalid array: in a call to run_diagnostic, array $T$
• has more than $N$ elements, or
• contains an element that is not an integer between $0$ and $N-1$, inclusive, or
• contains the same element at least twice.
• too many calls: the number of calls made to run_diagnostic exceeds 32.

Otherwise, let the elements of the array returned by malfunctioning_cores be
$c[0], c[1], \ldots, c[n-1]$ for some nonnegative $n$. The output of the sample grader is in the following
format:

• line 1: $c[0] \; c[1] \; \ldots \; c[n-1]$
• line 2: the number of calls to run_diagnostic

Execution limits

Your solution will have 0.5 second(s) execution time and 2048 MB memory limit to solve each test case.

Starting code

Here's your starting code with some skeleton/placeholder functionality:

#include "coreputer.h"

std::vector<int> malfunctioning_cores(int N) {
    return {};
}

参考代码

#include "coreputer.h"

std::vector<int> malfunctioning_cores(int N) {
    return {};
}

请将你的实现写入 submission.cpp（可沿用上面的框架与题目头文件）。判题时你的代码会与题目自带的 manager / grader 一起编译链接，并按题目规定的协议通信。

本题为交互题：你的程序需与题目自带的 manager 进程通信（按题目约定经标准输入输出或命名管道），无需自行读取测试数据。

由 manager 进程打印判定结果，无需自行写出答案。

include "coreputer.h"

std::vector<int> malfunctioning_cores(int N) {
return {};
}