猜一猜2【NOIP2024模拟赛T2】

75 分做法

快排居然能拿到 75 分

#include <bits/stdc++.h>
using namespace std;
int n, k, ans;
int a[1123456];
bool ask(int x, int y)
{
    cout << "1 " << x << " " << y << endl;
    int res;
    cin >> res;
    return 1 - res; // < 返回 true > 返回 false
}
void doSwap(int x, int y)
{
    cout << "2 " << x << " " << y << endl;
}
// 找到 a[l]~a[r] 的第 k 小（存入 ans）
void quick_sort(int l, int r)
{
    if (l >= r)
        return;
    // 1. 划分左右
    int pl, pr;
    pl = l;
    pr = r;
    while (pl < pr)
    {
        while (pl < pr && ask(pl, pr))
            pr--;
        if (pl != pr)
        {
            doSwap(pl, pr);
            pl++;
        }
        while (pl < pr && ask(pl, pr))
            pl++;
        if (pl != pr)
        {
            doSwap(pl, pr);
            pr--;
        }
    }
    quick_sort(l, pl - 1);
    quick_sort(pl + 1, r);
}
int main()
{
    cin >> n;
    quick_sort(1, n);
    cout << "3" << endl;
    return 0;
}

满分做法

先用归并排序，找到每个数最终应该被交换到哪儿，然后再来一口气 $n-1$ 次交换完成排序。

#include <bits/stdc++.h>
using namespace std;
bool xlty(int x, int y)
{
    cout << "1 " << x << " " << y << endl;
    int res;
    cin >> res;
    return 1 - res; // < 返回 true >= 返回 false
}
void doSwap(int x, int y)
{
    cout << "2 " << x << " " << y << endl;
}
int n;
int a[1123456];
int t[1123456];
void mergeSort(int l, int r)
{
    if (l >= r)
        return;
    int mid = (l + r) / 2;
    mergeSort(l, mid);
    mergeSort(mid + 1, r);
    int pl = l, pr = mid + 1, pt = l;
    while (pl <= mid && pr <= r)
    {
        if (xlty(a[pl], a[pr]))
            t[pt++] = a[pl++];
        else
            t[pt++] = a[pr++];
    }
    while (pl <= mid)
        t[pt++] = a[pl++];
    while (pr <= r)
        t[pt++] = a[pr++];
    for (int i = l; i <= r; i++)
        a[i] = t[i];
}
// a[1~n] 是最终这些数希望达成的顺序
// 记录当前数的顺序
int now[1123456];
// 记录每个数当前在哪儿
int pos[1123456];
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        a[i] = i;
    mergeSort(1, n);
    for (int i = 1; i <= n; i++)
    {
        pos[i] = i;
        now[i] = i;
    }
    // 每个位置把正确的数交换过来
    for (int i = 1; i <= n; i++)
    {
        // 第 i 个位置需要是 a[i]
        if (now[i] != a[i])
        {
            doSwap(i, pos[a[i]]);
            // i         ~ now[i]
            // pos[a[i]] ~ a[i]
            int posX = i, x = now[i];
            int posY = pos[a[i]], y = a[i];
            swap(pos[x], pos[y]);
            swap(now[posX], now[posY]);
        }
    }
    cout << "3" << endl;
    return 0;
}

手动交互器

这个代码把你要测试的排列输进去，就可以两个程序完成手动交互了。

#include <bits/stdc++.h>
using namespace std;
int n, T;
int a[5005];
int rnk[5005];
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    int op, x, y;
    while (1)
    {
        cin >> op;
        if (op == 3)
            break;
        if (op == 1)
        {
            cin >> x >> y;
            if (a[x] < a[y])
                cout << 0 << "\n";
            else
                cout << 1 << "\n";
        }
        if (op == 2)
        {
            cin >> x >> y;
            swap(a[x], a[y]);
            for (int i = 1; i <= n; i++)
                cout << a[i] << " ";
            cout << "\n";
        }
    }
    for (int i = 1; i <= n; i++)
        cout << a[i] << " ";
    cout << "\n";
    return 0;
}