|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|1 초||512 MB||0||0||0||0.000%|
You did it! You have finally made it to the X spot of the treasure map, but, to open the treasure chest, you first need to break the code. On the label attached to the chest, the rules of the game are written: the code is a binary sequence of length N, and in order to find this sequence you’re allowed to ask questions of the following type: “is S a subsequence of the hidden sequence?”
A binary sequence S, with values S1, S2, … , SK is considered to be a subsequence of the code C, with values C1, C2, … , CN, if and only if S can be obtained by deleting some of the values of C.
Formally, S is a subsequence of C if and only if there exist K values 1 ≤ i1 < i2 < ⋯ < iK ≤ N such that Cij = Sj for any 1 ≤ j ≤ N.
You will get a part of the treasure if you succeed in cracking the code. Depending on how short the longest query you’ve asked for is, you’ll get more or less of the treasure. (which, in our case, is represented by 100 points)
You should include the library “grader.h” at the beginning of your source code and implement the following procedure:
vector < int > findSequence (int N);
Your code may contain any number of additional procedures and may declare global variables.
Your solution can call the following function any number of times, as long as the overall process fits in the time limit:
bool isSubsequence (vector < int > S);
Let L be the length of the longest asked query. There are 2 subtasks for the problem. For each subtask you will receive a score equal to the smallest score obtained on one of the tests in that subtask:
|L ≤ ⌊N/2⌋ + 1||20|
|L ≤ ⌊3N/4⌋ + 1||15|
|L ≤ N||10|
|L ≤ ⌊N/2⌋ + 1||80|
|L ≤ ⌊N/2⌋ + 3||72|
|L ≤ ⌊3N/4⌋ + 1||44|
|L ≤ N||24|
The grader calls the function findSequence (3). The hidden sequence is 0 1 0. Your source calls the functions isSubsequence ([0, 1]) and isSubsequence ([1, 0]) and receives a positive answer for both queries. It then calls isSubsequence ([1, 1]), which returns a negative answer (0) and your program returns the sequence [0, 1, 0] by using the information it has received.
You’re provided with an archive containing a sample grader to help you test your sources locally. It includes a header file, a file grader.cpp, and a file sequence.cpp that you need to implement.
The grader reads from standard input the hidden sequence and then calls the function you’ve implemented to find the sequence. In the end, it checks if the returned sequence matched the hidden one and, if so, it prints the maximum length of a query you’ve asked for to the standard output.
The format of the input the grader reads is:
N C1 C2 C3 ... CN
The sample grader is not the one used for evaluation, but one that should assist you in your local testing. Of course, you are allowed to change it, but the source you submit should still respect the format (by including “grader.h” and implementing the function findSequence)
C++17, C++14, C++20, C++14 (Clang), C++17 (Clang), C++20 (Clang)