#P17767. 「LDOI R2」排列 / Permutation
「LDOI R2」排列 / Permutation
Background
When submitting on Luogu, please add the following line at the beginning of your code:
int query(int i, int j, int k);
Problem Description
The interactor has a hidden -indexed permutation .
You may query pairwise distinct , and the interactor returns .
Two permutations are defined to be equivalent if and only if for any pairwise distinct , .
After finishing the queries, you need to find any permutation equivalent to .
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:
vector<int> solve(int n, int sid);
- The parameter
nis the length of the permutation, andsidis the subtask number (in particular,sidis for samples). - You need to return a
vectorof length , representing the permutation you found. - This function will be called exactly once in a test case.
You may call the following function:
int query(int i, int j, int k);
- You need to ensure , , , .
- This function will return the value of .
Input Format
The sample interactor will read data in the following format.
The first line contains two numbers .
The next line contains numbers representing the sequence .
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 numbers representing the sequence you returned.
4 0
3 2 4 1
2
2 3 1 4
8 0
3 8 4 5 7 1 2 6
114514
3 8 4 5 7 1 2 6
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 | |
|---|---|
The interactor guarantees that when the number of queries is , the time used does not exceed seconds, and the space used does not exceed MB.
Scoring
Let be the number of queries you make.
In Subtask , if and the answer is correct, you get points; otherwise you get .
In Subtask , if the answer is correct, you are scored according to the following table; otherwise you get .
| Range | Score |
|---|---|
| $\left\lfloor 90 \left( \frac{2.4 \times 10^5 - Q}{1.4 \times 10^5} \right)^3 \right\rfloor$ | |
The graph of the reference function is as follows (the -axis is scaled down by a factor of ):

Testing
The sample interactor is provided below:
#include<bits/stdc++.h>
using namespace std;
vector<int> 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<=n; i++) cin>>_a[i];
vector<int> tmp=solve(n,sid);
cout<<_c<<'\n';
for(auto i:tmp) cout<<i<<' ';
cout<<'\n';
return 0;
}
Contestants can use the following command in the directory of this problem to compile an executable (assuming the sample interactor is grader.cpp and your code is perm.cpp):
g++ grader.cpp perm.cpp -o perm -O2
The interactor in the real judging environment may differ from the sample interactor. Your code should not depend on the interactor's implementation.