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