33OJ
登录 注册

#P17767. 「LDOI R2」排列 / Permutation

    ID: 20378 远端评测题 2000ms 512MiB 尝试: 0 已通过: 0 显示难度省选/NOI− 上传者: 标签>洛谷原创交互题Special JudgeO2优化洛谷月赛

「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 11-indexed permutation aa.

You may query pairwise distinct i,j,k (1≤i,j,k≤n)i,j,k\ (1\le i,j,k \le n), and the interactor returns ∣ai−aj∣+∣aj−ak∣|a_i-a_j|+|a_j-a_k|.

Two permutations a,ba,b are defined to be equivalent if and only if for any pairwise distinct i,j,k (1≤i,j,k≤n)i,j,k\ (1\le i,j,k \le n), ∣ai−aj∣+∣aj−ak∣=∣bi−bj∣+∣bj−bk∣|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 aa.

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 n is the length of the permutation, and sid is the subtask number (in particular, sid is 00 for samples).
  • You need to return a vector of length nn, representing the permutation bb 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 1≤i,j,k≤n1 \le i,j,k \le n, i≠ji \neq j, i≠ki \neq k, j≠kj \neq k.
  • This function will return the value of ∣ai−aj∣+∣aj−ak∣|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,sidn, \text{sid}.

The next line contains nn numbers representing the sequence aa.

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 nn numbers representing the sequence bb 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 n=n =
11 88
22 8×1048 \times 10^4

The interactor guarantees that when the number of queries is ≤2.4×105\le 2.4 \times 10^5, the time used does not exceed 1.21.2 seconds, and the space used does not exceed 88 MB.

Scoring

Let QQ be the number of queries you make.

In Subtask 11, if Q≤103Q \le 10^3 and the answer is correct, you get 1010 points; otherwise you get 00.

In Subtask 22, if the answer is correct, you are scored according to the following table; otherwise you get 00.

Range Score
Q>2.4×105Q > 2.4 \times 10^5 00
105<Q≤2.4×10510^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≤105Q \le 10^5 9090

The graph of the reference function is as follows (the xx-axis is scaled down by a factor of 10001000):

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.