题目大意
交互题。
交互库在开始时会生成一个长为n的排列p。你在开始时仅知道排列的长度n,你需要在进行不超过\left\lfloor\dfrac{3n}{2}\right\rfloor+30次询问后输出这个排列。
你可以进行两种类型的提问:
? 1 i j x
返回max(min(x,pi),min(x+1,pj))? 2 i j x
返回min(max(x,pi),max(x+1,pj))
解题思路
代码实现
#include <bits/stdc++.h>
using namespace std;
int ask1(int i, int j, int p) {
cout << "? 1 " << i << ' ' << j << ' ' << p << endl;
int ret;
cin >> ret;
return ret;
}
int ask2(int i, int j, int p) {
cout << "? 2 " << i << ' ' << j << ' ' << p << endl;
int ret;
cin >> ret;
return ret;
}
int p[10005];
bool vis[10005];
int main() {
ios::sync_with_stdio(false);
int _;
cin >> _;
while (_--) {
int n;
cin >> n;
for (register int i = 1; i <= n; i++) vis[i] = false;
for (register int i = 1; i < n; i += 2) {
int ret = ask1(i, i + 1, n - 1);
p[i] = (ret == n - 1 && ask2(i, i + 1, n - 1) == n) ? n : ret;
ret = ask2(i, i + 1, 1);
p[i + 1] = (ret == 2 && ask1(i, i + 1, 1) == 1) ? 1 : ret;
if (ask1(i, i + 1, p[i + 1]) == p[i + 1] + 1) swap(p[i], p[i + 1]);
vis[p[i]] = vis[p[i + 1]] = true;
}
if (n & 1)
for (register int i = 1; i <= n; i++)
if (!vis[i]) p[n] = i;
cout << '!';
for (register int i = 1; i <= n; i++) cout << ' ' << p[i];
cout << endl;
}
return 0;
}
0 条评论