题目背景

猜猜我是谁？

题目描述

本题仅允许使用 C++ 语言提交。

小 Q 有一个长度为 $n$ 的隐藏排列 $p$，你要把它猜出来。

你可以问他两个位置上较大的那个值是多少，你也可以问他一个答案是否正确，他会诚实的回答你。

实现细节

你需要在代码开头加入如下代码：

#include<vector>
int _max(int x,int y);
bool _ask(std::vector<int> a);

你要实现以下函数：

std::vector<int> Guess(int n)

• 保证在每个测试点交互库恰好调用 $50$ 次该函数，且在一个测试点内 $n$ 的值相同。
• $n$ 表示排列 $p$ 的长度。
• 该函数应该返回一个数组 Ans，下标从 $0$ 开始，表示你猜测的排列 $p$。

上述函数可以调用如下两个函数：

int _max(int x,int y)

• $x,y$ 表示你询问的位置，你需要保证 $1\leq x,y\leq n,x\not=y$。
• 该函数会返回 $\max(p_x,p_y)$。
• 对每一次 Guess 函数的调用，该函数最多被调用 $10^5$ 次。

bool _ask(std::vector<int> a)

• 数组 $a$ 表示你询问的排列，下标从 $0$ 开始，你需要保证 $a$ 是一个 $1-n$ 的排列。
• 若你的排列 $a$ 与答案排列 $p$ 相同，该函数会返回 True，否则返回 False。
• 对每一次 Guess 函数的调用，该函数最多被调用 $10$ 次。

本题的目的是使得 _ask 函数和 _max 函数的总调用次数尽量少。每一个测试点都有一个满分线 $MAX$，评测程序根据 $MAX$ 和你的总调用次数来评分。

评测程序的行为是非自适应的。这意味着在每次调用 Guess 前，排列 $p$ 是固定的。

输入格式

第一行两个整数 $n,T$，表示排列长度和 Guess 函数被调用的次数，保证 $1\leq n\leq10^4$，在数据中，保证 $T=50$（在样例中不保证）。

接下来 $T$ 行，每行有 $n$ 个整数，表示每次调用中隐藏的排列 $p$，保证每行的 $n$ 个整数组成一个 $1-n$ 排列。

输出格式

共 $T$ 行，每行输出该次测试的结果。

若你的所有调用合法，并且返回的排列正确，则输出 Y 与你的函数调用两个函数的次数。

否则输出一个字符 N。

3 1
1 3 2

Y 1 1

提示

【样例解释】

对于样例 $1$，可能的调用顺序： | 选手程序 | 交互库 | 说明 | | :-----------: | :-----------: |:-----------: | | | 获得排列，如 $[1,3,2]$ | | | | 调用 Guess(3) | 开始测试 | | 调用_max(1,2) | 返回 $3$ | $\max(p_1,p_2)=\max(1,3)=3$ | | 调用_ask([1,3,2]) | 返回 True | 猜测排列与真实排列相同 | | 运行结束并返回 $[1,3,2]$ | 向屏幕打印交互结果、_max和_ask的调用次数：Y 1 1 | 交互结束，结果正确，次数小于满分标准 |

【数据范围】

对于所有数据保证：$p$ 为 $1-n$ 的排列，$1\leq n\leq 10^4$。

本题共有 $50$ 组测试点，每个测试点的分值均为 $100$ 分，得分为所有测试点得分的平均数，数据范围如下：

设 $c$ 为测试点编号，

• 对于测试点 $1-5$：$n=c$
• 对于测试点 $6-10$：$n=2c$
• 对于测试点 $11-20$：$n=5c$
• 对于测试点 $21-30$：$n=50c$
• 对于测试点 $31-50$：$n=200c$

【评分方式】

注意：

• 选手不应通过非法方式获取交互库里的信息，如试图读取排列 $p$ 的值，或直接与标准输入、输出流进行交互。此类行为将被视为作弊。

在每次 Guess 函数的调用中，程序调用 _max 次数不得超过 $10^5$ 次，_ask 次数不得超过 $10$ 次，否则将会获得 $0$ 分。

若你调用 _max 或 _ask 的参数不符合题目要求，或者 Guess 的返回值不符合题目要求，将会获得 $0$ 分并获得 Wrong function using 的返回。

若你的返回值与正确排列 $p$ 不同，将会获得 $0$ 分并获得 Wrong answer permutation 的返回。

我们设你调用 _max 和 _ask 的总次数在 $T$ 次 Guess 函数调用中的最大值为 $w$，满分标准（满分标准见附件）为 $MAX$，若你返回正确排列，评分方式如下： | $w$ | 分数系数 | | :----------: | :----------: | | $[0,MAX]$ | $1$ | | $(MAX,2n)$ | $1-0.8(\log_{2n-MAX}w-MAX)$ | | $[2n,10^5+10]$ | $0.2$ |

【本地测试】

可以在代码最后加入以下示例交互库，按照输入格式测试。

示例交互库并不判断你的函数调用合法性，所以请注意你是否合法调用。

#include<bits/stdc++.h>
using namespace std;
vector<int> Guess(int n);
int __p[10005],__n,__T,__cnt1,__cnt2;
int _max(int x,int y){
	++__cnt1;
	return max(__p[x],__p[y]);
}
bool _ask(vector<int> a){
	++__cnt2;
	for(int i=0;i<__n;i++) if(a[i]!=__p[i+1]) return 0;
	return 1;
}
int main(){
	cin>>__n>>__T;
	for(int i=1;i<=__T;i++){
		for(int j=1;j<=__n;j++) scanf("%d",&__p[j]);
		__cnt1=__cnt2=0;
		vector<int> ans=Guess(__n);
		printf("%c %d %d\n","NY"[_ask(ans)],__cnt1,__cnt2);
	}
	return 0;
}

【附件】

在本题附件中，.in 文件中为对应测试点 $n$ 的值， .out 文件为对应的满分标准。

例如：data1.in 中是 1，data1.out 中是 0。