24253번 - Hint 서브태스크점수다국어언어 제한함수 구현투 스텝

Doc Brown managed to turn his DeLorean into a time machine. He has now set his sights on an even bigger problem: longest common subsequence. When given two sequences of numbers $A$ and $B$ with lengths $N$ and $M$, he wants to find the longest (or one of the longest) sequence $C$, such that all elements of $C$ appear in both $A$ and $B$ in the same order (but not necessarily consecutively) as in $C$. He has managed to write a somewhat slow program which will run for many days until it finds a solution. However, he needs an answer as soon as possible. His initial plan was to leave his program running and then in a few days send its output back in time to his present self. The problem is that time travel requires tremendous amounts of energy, so sending the full solution back in time would be extremely expensive.

Now Doc has a new plan, but he needs your help to implement it. He wants to send a short hint about the solution from the future to the present and then use this hint to reconstruct an optimal solution using the hint. Note that it does not necessarily need to be the same optimal solution as the one from the future.

You should write a program hint.cpp which implements two functions: genHint and solve, which achieve Doc’s plan.

Your function genHint needs to have the following prototype:

std::vector genHint(const std::vector& a, const std::vector& b, const std::vector& sol);

It will get called only once and receive as arguments the two given sequences and an optimal solution. It should return a hint, which will be sent to your other function.

Your function solve needs to have the following prototype:

std::vector solve(const std::vector& a, const std::vector& b, const std::vector& hint);

It will get called only once and receive as arguments the two given sequences and the hint that your other function returned. It should return an optimal solution.

Besides these two functions, your program may have any sort of auxiliary functions, classes, variables, etc. However, it must not contain a main function and it must include the header file hint.h. Note that on the grading system your two functions will be called in separate instances of your program, running in separate processes. This means you will not be able to share any global state between the runs of the two functions.

You are given the file Lgrader.cpp, which you can compile together with your program to test it. It will read $N$ and $M$, followed by $A$ and $B$. After that it will read the optimal solution length $K$ and an optimal solution $C$. It will output the length of the hint from your hint function, as well as the solution that your solve function returned. Note that, unlike in the official grading system, the local grader does not run your functions in separate processes.

• $1 ≤ N, M ≤ 2 \times 10^5$
• $0 ≤ A_i, B_j < \min{(N, M)}$