• $\lfloor n\rfloor =n-\varepsilon,\varepsilon\in [0,1)$.

设路标的位置为 $x_1,x_2,\cdots,x_n$，城市的位置为 $y_{1},y_2,\cdots,y_m$。

那么 正确的 $d_{i,j}$ 相当于限制了：

$$\exist \varepsilon_{i,j}\in [0,1):y_j-x_i-\varepsilon_{i,j}=d_{i,j}$$

---

$20\%$ 的限制容易刻画：随机 $\mathcal{O}(1)$ 次必定能取到一个在 最大合法路标集合 的元素 $u$。实际这里常数取 $40$ 比较稳。

现在钦定路标 $u$ 在最大集合中，要找到 此时最大合法路标集合。

考虑判断这东西肯定是行找个参照减一下，列找个参照减一下。这样就把 $x,y$ 消掉了。

行显然是找 $u$ 减：$a_{i,j}=d_{i,j}-d_{u,j}=x_u-x_1-\varepsilon_{i,j}+\varepsilon_{u,j}$

列我们可以找最小值减，设第 $i$ 行的最小值为 $a_{i,w_i}$，则有：

$$b_{i,j}=a_{i,j}-a_{i,w_i}=-\varepsilon_{i,j}+\varepsilon_{u,j}+\varepsilon_{i,w_i}-\varepsilon_{u,w_i}\ge 0$$

---

接下来要找到最大集合 $S$，使得 $\{i\in S,\varepsilon_{i,*}\}$ 的取值互不矛盾，即存在 $\varepsilon_{i,*}$ 的填法满足 $b$ 数组。

首先根据 $\varepsilon_{i,j}\in [0,1)$ 得出 $b_{i,j}<2$，而 $b_{i,j}\in \N\Rightarrow b_{i,j}\in \{0,1\}$。

我们就可以丢弃所有存在 $b_{i,j}>1$ 的行。接下来变形一下：

$$\varepsilon_{i,j}=\varepsilon_{u,j}-\varepsilon_{u,w_i}+\varepsilon_{i,w_i}-b_{i,j}$$

单独考虑第 $i$ 行，存在一个 $\varepsilon_{i,w_i}\in[0,1)$ 使得对所有 $j$ 上式都落在 $[0,1)$ 的 充要条件 是：

$$\text{D}(\{\varepsilon_{u,j}-b_{i,j}\})<1 \\ \text{D}(S)=\max S-\min(S)$$

因为 $b_{i,j}\in\{0,1\}$，把行中的两类列分成 $S_{0/1}=\{j:b_{i,j}=0/1\}$，可以证明上面的条件等价于：

$$\max_{k\in S_0}\varepsilon_{u,k}\;<\;\min_{j\in S_1}\varepsilon_{u,j}$$

也就是说，在某个给定的 $\varepsilon_u$ 大小顺序下，行 $i$ 可行当且仅当所有 $0$ 列都小于所有 $1$ 列。

换句话说，记 $T_i=\{j:b_{i,j}=1\}$，相当于选出最多的 $T_i$ 使得两两之间存在包含关系，否则顺序就矛盾了。

直接 bitset 然后拓扑序遍历一遍，复杂度 $\mathcal{O}(\frac{n^2m}{w})$。

上述结论充分性显然，必要性就是具体构造合法的 $\varepsilon$。这里不赘述，感兴趣可以自己想想。

:::info[$\mathbf{code}$]

#include<bits/stdc++.h>
#define LL long long
#define all(x) x.begin(),x.end()
#define bs basic_string<int>
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
mt19937 rnd(time(0));
const int N=1005,M=205;
int n,m,d[N][M],a[N][M],L[N],pre[N];
bitset<M>f[N];bs ans;
inline bs sol(int u)
{
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) a[i][j]=d[i][j]-d[u][j];
	bs g;int w;
	for(int i=1;i<=n;i++)
	{
		w=*min_element(a[i]+1,a[i]+1+m);
		bool o=1;f[i].reset();
		for(int j=1;j<=m;j++)
		{
			a[i][j]-=w;
			if(a[i][j]>1){o=0;break;}
			f[i][j]=a[i][j];
		}
		if(o) g+=i,L[i]=pre[i]=0;
	}
	sort(all(g),[](int x,int y){return f[x].count()<f[y].count();});
	for(int i=0;i<g.size();i++)
	{
		int x=g[i];
		for(int j=0;j<i;j++)
		{
			int y=g[j];
			if((f[y]&f[x])==f[y]&&L[y]+1>L[x])
				L[x]=L[y]+1,pre[x]=y;
		}
	}w=0;
	for(int i:g) if(L[i]>=L[w]) w=i;
	for(g.clear();w;w=pre[w]) g+=w;return g;
}
int main()
{
	cin.tie(0)->sync_with_stdio(0);cout.tie(0);cin>>n>>m;
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>d[i][j];
	for(int i=1;i<=40;i++)
	{
		int x=rnd()%n+1;bs t=sol(x);
		if(t.size()>ans.size()) ans=t;
	}
	sort(all(ans),[](int x,int y){
		for(int i=1;i<=m;i++) if(d[x][i]^d[y][i]) return d[x][i]>d[y][i];
        return x<y;
	});cout<<ans.size()<<"\n";
	for(int i:ans) cout<<i<<" ";
	return 0;
}

:::