世纪难题。
首先我们考虑先固定 \(x\)，比如让 \(x = a_1\)（重复问 \(1\) 直到回答为 =），那么此时我们可以知道任意一个 \(a_i\) 和 \(a_1\) 的大小关系（问一次 \(i\) 再问一次 \(1\)），并且可以知道 \(a_i\) 的具体值。
那么剩下的数被分成了两个集合，一个 \(< a_1\) 一个 \(> a_1\)。发现我们可以对这两个集合递归地做上面的过程。递归时传需要求的位置集合和值域 \([l, r]\) 即可。
问题在于询问次数没有保障。考虑每次递归时从当前集合中随机一个数作为分界点。期望询问次数 \(O(n \log n)\)。\(40n\) 的次数限制很宽松所以能过。
code
// Problem: E. ace5 and Task Order
// Contest: Codeforces - Codeforces Round 922 (Div. 2)
// URL: https://codeforces.com/contest/1918/problem/E
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 2020;
int n, a[maxn];
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
inline int ask(int i) {
printf("? %d\n", i);
fflush(stdout);
char op[9];
scanf("%s", op);
if (op[0] == '-') {
exit(0);
}
return op[0] == '>' ? 1 : (op[0] == '<' ? -1 : 0);
}
void dfs(int l, int r, vector<int> S) {
if (S.empty()) {
return;
}
if (l == r) {
a[S[0]] = l;
return;
}
int p = S[rnd() % (int)S.size()];
while (1) {
if (ask(p) == 0) {
break;
}
}
vector<int> L, R;
for (int i : S) {
if (i == p) {
continue;
}
int t = ask(i);
if (t == -1) {
L.pb(i);
} else {
R.pb(i);
}
ask(p);
}
int k = l + (int)L.size();
a[p] = k;
dfs(l, k - 1, L);
dfs(k + 1, r, R);
}
void solve() {
scanf("%d", &n);
vector<int> S;
for (int i = 1; i <= n; ++i) {
S.pb(i);
}
dfs(1, n, S);
printf("! ");
for (int i = 1; i <= n; ++i) {
printf("%d ", a[i]);
}
putchar('\n');
fflush(stdout);
}
int main() {
int T = 1;
scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}