题目链接

题目大意

交互题。

交互库在开始时会生成一个长为n的排列p。你在开始时仅知道排列的长度n,你需要在进行不超过\left\lfloor\dfrac{3n}{2}\right\rfloor+30次询问后输出这个排列。

你可以进行两种类型的提问:

  1. ? 1 i j x返回max(min(x,pi),min(x+1,pj))
  2. ? 2 i j x返回min(max(x,pi),max(x+1,pj))

解题思路

图片.png

代码实现

#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 条评论

发表评论

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注