J - 電子回路 2 (Circuit 2) Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

Submission on AtCoder

Distribution files

When using C++

  • Include circuit.h and implement the required functions.
  • Do not use standard input/output or file input/output.
When using other languages

Use standard input/output, following the JOIG version. Initially read N, R, and the N pairs U_i,V_i.

To ask a question, print ? s on one line, where s is a string of 2N+1 characters, each 0 or 1. It has the same meaning as the argument of query. Read the circuit's output, 0 or 1. If you receive - 1, terminate immediately.

To answer, print ! t on one line, where t is a string of N characters, each & or |. It has the same meaning as the return value of solve. Answer exactly once, and ask at most 1000 questions.

Flush standard output after every output.

Score: 100 points

Problem Statement

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

  • Each switch is assigned a number from 0 to 2N, and each switch has an ON or OFF state. Each switch outputs a value of 0 or 1 as described below.
  • Each component slot is assigned a number from 0 to N - 1. Each component slot also outputs a value of 0 or 1 as described below.
  • The output of each switch and each component slot is determined in order from the highest-numbered one to the lowest, according to the following rules. If a switch and a component slot share the same number, the component slot’s output is determined first.

    • For j = 2N, 2N - 1, \ldots, N, the output of switch j is determined as follows:

      • If switch j is OFF, it outputs 0.
      • If switch j is ON, it outputs 1.
    • For j = N - 1, N - 2, \ldots, 0, let the output of component slot j be x. The output of switch j is determined as follows:

      • If switch j is OFF, it outputs x.
      • If switch j is ON, it outputs 1 - x.
    • For i = N - 1, N - 2, \ldots, 0, component slot i is connected to two switches, U_{i} and V_{i}, where i < U_{i} < V_{i} \le 2N. Let the output of switch U_{i} be x and the output of switch V_{i} be y. The output of component slot i is determined as follows:

      • If component slot i has an AND component, it outputs \min(x, y).
      • If component slot i has an OR component, it outputs \max(x, y).
  • For each j = 1, 2, \ldots, 2N, there exists exactly one i (0 \le i \le N - 1) such that U_{i} = j or V_{i} = j.

  • The output of the circuit board is equal to the output of switch 0.

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.

Figure

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:

  • You can instruct JOI-kun on how to set the 2N + 1 switches. JOI-kun will then configure the switches accordingly and report the circuit board’s output to you.

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.

Implementation Details

You need to submit one file.

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)

    • This function is called exactly once per test case.
    • The argument N represents the number of component slots, N.
    • The argument R is the upper bound on the number of OR components, R.
    • The arguments U and V are arrays of length N, where U[i] and V[i] (0 \le i \le N - 1) are the switch numbers U_{i}, V_{i} connected to component slot i.
    • This function must return a string t of length N consisting of ‘&’ and ‘|’ that satisfies the following condition:

      • For each i = 0, 1, \ldots, N - 1, if component slot i contains an AND component, then t[i] must be ‘&’. If component slot i contains an OR component, then t[i] must be ‘|’.
    • If the returned string t is not of length N, your program is judged as Wrong Answer [1].

    • If t contains characters other than ‘&’ or ‘|’, your program is judged as Wrong Answer [2].
    • If the actual type of component placed in each slot does not match the one represented by the returned string t, your program is judged as Wrong Answer [3].

Your program may call the following function:

  • int query(std::string s)

    • You can use this function to ask JOI-kun a query.
    • The argument s must be a string of length 2N + 1 consisting only of ‘0’ and ‘1’. For each j = 0, 1, \ldots, 2N, if s[j] is ‘0’, switch j is set to OFF. If s[j] is ‘1’, switch j is set to ON.
    • If the length of s is not 2N + 1, your program is judged as Wrong Answer [4].
    • If s contains characters other than ‘0’ or ‘1’, your program is judged as Wrong Answer [5].
    • You must not call this function more than 1\,000 times. If this function is called more than 1\,000 times, your program is judged as Wrong Answer [6].
    • The return value of this function is the output of the circuit board after setting the switches as specified in s.

Important Notices

  • You may implement additional helper functions or declare global variables for internal use.
  • Your program must not use standard input/output or any other file interaction. However, you may use standard error output for debugging.

Compilation and Execution

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):

  • If your program is judged as correct, it reports the number of calls to query as “Accepted: 22”.
  • If your program is judged as any type of Wrong Answer, the sample grader writes its type as “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.

