| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 2048 MB | 6 | 6 | 6 | 100.000% |
JOI-kun is playing with an electronic circuit set.
The electronic circuit set consists of $N$ AND components, $N$ OR components, and one circuit board. The circuit board is composed of $2N + 1$ switches and $N$ component slots, where each component slot can be used by placing either an AND component or an OR component. The circuit board outputs a value of $0$ or $1$, depending on the placed components and the states of the switches.
Specifications of the Circuit Board
For example, when $N = 3$, $U_0 = 1$, $V_0 = 2$, $U_1 = 3$, $V_1 = 4$, $U_2 = 5$, $V_2 = 6$, and AND components are placed in component slots $0$ and $1$ while an OR component is placed in component slot $2$, the circuit board is represented as shown in the figure below.
Now, JOI-kun attempted to place AND components in all component slots. However, it turned out that up to $R$ OR components were accidentally mixed in. Since AND and OR components look identical, they must be distinguished using the circuit board. Your task is to identify which component slots contain OR components by asking at most $1\, 000$ queries in the following format:
Given the connection structure of the circuit board and the upper bound on the number of OR components, write a program that determines the locations of all OR components using at most $1\, 000$ queries.
The file is circuit.cpp. This program should include circuit.h using the #include preprocessor directive.
circuit.cpp must implement the following function:
std::string solve(int N, int R, std::vector<int> U, std::vector<int> V)
N represents the number of component slots, $N$.R is the upper bound on the number of OR components, $R$.U and V are arrays of length $N$, where U[i] and V[i] ($0 ≤ i ≤ N − 1$) are the switch numbers $U_i$, $V_i$ connected to component slot $i$.&’ and ‘|’ that satisfies the following condition:
t[i] must be ‘&’. If component slot $i$ contains an OR component, then t[i] must be ‘|’.&’ or ‘|’, your program is judged as Wrong Answer [2].Your program may call the following function:
int query(std::string s)
0’ and ‘1’. For each $j = 0, 1, \dots , 2N$, if s[j] is ‘0’, switch $j$ is set to OFF. If s[j] is ‘1’, switch $j$ is set to ON.s is not $2N + 1$, your program is judged as Wrong Answer [4].s contains characters other than ‘0’ or ‘1’, your program is judged as Wrong Answer [5].s.Important Notices
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. To test your program, place the files grader.cpp, circuit.cpp, and circuit.h in the same directory, and compile them using the following command:
g++ -std=gnu++20 -O2 -o grader grader.cpp circuit.cpp
Alternatively, you can execute the compile.sh file included in the archive by running:
./compile.sh
If the compilation is successful, an executable file named grader will be 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
Let $T$ be the string of length $N$ that the function solve should return. The sample grader reads input from standard input in the following format:
$N$ $R$
$U_0$ $V_0$
$U_1$ $V_1$
$\vdots$
$U_{N−1}$ $V_{N−1}$
$T$
Output of the Sample Grader
The sample grader outputs the following information to standard output (quotation marks are not included in the actual output):
query as “Accepted: 22”.Wrong Answer [4]”.The sample grader terminates execution as soon as any incorrect condition is met. If multiple incorrect conditions are met, only one of them is displayed.
The actual grader is not adaptive; it has a fixed answer from the beginning of the interaction.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 1 | $N = 1$. |
| 2 | 4 | $N ≤ 1\, 000$, $R = 1$. |
| 3 | 5 | $N ≤ \,1 000$. |
| 4 | 17 | $U_i = i + 1$, $V_i = N + 1 + i$ ($0 ≤ i ≤ N − 1$), $R ≤ 70$. |
| 5 | 8 | $U_i = i + 1$, $V_i = N + 1 + i$ ($0 ≤ i ≤ N − 1$). |
| 6 | 23 | $U_i = 2i + 1$, $V_i = 2i + 2$ ($0 ≤ i ≤ N − 1$), $R ≤ 70$. |
| 7 | 8 | $U_i = 2i + 1$, $V_i = 2i + 2$ ($0 ≤ i ≤ N − 1$). |
| 8 | 27 | $R ≤ 70$. |
| 9 | 7 | No additional constraints. |
Below is an example of input that the sample grader reads and the corresponding function calls.
| Sample Input 1 | solve Call |
Return Value | query Call |
Return Value |
|---|---|---|---|---|
1 1 1 2 | |
solve(1, 1, [1], [2]) |
|||
query(“010”) |
1 |
|||
query(“011”) |
1 |
|||
query(“111”) |
0 |
|||
“|” |
In the first call to query, the output of the circuit board can be calculated as follows:
This example satisfies the constraints of all subtasks.
| Sample Input 2 | solve Call |
Return Value | query Call |
Return Value |
|---|---|---|---|---|
3 3 1 2 3 4 5 6 &&| |
solve(3, 3, [1, 3, 5], [2, 4, 6]) |
|||
query(“0001001”) |
0 |
|||
query(“0001110”) |
1 |
|||
query(“0000011”) |
0 |
|||
“&&|” |
The diagram in the problem statement represents the circuit board for this example.
This example satisfies the constraints of subtasks 3, 6, 7, 8, 9.
Among the files available for download from the contest site: sample-01-in.txt corresponds to Sample Input 1, and sample-02-in.txt corresponds to Sample Input 2. Additionally, sample-03-in.txt satisfies the constraints of subtasks 3, 4, 5, 8, 9, and sample-04-in.txt satisfies the constraints of subtasks 3, 6, 7, 8, 9.
C++17, C++20, C++23, C++26, C++17 (Clang), C++20 (Clang)