赛时没写完，急急急。

把数分成 $n$ 组，初始每组 $n$ 个数，并且对于每组记录一下这组哪个位置最大，$n$ 次询问。

每轮求出最大的位置是哪个，只要在每组的最大位置里面询问一次就行。

接下来我们得从某一组里面删掉这个最大位置，现在这组不完整了，为了维护出这个结构，我们从其他组拉一些不是最大位置的元素到这组知道凑够 $n$ 个数，再询问一次。这样可以发现确定答案的一个元素 $2$ 个询问就够了。

当剩余元素 $=2n-1$ 时候，再取出最大之后已经没有足够的元素组成一组了，这时候考虑一个性质：每组的最大值一定打赢过至少一场比赛，那么剩下的 $n-1$ 个一定是最小的那几个，直接 $n-1$ 次询问就能确定剩下 $n$ 个最大值的排名。

赛时写对了。

连通就有解。

先从终点开始 dfs 一次整个迷宫回到自己，记录这个串为 $S$。

那么我们试图构造答案为 $rev(S)+T+S$，其中 $T$ 是回文。

现在转化为了已经访问每个点，只要从起点走到终点，把合法转移写出来 bfs 即可。

注意不能从起点开始 dfs，比如：

S111
1000
1T10

如果你开头放了 RRR 就没救了。

5:03 写对了，火大。

$n\le 4$ 随便造。

$n=5,6$ 一看就没救。

玩一下会发现 $n=7$ 没救，$n=8,10$ 有救：

仔细一看：

这样就能加四个点，于是可以获得 $\ge 8$ 的任意偶数的构造。

大力猜测奇数无解，过了。

这种题加点限制就行。

出现次数给他来个不超过 $4$ 次，$4n^2$ 把他紧到取 $k=2^t$ 且大于等于 $n$ 的最小 $k$，然后就是 $k^2$。

考虑构造出第一行之后，后面可以：

00 11 02 13 04
11 22 13 24 10
20 31 22 33 24
31 42 33 44 30
40 01 42 03 44

这样整一下行列分别高低位。方便起见钦定 $a_{0,0}=0$。

发现让 $a$ 的第一行互不相同是不现实的，至少会有数出现两次。这样极端情况下矩阵出现次数最多的就是八次了，不太行。

但是你发现可以考虑一下奇偶性，如果两次出现位置奇偶性不同那就只会出现四次了。

一个简单的构造是类似回文的东西：$0 a b c d \cdots x y \color{red}z x \cdots d c b a 0$ 这样的。

直接搜就能搜出一个合法序列。

赛时写挂了。

答案是 $\max a$。

对于第 $i$ 条线路，找到 $a_x\ge i$ 的所有站建立 W 型线路。

旋转一下坐标系就能保证这个做法一定成功。

qwq

赛时写对了。

24\time 62 > 1000，我们可以给每个数记录一个信息。一个 ull 去掉两位信息位来判断有没有反转大小端（$0$ 位放 $0$，$56$ 位放 $1$）来记录 $62$ bit 信息。

一个数的信息可以看成：他大端读和小端读，他是大的那个还是小的那个。然后就好了。

qwq

赛时写对了。

$2\times{ \infty}$ 的 $1$ 矩阵是合法的，这样可以构造 $\frac p q \le \frac 2 3$。

上界显然是 $\frac 4 5$。因为每个十字至少有一个 $0$。

考虑 $0$ 的连通块：必须构成矩形，否则有 $1$ 相邻两个 $0$ 了。

我们试试只用宽度为 $1$ 的矩形，题目可以转化为用

.111..
10001.
.111..

这样的图形铺满整个平面。

........-------
........|1.1.1|
......---.....---
......|1.0.0.0.1|
......---.....---
........|1.1.1|
........-------
..........|1.1.1|
........---.....---
........|1.0.0.0.1|
........---.....---
..........|1 1 1|
..........---------
............|1.1.1|
..........---.....---
..........|1.0.0.0.1|
..........---.....---
............|1 1 1|
............-------

注意到你可以这样子平铺，并且每一列的矩形长度你可以自己选定。

所以放一列 $1\times x$ 能带来 $x$ 个 $0$ 和 $2x+2$ 个 $1$。

线性组合一下就能组合出 $1$ 密度为 $\frac p q$ 的解了。