시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 63 | 20 | 19 | 44.186% |
Anna invented a secret binary operation ★. For non-negative integers x, y less than or equal to 1 000 000 000, a non-negative integer x ★ y less than or equal to 1 000 000 000 is determined. This operation ⋆ is associative. Namely, the equality (x ★ y) ★ z = x ★ (y ★ z) holds for non-negative integers x, y, z less than or equal to 1 000 000 000. This value is simply denoted by x ★ y ★ z.
Anna planned to play a game with Bruno. She asked him to guess the operation ★. She showed N integers A0, A1, . . . , AN−1 to him. She gave to him a number of queries of the following form: “What is the value of AL ★ AL+1 ★ · · · ★ AR?”
Bruno said it is difficult to play this game without hints. Anna decided to give hints to him. Each hint is given as follows: he will choose x, y to ask the value of x ★ y, and she will tell him the value of x ★ y. He can ask for hints when the integers A0, A1, . . . , AN−1 are given in the beginning of the game. He can also ask for hints when she gives a query to him. Of course, he would like to reduce the number of hints. Because he would like to behave as if he knows almost everything about the operation ★, he would especially like to reduce the number of hints after a query is given to him.
Write a program which implements Bruno’s strategy to ask for hints and answer Anna’s queries correctly.
You should write a program which implements the strategy to ask for hints and answer Anna’s queries. Your program should include the header file secret.h
by #include "secret.h"
.
Your program should implement the following procedures.
void Init(int N, int A[])
N
is the number N of the integers shown by Anna. The parameter A
is an array of length N. The elements A[0]
, A[1]
, . . . , A[N-1]
are the integers A0, A1, . . . , AN−1 shown by her.int Query(int L, int R)
int Secret(int X, int Y)
X
and Y
should be integers X and Y satisfying 0 ≤ X ≤ 1 000 000 000 and 0 ≤ Y ≤ 1 000 000 000. If this procedure is called with parameters not satisfying this condition, your program is considered as Wrong Answer [1] and terminated.The sample grader reads the following data from the standard input.
When the program terminates successfully, the sample grader writes to the standard output the values returned by Query one per line. It also writes the following information to the standard error.
Wrong Answer [1]
”. (The quotation mark is not written actually.)Secret
in the procedure Init, and the maximum number of calls to Secret
in each call to the procedure Query.The score will be given to your program if your program terminates successfully for each test case, it is not considered as Wrong Answer [1], and it returns the correct value for each call to Query
.
Your score is calculated as follows.
Here is a sample input for the sample grader and examples of interactions between the procedures. Note that the the following return values are correct if the sample grader is used.
Input
8 1 4 7 2 5 8 3 6 4 0 3 1 7 5 5 2 4
Call | Return |
---|---|
Init(8, [1, 4, 7, 2, 5, 8, 3, 6]) |
None |
Query(0, 3) |
13 |
Query(1, 7) |
32 |
Query(5, 5) |
8 |
Query(2, 4) |
13 |
The procedure Secret
can be called in the procedure Init
or the procedure Query
. For example, when Secret(4, 7)
is called, the return value is 10 because 4 ★ 7 = 10 if the sample grader is used.
The value of 1 ★ 4 ★ 7 ★ 2 is asked in the first query. Since
1 ★ 4 ★ 7 ★ 2 = (1 ★ (4 ★ 7)) ★ 2 = (1 ★ 10) ★ 2 = 11 ★ 2 = 13
holds if the sample grader is used, the procedure Query should return 13.
C++17, C++14, C++20, C++14 (Clang), C++17 (Clang), C++20 (Clang)