Notices on Grading

The actual grader is not adaptive; it has a fixed answer from the beginning of the interaction.

Constraints

  • 1 \le N \le 8\,000.
  • 1 \le R \le\min(N, 120).
  • i < U_{i} < V_{i} \le 2N (0 \le i \le N - 1).
  • For each j = 1, 2, \ldots, 2N, there exists exactly one i (0 \le i \le N - 1) such that U_{i} = j or V_{i} = j.

Subtasks

  1. (1 point) N = 1.
  2. (4 points) N \le 1\,000, R = 1.
  3. (5 points) N \le 1\,000.
  4. (17 points) U_{i} = i + 1, V_{i} = N + 1 + i (0 \le i \le N - 1), R \le 70.
  5. (8 points) U_{i} = i + 1, V_{i} = N + 1 + i (0 \le i \le N - 1).
  6. (23 points) U_{i} = 2i + 1, V_{i} = 2i + 2 (0 \le i \le N - 1), R \le 70.
  7. (8 points) U_{i} = 2i + 1, V_{i} = 2i + 2 (0 \le i \le N - 1).
  8. (27 points) R \le 70.
  9. (7 points) No additional constraints.

Example Interaction

Below is an example of input that the sample grader reads and the corresponding function calls.

Sample Input 1

1 1
1 2
|
solve call Return value query call Return value
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:

  • Switches 1 and 2 are ON and OFF, respectively, so switch 1 outputs 1 and switch 2 outputs 0.
  • Component slot 0 contains an OR component, and the connected switches 1 and 2 output 1 and 0, respectively. Thus, component slot 0 outputs \max(1, 0) = 1.
  • Switch 0 is OFF, and component slot 0 outputs 1, so switch 0 outputs 1.
  • Therefore, the circuit board outputs 1.

This example satisfies the constraints of all subtasks.

Sample Input 2

3 3
1 2
3 4
5 6
&&|
solve Call Return Value query Call Return Value
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.

AtCoder での提出方法

配布ファイル

C++ を使用する場合

  • circuit.h を include し,問題文で指定された関数を実装してください.
  • 標準入出力やファイルへの入出力を使用しないでください.
その他の言語を使用する場合

配点 : 100 点


問題文

JOI 君は電子回路セットで遊んでいる. 電子回路セットは N 個の AND 部品,N 個の OR 部品 と,1 個の 回路ボード からなる. 回路ボードは 2N+1 個の スイッチ と N 個の 部品スロット で構成され, 各部品スロットに AND 部品か OR 部品を設置することで使用することができる. 回路ボードは,設置された部品とスイッチの状態に応じて,以下のように 0 または 1 の値を出力する.

回路ボードの仕様

  • スイッチには 0 から 2N までの番号が付けられており,各スイッチは ON または OFF の状態を持つ.各スイッチは下に書かれたように 0 または 1 の値を出力する.
  • 部品スロットには 0 から N - 1 までの番号が付けられている.各部品スロットは下に書かれたように 0 または 1 の値を出力する.
  • 各スイッチおよび各部品スロットの出力は,以下の規則によって番号の大きなものから順(同じ番号のスイッチと部品スロットについては部品スロットが先)に定まる.
    • j = 2N, 2N - 1, \dots, N について,スイッチ j は以下を出力する.
      • スイッチ j が OFF であるとき,0 を出力する.
      • スイッチ j が ON であるとき,1 を出力する.
    • j = N - 1, N - 2, \dots, 0 について,部品スロット j の出力を x としたとき,スイッチ j は以下を出力する.
      • スイッチ j が OFF であるとき,x を出力する.
      • スイッチ j が ON であるとき,1 - x を出力する
    • i = N - 1, N - 2, \dots, 0 について,部品スロット i は 2 個のスイッチ U_i, V_i と接続している.ここで,U_i, V_i は i < U_i < V_i \leqq 2N を満たす.スイッチ U_i の出力を x,スイッチ V_i の出力を y としたとき,部品スロット i は以下を出力する.
      • 部品スロット i に AND 部品が設置されているとき,\min(x, y) を出力する.
      • 部品スロット i に OR 部品が設置されているとき,\max(x, y) を出力する.
  • j = 1, 2, \dots, 2N について,U_i = j または V_i = j であるような i (0 \leqq i \leqq N - 1) がただ 1 つ存在する.
  • 回路ボードの出力は,スイッチ 0 の出力と等しい.

