85分
这本质上是一个拓扑排序，每次拿出一整行/一整列完全相同的，然后把这一行/这一列从矩阵里面删掉。
倒着输出这个顺序就是答案。
一个简单的维护的方法是对于每一行，每一列开一个multiset，一旦这个multiset首尾一样了就说明内部元素全一样了，非常好写，但是非常慢。
#include <bits/stdc++.h>
#define ll long long
#define maxn 1005
#define mod 998244353
using namespace std;
int n;
int col[maxn][maxn],ok[maxn+maxn];
multiset<int> vis[maxn+maxn];
basic_string<pair<int,int>> ans;
void del1(int i)
{
for (int j=1;j<=n;j++)
if (col[i][j]!=-1 && !ok[j+n])
{
vis[j+n].erase(vis[j+n].find(col[i][j]));
col[i][j]=-1;
}
return;
}
void del2(int j)
{
for (int i=1;i<=n;i++)
if (col[i][j]!=-1 && !ok[i])
{
vis[i].erase(vis[i].find(col[i][j]));
col[i][j]=-1;
}
return;
}
int main()
{
cin>>n;
for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) cin>>col[i][j];
for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) vis[i].insert(col[i][j]),vis[j+n].insert(col[i][j]);
int cnt=0;
while (cnt!=n+n)
{
for (int i=1;i<=2*n;i++)
if (!ok[i] && (vis[i].empty() || (*vis[i].begin()==*(--vis[i].end())) ) )
{
cnt++;
ok[i]=1;
if (vis[i].empty()) continue;
ans+=make_pair(i,*vis[i].begin());
if (i<=n) del1(i); else del2(i-n);
}
}
reverse(ans.begin(),ans.end());
cnt=0;
for (auto tt:ans) if (tt.second!=0) cnt++;
cout<<cnt<<endl;
for (auto tt:ans) if (tt.second!=0) cout<<tt.first<<" "<<tt.second<<endl;
}
100分
我们需要一个线性做法，瓶颈主要是如何判断一行/一列已经彻底只剩下同一种元素了。
我们可以给所有颜色赋予一个以内的权值，然后用一行，一列的异或值是否等于（偶数个元素）或者是等于第一个元素（奇数个元素）来判断这一行/一列是否已经彻底被染完毕了。
至于维护每一行/每一列第一个没被删除的元素，我们可以直接在每一行，每一列维护一个指针即可。
如果你直接这么写，你将挂掉30分。
原因是，还有这样一种小概率情况，一行剩下的元素有，虽然异或起来就是，但实际上这里面有一些元素出现了偶数次。
显而易见的是，这样的概率非常小（至少是不到1/2）的，所以我们可以在每次选出一行/一列的时候，暴力一下这一行/一列是否全是一样的元素，如果是，则继续进行。
那么，复杂度就是的线性。
#include <bits/stdc++.h>
#define ll long long
#define maxn 3005
#define mod 998244353
using namespace std;
mt19937 rnd(time(NULL)^clock());
ll rad(int x,int y){
return rnd()%(y-x+1)+x;
}
int n;
ll col[maxn][maxn],v[maxn][maxn],ok[maxn+maxn];
int hang[maxn],lie[maxn]; //存这一行，这一列，还剩哪个位置
ll XOR[maxn+maxn];
ll id1[1<<14],id2[1<<14];
map<ll,int> ID;
basic_string<pair<int,int>> ans;
void del1(int i) //删除一行
{
for (int j=1;j<=n;j++)
if (v[i][j]!=-1)
{
XOR[j+n]^=v[i][j]; v[i][j]=-1;
}
return;
}
void del2(int j) //删除一列
{
for (int i=1;i<=n;i++)
if (v[i][j]!=-1)
{
XOR[i]^=v[i][j]; v[i][j]=-1;
}
return;
}
int main()
{
srand(time(0));
cin>>n;
for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) cin>>col[i][j];
for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) assert(col[i][j]>=0 && col[i][j]<=2*n);
//每一个hash值对应的实际颜色
for (int i=0;i<=2*n;i++) {id1[i]=rad(0,1<<29),id2[i]=rad(0,1<<29); ID[id1[i]|(id2[i]<<30ll)]=i;}
for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) v[i][j]=id1[col[i][j]]|(id2[col[i][j]]<<30ll);
for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) assert(v[i][j]!=-1);
for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) XOR[i]^=v[i][j],XOR[j+n]^=v[i][j];
for (int i=1;i<=n+n;i++) hang[i]=lie[i]=1; //当前都是第一个位置开始的
int cnt=0;
while (cnt<n+n)
{
for (int i=1;i<=n+n;i++)
if (!ok[i])
{
if (i<=n)
{
while (hang[i]<=n && v[i][hang[i]]==-1) hang[i]++;
if (hang[i]==n+1)
{
ok[i]=1; cnt++;
continue;
}
if (XOR[i]==0 || XOR[i]==v[i][hang[i]])
{
ll zd=-1,zx=1ll<<62;
for (int j=1;j<=n;j++)
if (v[i][j]!=-1)
{
zd=max(zd,v[i][j]);
zx=min(zx,v[i][j]);
if (zd!=zx) break;
}
if (zd!=zx) continue;
ok[i]=1; cnt++;
ans+=make_pair(i,ID[v[i][hang[i]]]);
if (ID[v[i][hang[i]]]!=0) del1(i);
}
}
else
{
while (lie[i-n]<=n && v[lie[i-n]][i-n]==-1) lie[i-n]++;
if (lie[i-n]==n+1)
{
ok[i]=1; cnt++;
continue;
}
if (XOR[i]==0 || XOR[i]==v[lie[i-n]][i-n])
{
ll zd=-1,zx=1ll<<62;
for (int x=1;x<=n;x++)
if (v[x][i-n]!=-1)
{
zd=max(zd,v[x][i-n]);
zx=min(zx,v[x][i-n]);
if (zd!=zx) break;
}
if (zd!=zx) continue;
ok[i]=1; cnt++;
ans+=make_pair(i,ID[v[lie[i-n]][i-n]]);
if (ID[v[lie[i-n]][i-n]]!=0) del2(i-n);
}
}
}
}
reverse(ans.begin(),ans.end());
cnt=0;
for (auto tt:ans) if (tt.second!=0) cnt++;
cout<<cnt<<endl;
for (auto tt:ans) if (tt.second!=0) cout<<tt.first<<" "<<tt.second<<endl;
}