竞赛图有一个性质:一定可以找到一条哈密顿路(就是一条 path 经过所有的点恰好一次),那么首先就需要找到这样一条哈密顿路。

有多种方法可以找到这条路径,官方题解给了个归并排序的做法,大致如下图:

归并就是把上面那条和下面那条合并,每次提取两条路径的首节点,问这两个节点的边的方向,如果是图中红边那样黑色指向白色,就把黑色删去放到新的路径内,之后依次这样操作即可。这样,询问的次数大致为 $n\log n$ 次,还是很少的(

然后第二个问题就是找到剩下的关系,显然在路径上加一条有向边形成一个环就可以一下子确定一坨关系。从路径的终点 u 开始往前,依次问 (1,2,3,...,u-1), (1,2,3,...,u-2),... ,用双指针维护即可,一共问 $2n$ 次。

所有的询问搞完之后跑一个传递闭包即可。

这个题真的好玩(

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <string>
#include <vector>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define fillarray(array, value, begin, end) fill((array) + (begin), (array) + (end) + 1, value)
#define fillvector(v, value) fill((v).begin(), (v).end(), value)
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
#define vecfirst (*vec.begin())
#define veclast (*vec.rbegin())
#define vecall(v) (v).begin(), (v).end()
#define vecupsort(v) (sort((v).begin(), (v).end()))
#define vecdownsort(v, type) (sort(vecall(v), greater<type>()))
#define veccmpsort(v, cmp) (sort(vecall(v), cmp))
using namespace std;
const int N = 500050;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
clock_t TIME__START, TIME__END;
void program_end()
{
#ifdef ONLINE
    printf("\n\nTime used:
    system("pause");
#endif
}
int n;
int ask1(int x, int y)
{
    printf("1
    int ret;
    scanf(
    return ret;
}
int ask2(int x, const vector<int> &vec)
{
    printf("2
    for (auto i : vec)
        printf("
    putchar('\n'), Flush;
    int ret;
    scanf(
    return ret;
}
int ans[105][105];
vector<int> e;

vector<int> mergesort(int l, int r)
{
    vector<int> ret;
    if (l == r)
    {
        ret.push_back(l);
        return ret;
    }
    int mid = (l + r) >> 1;
    auto vl = mergesort(l, mid);
    auto vr = mergesort(mid + 1, r);
    int i = 0, j = 0;
    while (i < (int)vl.size() && j < (int)vr.size())
    {
        int r = ask1(vl[i], vr[j]);
        if (r == 1)
        {
            ret.push_back(vl[i]);
            i++;
        }
        else
        {
            ret.push_back(vr[j]);
            j++;
        }
    }
    while (i < (int)vl.size())
        ret.push_back(vl[i]), i++;
    while (j < (int)vr.size())
        ret.push_back(vr[j]), j++;
    return ret;
}

void work1()
{
    e.clear();
    e = mergesort(0, n - 1);
    for (int i = 0; i < (int)e.size(); ++i)
        for (int j = i; j < (int)e.size(); ++j)
            ans[e[i]][e[j]] = 1;
}

inline void solve()
{
    memarray(ans, 0);
    scanf(
    work1();
    int u = n - 1, p = n - 2;
#ifdef VINGYING
    printf("Hamiton: ");
    for (auto i : e)
        cout << i << ' ';
    putchar('\n');
#endif
    while (u >= 0 && p >= 0)
    {
        vector<int> v;
        for (int i = 0; i <= p; ++i)
            v.push_back(e[i]);
        int r = ask2(e[u], v);
        if (r == 1)
            p--;
        if (p < 0)
        {
            ans[e[u]][e[0]] = 1;
            break;
        }
        if (r == 0)
        {
            ans[e[u]][e[p + 1]] = 1;
            u--;
            if (p == u)
                p--;
            if (p < 0)
            {
                ans[e[u]][e[0]] = 1;
                break;
            }
        }
    }
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                ans[i][j] = (ans[i][j] || (ans[i][k] && ans[k][j]));
    printf("3\n");
    for (int i = 0; i < n; ++i, putchar('\n'))
        for (int j = 0; j < n; ++j)
            printf(
    Flush;
    int resp;
    scanf(
    if (resp == -1)
        exit(0);
}

int main()
{
    TIME__START = clock();
    int Test = 1;
    scanf(
    while (Test--)
    {
        solve();
        // if (Test)
        //     putchar('\n');
    }
    TIME__END = clock();
    program_end();
    return 0;
}