시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 9 | 9 | 9 | 100.000% |
A mechanical doll is a doll which automatically repeats a specific sequence of motions. In Japan, many mechanical dolls have been created since ancient times.
The motions of a mechanical doll are controlled by a circuit that consists of devices. The devices are connected with tubes. Each device has one or two exits, and can have arbitrarily many (possibly zero) entrances. Each tube connects an exit of a device to an entrance of the same or another device. Exactly one tube is connected to each entrance, and exactly one tube is connected to each exit.
To describe how the doll makes motions, consider a ball that is placed on one of the devices. The ball travels through the circuit. At each step of the travel, the ball leaves the device using one of its exits, travels along the tube connected to the exit and enters the device at the other end of the tube.
There are three types of devices: origin, trigger, and switch. There are exactly one origin, M triggers, and S switches (S can be zero). You must decide the value of S. Each device has a unique serial number.
The origin is the device where the ball is initially placed. It has one exit. Its serial number is 0.
A trigger causes the doll to make a specific motion whenever the ball enters it. Every trigger has one exit. The serial numbers of the triggers are from 1 through M.
Each switch has two exits, which are called 'X' and 'Y'. The state of a switch is either 'X' or 'Y'. After the ball enters a switch, it leaves the switch using the exit given by the current state of the switch. After that, the switch changes its state to the opposite one. Initially, the state of every switch is 'X'. The serial numbers of the switches are from -1 through -S.
You are given the number of triggers M. You are also given a sequence A of length N, each of whose element is a serial number of a trigger. Each trigger might appear some (possibly zero) times in the sequence A. Your task is to create a circuit that satisfies the following conditions:
At the same time, you don't want to use too many switches.
You should implement the following procedure.
create_circuit(int M, int[] A)
M
: the number of triggers.A
: an array of length N, giving the serial numbers of the triggers the ball needs to enter, in the order they are to be entered.A
, and can be obtained as indicated in the implementation notice.Your program should call the following procedure to answer.
answer(int[] C, int[] X, int[] Y)
C
: an array of length M + 1. The exit of the device i (0 ≤ i ≤ M) is connected to the device C[i]
.X
, Y
: arrays of the same length. The length S of these arrays is the number of the switches. For the switch -j (1 ≤ j ≤ S), its exit 'X' is connected to the device X[j - 1]
and its exit 'Y' is connected to the device Y[j - 1]
.C
, X
, and Y
must be an integer between -S and M, inclusive.C
, X
, and Y
must satisfy the conditions in the problem statement.If some of the above conditions are not satisfied, your program is judged as Wrong Answer. Otherwise, your program is judged as Accepted and your score is calculated by S (see Subtasks).
Let M = 4, N = 4, and A = [1, 2, 1, 3]. The grader calls create_circuit(4, [1, 2, 1, 3])
.
The above figure shows a circuit, which is described by a call answer([1, -1, -2, 0, 2], [2, -2], [3, 1])
. The numbers in the figure are the serial numbers of the devices.
Two switches are used. Thus S = 2.
Initially, the states of the switches -1 and -2 are both 'X'.
The ball travels as follows:
0 → 1 → -1 → 2 → -2 → -2 → 1 → -1 → 3 → 0
The ball first returns to the origin, having entered the triggers 1, 2, 1, 3. The states of the switches -1 and -2 are both 'X'. The value of P is 4. Therefore, this circuit satisfies the conditions.
번호 | 배점 | 조건 |
---|---|---|
1 | 2 | For each i (1 ≤ i ≤ M), the integer i appears at most once in the sequence A_{0}, A_{1}, ..., A_{N-1}. |
2 | 4 | For each i (1 ≤ i ≤ M), the integer i appears at most twice in the sequence A_{0}, A_{1}, ..., A_{N-1}. |
3 | 10 | For each i (1 ≤ i ≤ M), the integer i appears at most 4 times in the sequence A_{0}, A_{1}, ..., A_{N-1}. |
4 | 10 | N = 16 |
5 | 18 | M = 1 |
6 | 56 | No additional constraints |
For each test case, if your program is judged as Accepted, your score is calculated according to the value of S:
Note that your score for each subtask is the minimum of the scores for the test cases in the subtask.
The sample grader reads the input from the standard input in the following format.
The sample grader produces three outputs.
First, the sample grader outputs your answer to a file named out.txt
in the following format.
C[i]
X[j - 1]
Y[j - 1]
Second, the sample grader simulates the moves of the ball. It outputs the serial numbers of the devices the ball entered in order to a file named log.txt
.
Third, the sample grader prints the evaluation of your answer to the standard output.
Accepted: S P
.Wrong Answer: MSG
. The meaning of MSG
is as follows:
answered not exactly once
: The procedure answer
is called not exactly once.wrong array length
: The length of C
is not M + 1, or the lengths of X
and Y
are different.over 400000 switches
: S is larger than 400,000.wrong serial number
: There is an element of C
, X
, or Y
which is smaller than -S or larger than M.over 20000000 inversions
: The ball doesn't return to the origin within 200,000,000 state changes of the switches.state 'Y'
: There is a switch whose state is 'Y
' when the ball first returns to the origin.wrong motion
: The triggers which cause motions are different from the sequence A.Note that the sample grader might not create out.txt and/or log.txt when your program is judged as Wrong Answer.
C++17, C++14, C++20, C++14 (Clang), C++17 (Clang), C++20 (Clang)