挺好玩的交互题。
思路
首先，我们一定需要知道 DAG 中最长路径的起点，这可以通过 \(n\) 次询问来找到。即对于每一个点 \(i\) 满足 \(1\le i\le n\) 我们都去查询从 \(i\) 开始，经过整个 DAG 可以得到的最长路是多少，同时使用一个 vector 记录长度为 \(len\) 的点有哪些。
设查询到的最长路径的长度为 \(maxn\)，最长路径的起点为 \(u\)，那么现在考虑从最长路径为 \(maxn-1\) 点一直查询到最长路径为 \(1\) 的点。在查询时维护一个点集 \(S\) 表示最长路径里的点，一开始 \(S=\{u\}\)，然后在每次查询时都把点集里的点和即将要查询的点 \(v\) 输出，如果得到的结果比只通过点集里的点走出的最长路要长的话，就说明点 \(v\) 在最长路径上，于是也把点 \(v\) 加入点集 \(S\)。在这部分查询中，我们只会遍历 vector 中的元素一遍，也就是只会有 \(n\) 次询问，满足题意。
最后，点集 \(S\) 里的点便是最长路径上的点，将其顺序输出即可。
注意要特判一下 \(maxn\) 为 \(1\) 的情况。
代码
赛时丑陋代码：
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define i128 __int128
#define inf (1ll << 62)
#define PII pair<int, int>
#define pb push_back
#define fi first
#define se second
using namespace std;void solve() {int n;cin >> n;int node, maxn = 0;vector<vector<int>> pos(n + 1);for (int i = 1; i <= n; i++) {cout << "? " << i << " " << n << " ";for (int j = 1; j <= n; j++) cout << j << " ";cout << "\n";cout.flush();int length;cin >> length;if (maxn < length) {maxn = length;node = i;}pos[length].pb(i);}if (maxn == 1) {cout << "! 1 1\n";cout.flush();return;}vector<int> path(maxn);int last = 1;for (int i = maxn - 1; i >= 1; i--) {for (auto j : pos[i]) {cout << "? " << node << " " << maxn - i + 1 << " " << node << " ";for (int k = maxn - 1; k > i; k--) cout << path[k] << " ";cout << j << "\n";cout.flush();int length;cin >> length;if (length > last) path[i] = j;}last++;}cout << "! " << maxn << " " << node << " ";for (int i = maxn - 1; i >= 1; i--) cout << path[i] << " ";cout << "\n";cout.flush();
}int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t = 1;cin >> t;while (t--) {solve();}return 0;
}