P8150 Sayounara | Sayounara

“Has everything in the past become meaningless?” “Not to that extent yet.” “Have you already finished everything you wanted to do?” “Now, it seems I can only move forward by making choices and trade-offs.” “Have you said goodbye?” “… Not yet, but I am trying.” > I have > > 我仍有 > > plenty want to say > > 无数未道尽的言语 > > Before > > 在离开之前 > > I leave this world > > 在再会之前

“What is this…?” “Ah… a diary management program I wrote myself.” “Pfft… ‘What kind of normal person writes a diary?’ You would usually say that, right?” “… Don’t make fun of me.” “Fine, fine. But it looks like you forgot the password?” “…… I have my own ways.” “Huh…? What is this, recovery software?” “Yeah… The password can be represented as a non-negative integer sequence of length $n$, **where all elements are pairwise distinct**. This software can perform two kinds of operations: first, query the result of the sum of a continuous interval minus the minimum value in that interval; second, query the value at a position. Now if I need to recover the password…” “Eh? Why not just use the second operation $n$ times?” “This is a trial version… so the second operation can only be used twice… and the first operation also seems to have some limits, so…” “This… By the way, why is recovering a password so troublesome? Shouldn’t there be some convenient mechanism like ‘retrieve password’?” “… Most likely it was arranged by that person.” ### Brief Statement There is a non-negative integer sequence $a$ with pairwise distinct elements, of length $n$. You may perform the following two types of queries multiple times: - Given $l, r$, obtain $\left(\sum_{k=l}^r a_k\right)-\left(\min_{k=l}^r a_k\right)$. - Given $k$, obtain the value of $a_k$. This type of query can be performed at most twice. You need to deduce the entire sequence with as few queries as possible. **All queries in this problem use $1$ as the starting index, but when you return the answer you must return a `vector` indexed from $0$. Please note this.** ### Interaction Details This problem only allows C++11 / C++17 submissions. You need to implement the following function: ```cpp #include #include std::vector recover(int n); ``` This function receives the password length $n$ and returns the recovered password (the return value should be a `vector` of size $n$). You may use the following two functions: ```cpp #include uint64_t query(int l, int r); uint32_t get(int x); ``` Here, `query` corresponds to the first operation in the statement, and `get` corresponds to the second operation. Below is a sample program (only demonstrating how to use the interaction library): ```cpp #include #include uint64_t query(int l, int r); uint32_t get(int x); std::vector recover(int n) { std::vector ans(n); int what = query(1, n), hey = get(1); for (int i = 0; i < n; ++i) ans[i] = i + 1; return ans; } ``` The problem provides a sample interaction library `lib.cpp` (not the real implementation). You can compile and run locally with the command `g++ -o code code.cpp lib.cpp`.

**This is the input format of the interaction library. Contestants do not need to, and cannot, read any information from standard input.** The first line contains a positive integer $n$, the password length. The second line contains $n$ non-negative integers, the password.

**This is the output format of the interaction library. Contestants do not need to, and cannot, write any information to standard output.** There are four possible outputs: - `0 A B`: The contestant’s answer is correct. Here `A` is the number of times operation 1 is used, and `B` is the number of times operation 2 is used. - `-1`: The contestant’s function finishes successfully, but the answer is incorrect. - `-2`: The $l, r$ passed when calling operation 1 do not meet the requirements. - `-3`: Operation 1 was called more than $2n$ times. - `-4`: Operation 2 was called more than twice.

### Scoring Rules This problem has no subtasks. All testdata guarantee $n=10^6$. If your answer is wrong or you exceed the query limits on any test point, you will achieve a great score of 0 points. If you pass all test points, let $x$ be the maximum number of times you called operation 1 among all testdata. Then your score is: $$ \begin{cases} \frac{60}{e^7-1}\left(e^{10-\max\left\{\frac{x-10^6}{100},3\right\}}-1\right)+40,&x\le 1001000\\ 25,&\mathrm{otherwise.} \end{cases} $$ Translated by ChatGPT 5