Subtask 1
直接每对 \((i,j)\) 均询问一次，然后找出比其他数都大的一个即可。
Subtask 2
不难想到每次请求把候选点集合二等分并对应连边，每条边必然排除一个数。于是每次请求排除一半候选点。可以做到 \(t=20,s=10^6\)，期望得分 \(11\)。
题目要求 \(t\le 8,s\le 1099944\)。我们需要用查询次数换请求次数。\(1099944\) 这样的奇怪限制启发我们 dp。设 \(f_{k,i}\) 为用 \(k\) 次请求，把 \(i\) 个候选点缩减到 \(1\) 个的最少查询次数，答案即为 \(f_{8,N}\)。转移为：
其中 \(w(j,i)\) 为一次请求把 \(i\) 个候选点缩减到 \(j\) 个的最小查询次数。现在问题变成如何计算 \(w\)。
对于每次请求，我们不妨把查询视为无向图 \(G\) 的边。那么交互库把图定向成 DAG（大指向小），入度不为 \(0\) 的点一定会被排除，我们只保留入度为 \(0\) 的点。
因此在一次请求中留下来的点集中任意两点间无连边，即点集为 \(G\) 的独立集。反过来，任意独立集都能取到：将该独立集排在拓扑序最前面，然后按拓扑序大小关系定向即可给出构造。
因此，如果我们希望一次请求后最多剩下 \(j\) 个候选点，必须保证
其中 \(\alpha(G)\) 是 \(G\) 的最大独立集大小。因此 \(w(j,i)\) 就转化为有 \(i\) 个点且满足 \(\alpha(G)\le j\) 的图 \(G\) 的最小边数。
手模小样例，发现一个比较优秀的构造：把 \(i\) 个点平均分成 \(j\) 组，每组连成完全图，总边数为
事实上，可以证明这是最优构造：
注意到，\(G\) 的独立集和补图 \(\overline{G}\) 中的团一一对应。因此
\[\alpha(G)\le j\Longleftrightarrow K_{j+1}\notin\overline{G} \]而 \(G\) 的边数最少等价于 \(\overline{G}\) 的边数最多。
这正是图兰定理：
在所有 \(i\) 个点且不包含 \(K_{j+1}\) 的图中，边数最多的图是具有 \(i\) 个点的完全 \(j\) 分图（即上面构造的图）。
现在还有一个问题：朴素 dp 是 \(O(tn^2)\) 的，会 T。暴力枚举发现 \(w\) 满足四边形不等式。这一点可以证明：
往证 \(\forall j<i\) 有
\[w(j,i)+w(j+1,i+1)\le w(j+1,i)+w(j,i+1) \]移项，得
\[w(j+1,i+1)-w(j+1,i)\le w(j,i+1)-w(j,i) \]而
\[w(j,i+1)-w(j,i)\le \binom{\left\lfloor i/j\right\rfloor+1}{2}->\binom{\left\lfloor i/j\right\rfloor}{2} \]代入原式，得
\[\binom{\left\lfloor i/(j+1)\right\rfloor+1}{2}-\binom{\left\lfloor >i/(j+1)\right\rfloor}{2} \le \binom{\left\lfloor i/j\right\rfloor+1}{2}-\binom{\left\lfloor >i/j\right\rfloor}{2} \]即
\[\left\lfloor i/(j+1)\right\rfloor\le \left\lfloor i/j\right\rfloor \]证毕。
于是决策单调性成立，可以用分治算法优化到 \(O(tn\log n)\)，发现 \(f_{8,N}\) 的值恰好满足限制，从而通过本题。
Code
#include "richest.h"
#include <vector>
#include <bitset>
#define rep(i,a,b) for(int i(a);i<b;++i)
#define rept(i,a,b) for(int i(a);i<=b;++i)
#define eb emplace_back
#define ll long long
#define il inline
using namespace std;
namespace{constexpr ll INF=1e16;int N,T,S;bool INITED;
}
namespace Case1{constexpr int MAXN=1000;bitset<MAXN> mk;vector<int> A,B,C;int solve(){if(!INITED){A.reserve(499500);B.reserve(499500);C.reserve(499500);INITED=true;}mk.reset();A.clear(),B.clear();rep(i,0,N-1) rep(j,i+1,N) A.eb(i),B.eb(j);C=ask(A,B);rep(i,0,499500) mk.set(C[i]==A[i]?B[i]:A[i]);rep(i,0,N) if(!mk[i]) return i;return 0;}
}
namespace Case2{constexpr int MAXN=1e6+1;ll f[9][MAXN];int g[9][MAXN];bitset<MAXN> mk;vector<int> A,B,C,D;il ll comb(ll x){return x*(x-1)/2;}il ll w(int m,int n){int a=n/m,b=n%m;return (m-b)*comb(a)+b*comb(a+1);}void calc(int k,int l,int r,int opt_l,int opt_r){int i=l+r>>1;g[k][i]=opt_l;rept(j,opt_l,min(opt_r,i-1)){if(f[k-1][j]+w(j,i)<f[k][i]){f[k][i]=f[k-1][j]+w(j,i);g[k][i]=j;}}if(l<i) calc(k,l,i-1,opt_l,g[k][i]);if(r>i) calc(k,i+1,r,g[k][i],opt_r);}int solve(){mk.reset();if(!INITED){ // 仅在初始时运行一次dpfill(f[0]+2,f[0]+N+1,INF);rept(k,1,8){fill(f[k]+1,f[k]+N+1,INF);calc(k,1,N,1,N);}A.reserve(f[8][N]),B.reserve(f[8][N]);C.reserve(f[8][N]),D.reserve(f[8][N]);INITED=true;}int k=8,n=N;while(n>1){int m=g[k][n];int len=w(m,n),a=n/m,b=n%m,p=0;A.clear(),B.clear(),D.clear();rep(_,0,m-b){while(D.size()<a){if(!mk[p]) D.eb(p);++p;}rep(i,0,D.size()-1){rep(j,i+1,D.size()){A.eb(D[i]),B.eb(D[j]);}}D.clear();}rep(_,0,b){while(D.size()<a+1){if(!mk[p]) D.eb(p);++p;}rep(i,0,D.size()-1){rep(j,i+1,D.size()){A.eb(D[i]),B.eb(D[j]);}}D.clear();}C=ask(A,B);rep(i,0,len){int u=C[i]==A[i]?B[i]:A[i];if(!mk[u]) mk.set(u),--n;}--k;}rep(i,0,N) if(!mk[i]) return i;return 0;}
}
int richest(int _N,int _T,int _S){N=_N,T=_T,S=_S;return N==1000?Case1::solve():Case2::solve();
}