猜一猜【NOIP2024模拟赛T1】

#include <bits/stdc++.h>
using namespace std;
int n;
void ok(int x, int y)
{
    cout << "2 " << x << " " << y << endl;
    exit(0);
}
int ask(int x, int y)
{
    cout << "1 " << x << " " << y << endl;
    int res;
    cin >> res;
    if (res >= (n + 2) / 3)
        ok(x, y);
    return res;
}
mt19937 rnd(time(0));
vector<int> now, nxt;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        now.push_back(i);
    for (int t = 2; t <= n; t *= 2)
    {
        // 找到两个数的 gcd 是 t
        int pos = -1;
        while (pos == -1)
        {
            int x, y;
            x = y = 1;
            while (x == y)
            {
                x = rnd() % now.size();
                y = rnd() % now.size();
            }
            int res = ask(now[x], now[y]);
            if (res % t == 0)
                pos = now[x];
        }
        // 所有 t 的倍数放入 nxt
        nxt.push_back(pos);
        for (int x : now)
        {
            if (x == pos)
                continue;
            if (ask(pos, x) % t == 0)
            {
                nxt.push_back(x);
            }
        }
        now = nxt;
        nxt.clear();
    }
    return 0;
}