记录编号	596134	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2020]移球游戏	最终得分	100
用户昵称	小金	是否通过	通过
代码语言	C++	运行时间	0.890 s
提交时间	2024-10-22 17:30:50	内存使用	5.36 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=60,M=410,K=820010;
int a[N][M],top[N],n,m,ans[K][2],tot;
bool flag[N];
void pour(int x,int y) 
{
	tot++;
	ans[tot][0]=x;
	ans[tot][1]=y;
	top[y]++;
	a[y][top[y]]=a[x][top[x]];
	top[x]--;
}
void solve(int l,int r)
{
	if(l==r) return;
	int mid=(l+r)>>1;
	memset(flag,0,sizeof(flag));
	for(int i=l;i<=mid;i++)
	{
		for(int j=mid+1;j<=r;j++)
		{
			if(flag[i]||flag[j]) continue;
			int s=0;
			for(int k=1;k<=m;k++) s+=(a[i][k]<=mid);
			for(int k=1;k<=m;k++) s+=(a[j][k]<=mid);
			if(s>=m) 
			{
				s=0;
				for(int k=1;k<=m;k++) s+=(a[i][k]<=mid);
				for(int k=1;k<=s;k++) pour(j,n+1);
				while(top[i])
				{
					if(a[i][top[i]]<=mid) pour(i,j);
					else pour(i,n+1);
				} 
				for(int k=1;k<=s;k++) pour(j,i);
				for(int k=1;k<=m-s;k++) pour(n+1,i);
				for(int k=1;k<=m-s;k++) pour(j,n+1);
				for(int k=1;k<=m-s;k++) pour(i,j);
				while(top[n+1]) 
				{
					if(top[i]==m||a[n+1][top[n+1]]>mid) pour(n+1,j);
					else pour(n+1,i); 
				}
				flag[i]=1;
			}
			else 
			{
				s=0;
				for(int k=1;k<=m;k++) s+=(a[j][k]>mid);
				for(int k=1;k<=s;k++) pour(i,n+1); 
				while(top[j])
				{
					if(a[j][top[j]]>mid) pour(j,i);
					else pour(j,n+1); 
				} 
				for(int k=1;k<=s;k++) pour(i,j);
				for(int k=1;k<=m-s;k++) pour(n+1,j);
				for(int k=1;k<=m-s;k++) pour(i,n+1); 
				for(int k=1;k<=m-s;k++) pour(j,i); 
				while(top[n+1]) 
				{
					if(top[j]==m || a[n+1][top[n+1]]<=mid) pour(n+1,i);
					else pour(n+1,j); 
				}
				flag[j]=1;
			}
		}
	}	
	solve(l,mid);
	solve(mid+1,r);
}
int main()
{
	freopen("2020ball.in","r",stdin);
    freopen("2020ball.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		for(int j=1,x;j<=m;j++)
		{
			scanf("%d",&x);
			top[i]++;
			a[i][top[i]]=x;
		}
	} 	
	solve(1,n);
	printf("%d\n",tot);
	for(int i=1;i<=tot;i++)
	{
		printf("%d %d\n",ans[i][0],ans[i][1]);
	} 
	return 0;
}