P17767 「LDOI R2」排列 / Permutation
Background
When submitting on Luogu, please add the following line at the beginning of your code:
```cpp
int query(int i, int j, int k);
```
Description
The interactor has a hidden $1$-indexed permutation $a$.
You may query pairwise distinct $i,j,k\ (1\le i,j,k \le n)$, and the interactor returns $|a_i-a_j|+|a_j-a_k|$.
Two permutations $a,b$ are defined to be equivalent if and only if for any pairwise distinct $i,j,k\ (1\le i,j,k \le n)$, $|a_i-a_j|+|a_j-a_k| = |b_i-b_j|+|b_j-b_k|$.
After finishing the queries, you need to find any permutation equivalent to $a$.
The query limit is described in the scoring section.
### Implementation Details
**Contestants do not need to, and should not, implement the main function.**
You need to implement the following function:
```cpp
vector solve(int n, int sid);
```
- The parameter `n` is the length of the permutation, and `sid` is the subtask number (in particular, `sid` is $0$ for samples).
- You need to return a `vector` of length $n$, representing the permutation $b$ you found.
- This function will be called **exactly once** in a test case.
You may call the following function:
```cpp
int query(int i, int j, int k);
```
- You need to ensure $1 \le i,j,k \le n$, $i \neq j$, $i \neq k$, $j \neq k$.
- This function will return the value of $|a_i-a_j|+|a_j-a_k|$.
Input Format
The **sample interactor** will read data in the following format.
The first line contains two numbers $n, \text{sid}$.
The next line contains $n$ numbers representing the sequence $a$.
Output Format
The **sample interactor** will output data in the following format.
The first line contains one number representing the number of queries you made.
The second line contains $n$ numbers representing the sequence $b$ you returned.
Explanation/Hint
### Explanation
The following is a possible interaction (only for demonstrating the interaction format):
| Contestant's program | Interactor |
|:-:|:-:|
|| Call `solve(4,0)` |
| Call `query(1,2,3)` ||
|| Return `3` |
| Call `query(2,3,4)` ||
|| Return `5` |
| Return `{2,3,1,4}` ||
### Constraints
**This problem uses subtask scoring.**
| Subtask | $n =$ |
|:-:|:-:|
| $1$ | $8$ |
| $2$ | $8 \times 10^4$ |
The interactor guarantees that when the number of queries is $\le 2.4 \times 10^5$, the time used does not exceed $1.2$ seconds, and the space used does not exceed $8$ MB.
### Scoring
Let $Q$ be the number of queries you make.
In Subtask $1$, if $Q \le 10^3$ and the answer is correct, you get $10$ points; otherwise you get $0$.
In Subtask $2$, if the answer is correct, you are scored according to the following table; otherwise you get $0$.
| Range | Score |
|:-:|:-:|
| $Q > 2.4 \times 10^5$ | $0$ |
| $10^5 < Q \le 2.4 \times 10^5$ | $\left\lfloor 90 \left( \frac{2.4 \times 10^5 - Q}{1.4 \times 10^5} \right)^3 \right\rfloor$ |
| $Q \le 10^5$ | $90$ |
The graph of the reference function is as follows (the $x$-axis is scaled down by a factor of $1000$):
### Testing
The sample interactor is provided below:
```cpp
#include
using namespace std;
vector solve(int n, int sid);
int _a[100005],_c;
int query(int i, int j, int k) {
return _c++, abs(_a[i]-_a[j])+abs(_a[j]-_a[k]);
}
int main() {
int n,sid;
cin>>n>>sid;
for(int i=1; i>_a[i];
vector tmp=solve(n,sid);
cout