例えば,N = 3,U_0 = 1,V_0 = 2,U_1 = 3,V_1 = 4,U_2 = 5,V_2 = 6 で,部品スロット 0, 1, 2 にそれぞれ AND 部品,AND 部品,OR 部品が設置されている場合,回路ボードは以下の図のように表される.

さて,JOI 君がすべての部品スロットに AND 部品を設置しようとしたところ,設置した部品の中に 最大 R 個 の OR 部品がまぎれ込んでいることが明らかになった. AND 部品と OR 部品は見た目で区別することができないため,回路ボードを使用して AND 部品と OR 部品を区別しなければならない. あなたの仕事は,JOI 君に以下の形式の質問を 1\,000 回まで行い,どの部品スロットに OR 部品が設置されているかを特定することである.

  • あなたは JOI 君に 2N+1 個のスイッチをどのような状態にするか指示する.JOI 君は指示された通りにスイッチの状態を変更し,回路ボードの出力をあなたに教える.

回路ボードの回路の接続の情報と設置されている OR 部品の個数の上限が与えられたとき,1\,000 回以下の質問で,どの部品スロットに OR 部品が設置されているかを特定するプログラムを作成せよ

実装の詳細

あなたは 1 つのファイルを提出しなければならない.

あなたの提出するファイルは circuit.cpp という名前である. そのプログラムは #include プリプロセッサ指令によって circuit.h を読み込むこと.

circuit.cpp は以下の関数を実装していなければならない.

  • std::string solve(int N, int R, std::vector<int> U, std::vector<int> V)
    • この関数は各テストケースにおいて 1 回だけ呼び出される.
    • 引数 N は部品スロットの個数 N である.
    • 引数 R は設置されている OR 部品の個数の上限 R である.
    • 引数 U,V は長さ N の配列であり,U[i],V[i] (0 \leqq i \leqq N - 1) は部品スロット i に接続されているスイッチの番号 U_{i}, V_{i} である.
    • この関数は,以下の条件を満たす & と | からなる長さ N の文字列 t を返さなければならない.
      • 各 i = 0, 1, \dots, N - 1 について,部品スロット i に設置されている部品が AND 部品ならば t[i] は & であり,OR 部品ならば t[i] は | である.
    • 戻り値 t の長さが N でない場合,不正解[1] と判定される.
    • 戻り値 t に & でも | でもない文字が含まれる場合,不正解[2] と判定される.
    • 実際に各部品スロットに設置されている部品の種類が,戻り値 t の表すものと異なる場合,不正解[3] と判定される.

あなたのプログラムは以下の関数を呼び出すことができる.

  • int query(std::string s)
    • あなたはこの関数を用いて JOI 君に質問をすることができる.
    • 引数 s は 0 と 1 からなる長さ 2N + 1 の文字列でなければならない.各 j = 0, 1, \dots, 2N について,s[j] が 0 ならばスイッチ j を OFF にすることを,s[j] が 1 ならばスイッチ j を ON にすることを表す.
    • 引数 s の長さが 2N+1 でない場合,不正解[4] と判定される.
    • 引数 s に 0 でも 1 でもない文字が含まれる場合,不正解[5] と判定される.
    • この関数を 1\,000 回より多く呼び出してはならない.1\,000 回より多く呼び出した場合,不正解[6] と判定される.
    • この関数の戻り値は,引数 s の通りにスイッチの状態を変更したときの回路ボードの出力である.

重要な注意

  • 内部での使用のために他の関数を実装したり,グローバル変数を宣言するのは自由である.
  • あなたの提出したプログラムは,標準入力・標準出力,あるいは他のファイルといかなる方法でもやりとりしてはならない.ただし,標準エラー出力にデバッグ情報等を出力することは許される.

コンパイル・実行の方法

作成したプログラムをテストするための,採点プログラムのサンプルが, コンテストサイトからダウンロードできるアーカイブの中に含まれている. このアーカイブには,提出しなければならないファイルのサンプルも含まれている.

採点プログラムのサンプルは 1 つのファイルからなる. そのファイルは grader.cpp である. 作成したプログラムをテストするには, これらのファイル grader.cpp, circuit.cpp, circuit.h を同じディレクトリに置き,次のようにコマンドを実行する.

g++ -std=gnu++20 -O2 -o grader grader.cpp circuit.cpp

