Background

“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

在再会之前

Problem Description

“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:

#include <cstdint>
#include <vector>

std::vector<uint32_t> 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:

#include <cstdint>

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):

#include <cstdint>
#include <vector>

uint64_t query(int l, int r);
uint32_t get(int x);

std::vector<uint32_t> recover(int n) {
	std::vector<uint32_t> 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.

Input Format

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.

Output Format

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.

Hint

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