29741번 - 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],\dots ,T[l - 1]$ for some $0 ≤ l ≤ 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.

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], \dots , 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.

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]$.

• $2 ≤ N ≤ 16$

The sample grader reads the input in the following format:

• line $1$: $N$
• line $2$: $M[0]$ $M[1]$ $\dots$ $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], \dots , c[n - 1]$ for some nonnegative $n$. The output of the sample grader is in the following format:

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

• coreputer.zip