なお,アーカイブの中に含まれている compile.sh というファイルを代わりに実行してもよい.その場合,次のようにコマンドを実行する.

./compile.sh

コンパイルが成功すれば,grader という実行ファイルが生成される.

実際の採点プログラムは,採点プログラムのサンプルとは異なることに注意すること. 採点プログラムのサンプルは単一のプロセスとして起動する. このプログラムは,標準入力から入力を読み込み,標準出力に結果を出力する.

採点プログラムのサンプルの入力

T を関数 solve が返すべき長さ N の文字列とする.採点プログラムのサンプルは標準入力から以下の形式で入力を読み込む.

N R
U_0 V_0
U_1 V_1
\vdots
U_{N - 1} V_{N - 1}
T

採点プログラムのサンプルの出力

採点プログラムのサンプルは標準出力へ以下の情報を出力する(引用符は実際には出力されない).

  • 正解の場合,関数 query の呼び出し回数が “Accepted: 22” のように出力される.
  • 不正解の場合,不正解の種類が “Wrong Answer [4]” のように出力される.

採点プログラムのサンプルは,いずれかの不正解の条件が満たされた時点で実行を終了する. 実行するプログラムが複数の不正解の条件を満たした場合,表示される不正解の種類はそれらのうち 1 つのみである.

採点に関する注意

実際の採点プログラムは適応的 (adaptive) ではなく,やりとりの初めから固定された答えを持つ.

制約

  • 1 \leqq N \leqq 8\,000.
  • 1 \leqq R \leqq \min(N, 120).
  • i < U_i < V_i \leqq 2N (0 \leqq i \leqq N - 1).
  • j = 1, 2, \dots, 2N について,U_i = j または V_i = j であるような i (0 \leqq i \leqq N - 1) がただ 1 つ存在する.

小課題

  1. (1 点) N = 1.
  2. (4 点) N \leqq 1\,000,R = 1.
  3. (5 点) N \leqq 1\,000.
  4. (17 点) U_i = i + 1,V_i = N + 1 + i (0 \leqq i \leqq N - 1),R \leqq 70.
  5. (8 点) U_i = i + 1,V_i = N + 1 + i (0 \leqq i \leqq N - 1).
  6. (23 点) U_i = 2i + 1,V_i = 2i + 2 (0 \leqq i \leqq N - 1),R \leqq 70.
  7. (8 点) U_i = 2i + 1,V_i = 2i + 2 (0 \leqq i \leqq N - 1).
  8. (27 点) R \leqq 70.
  9. (7 点) 追加の制約はない.

やりとりの例

採点プログラムのサンプルが読み込む入力の例と,それに対応する関数の呼び出しの例を以下に示す.

入力例 1

1 1
1 2
|
solve の呼び出し 戻り値 query の呼び出し 戻り値
solve(1, 1, [1], [2])
query("010") 1
query("011") 1
query("111") 0
"|"

1 回目の query の呼び出しでは,回路ボードの出力は以下のように計算できる.

  • スイッチ 1, 2 の状態はそれぞれ ON, OFF であるから,スイッチ 1, 2 はそれぞれ 1, 0 を出力する.
  • 部品スロット 0 には OR 部品が設置されていて,接続するスイッチ 1, 2 はそれぞれ 1, 0 を出力しているから,部品スロット 0 は \max(1, 0) = 1 を出力する.
  • スイッチ 0 の状態は OFF で,部品スロット 0 の出力は 1 であるから,スイッチ 0 の出力は 1 である.
  • したがって,回路ボードの出力は 1 である.

この入力例はすべての小課題の制約を満たす.


入力例 2

3 3
1 2
3 4
5 6
&&|
solve の呼び出し 戻り値 query の呼び出し 戻り値
solve(3, 3, [1, 3, 5], [2, 4, 6])
query("0001001") 0
query("0001110") 1
query("0000011") 0
"&&|"

問題文中の図がこの入力例の回路ボードを表している.

この入力例は小課題 3, 6, 7, 8, 9 の制約を満たす.

コンテストサイトからダウンロードできるファイルのうち,sample-01-in.txt は入力例 1 に対応し,sample-02-in.txt は入力例 2 に対応する. また,sample-03-in.txt は小課題 3, 4, 5, 8, 9 の制約を満たし,sample-04-in.txt は小課題 3, 6, 7, 8, 9 の制約を満たす.


Source Name

JOI 2024/2025 春季トレーニング Contest Day4