Just Another Disney Problem
有一个 \(n \leq 1000\) 个点的竞赛图，你可以进行最多 \(10000\) 次询问，每次询问形如：
- 给出 \(u\) 和 \(v\)，交互库返回边 \(u \to v\) 的存在性。
你需要在询问后给出该图的一条哈密顿路径，或报告无解。
关于竞赛图必然存在哈密顿路径的证明：
考虑归纳证明，对于 \(n \leq 2\) 此性质必然成立，不妨设 \(n = n_0\) 时性质成立。
设前 \(n_0\) 个点的哈密顿路径为 \(v_1 \rightarrow v_2 \rightarrow \dots \rightarrow v_{n_0}\)，此时将 \(n_0 + 1\) 加入路径。
有以下两种简单的情况：
-
\(n_0 + 1 \rightarrow v_1\)，此时有 \(n_0 + 1 \rightarrow v_1 \rightarrow v_2 \rightarrow \dots \rightarrow v_{n_0}\)。
-
\(v_{n_0} \rightarrow n_0 + 1\)，此时有 \(v_1 \rightarrow v_2 \rightarrow \dots \rightarrow v_{n_0} \rightarrow n_0 + 1\)。
若上面两种情况不成立，说明必然存在 \(v_1 \rightarrow n_0 + 1\) 和 \(n_0 + 1 \rightarrow v_{n_0}\)。
考虑一个 \(01\) 序列 \(a\)，\(a_i = 0\) 表示 \(v_i \rightarrow n_0 + 1\)，\(a_i = 1\) 表示 \(n_0 + 1 \rightarrow v_i\)。
显然我们有 \(a_1 = 0\)，\(a_{n_0} = 1\)，则必然会有一个 \(i\) 使得 \(a_i = 0\) 且 \(a_{i+1} = 1\)。
则此时有 \(v_1 \rightarrow v_2 \rightarrow \dots \rightarrow v_i \rightarrow n_0 + 1 \rightarrow v_{i+1} \rightarrow v_{i+2} \rightarrow \dots \rightarrow v_{n_0}\)。
考虑直接套上面的做法，显然可以直接二分，做完了，注意常数即可。
//Ad astra per aspera
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<vector>
#include<random>
#include<algorithm>
#include<ctime>
using namespace std;
string qa;
mt19937 rnd(time(0));
int id[1010];
int main(){int n;cin>>n;if(n==1){cout<<"0 1"<<endl;return 0;}for(int i=1;i<=n;i++){id[i]=i;}shuffle(id+1,id+n+1,rnd);cout<<"1 "<<id[1]<<" "<<id[2]<<endl;vector<int> path;cin>>qa;if(qa=="YES"){path.push_back(id[1]);path.push_back(id[2]);}else{path.push_back(id[2]);path.push_back(id[1]);}for(int i=3;i<=n;i++){vector<int> new_path;int l=-1,r=i-1;while(r-l>1){int mid=(l+r)/2;cout<<"1 "<<id[i]<<" "<<path[mid]<<endl;cin>>qa;if(qa=="YES"){r=mid;}else{l=mid;}}for(int j=0;j<=l;j++){new_path.push_back(path[j]);}new_path.push_back(id[i]);for(int j=r;j<=i-2;j++){new_path.push_back(path[j]);}path=new_path;}cout<<"0 ";for(int i=0;i<=n-1;i++){cout<<path[i];if(i<=n-2){cout<<" ";}}cout<<endl;return 0;
}