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

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define fi first
#define in inline
#define se second
#define mp make_pair
#define pb push_back
const int N = 60,M = 410;

ll read(){
	ll x = 0,f = 1;char c = getchar();
	for(;c < '0' || c > '9';c = getchar())if(c == '-')f = -1;
	for(;c >= '0' && c <= '9';c = getchar())x = (x<<1) + (x<<3) + c-'0';
	return x * f;
}


int n,m,p;
int a[N][M],top[N];

vector<pii>ans;
void prin(int x,int y){
	if(x == y)return;
	a[y][++top[y]] = a[x][top[x]],a[x][top[x]--] = 0;
	ans.pb({x,y});
}


bool v[N];
int s1,s2;
void solve(int l,int r){
	if(l == r)return;
	int mid = l + r >> 1;
	for(int i = l;i <= mid;i++){
		int s = 0,mi = n + 1; 
		for(int k = 1;k <= m;k++)if(a[i][k] > mid)mi = min(mi,k),s++;
		if(!s)continue;
		int w = (i == p-1 ? i - 1 : i + 1);
		for(int k = 1;k <= s;k++)prin(w,p);
		for(int k = m;k >= 1;k--)
			if(a[i][k] <= mid)prin(i,p);
			else prin(i,w);
		for(int k = m;k > s;k--)prin(p,i);
		for(int k = 1;k <= s;k++)prin(w,i);
		for(int k = s;k >= 1;k--)prin(p,w);
	}
	for(int i = mid + 1;i <= r;i++){
		int s = 0,mi = n + 1; 
		for(int k = 1;k <= m;k++)if(a[i][k] <= mid)mi = min(mi,k),s++;
		if(!s)continue;
		int w = (i == p-1 ? i - 1 : i + 1);
		for(int k = 1;k <= s;k++)prin(w,p);
		for(int k = m;k >= 1;k--)
			if(a[i][k] > mid)prin(i,p);
			else prin(i,w);
		for(int k = m;k > s;k--)prin(p,i);
		for(int k = 1;k <= s;k++)prin(w,i);
		for(int k = s;k >= 1;k--)prin(p,w);
	}
	for(int i = l;i <= r;i++)v[i] = 0;
	for(int i = l;i <= mid;i++) 
		for(int j = mid+1;j <= r;j++){
			if(v[i] || v[j])continue;
			int s1 = 0,s2 = 0;
			for(int k = m;k >= 1;k--)
				if(a[i][k] > mid)s1++;
				else break;
			for(int k = m;k >= 1;k--)
				if(a[j][k] <= mid)s2++;
				else break;
			if(s1 >= s2){
				for(int k = 1;k <= s2;k++)prin(j,p);
				for(int k = 1;k <= s2;k++)prin(i,j);
				for(int k = 1;k <= s2;k++)prin(p,i);
				int s = 0,mi = n + 1; 
		for(int k = 1;k <= m;k++)if(a[i][k] > mid)mi = min(mi,k),s++;
		if(!s)continue;
		int w = (i == p-1 ? i - 1 : i + 1);
		for(int k = 1;k <= s;k++)prin(w,p);
		for(int k = m;k >= 1;k--)
			if(a[i][k] <= mid)prin(i,p);
			else prin(i,w);
		for(int k = m;k > s;k--)prin(p,i);
		for(int k = 1;k <= s;k++)prin(w,i);
		for(int k = s;k >= 1;k--)prin(p,w);
				v[j] = 1;
			}
			else{
				for(int k = 1;k <= s1;k++)prin(i,p);
				for(int k = 1;k <= s1;k++)prin(j,i);
				for(int k = 1;k <= s1;k++)prin(p,j);
				int s = 0,mi = n + 1; 
		for(int k = 1;k <= m;k++)if(a[j][k] <= mid)mi = min(mi,k),s++;
		if(!s)continue;
		int w = (j == p-1 ? j - 1 : j + 1);
		for(int k = 1;k <= s;k++)prin(w,p);
		for(int k = m;k >= 1;k--)
			if(a[j][k] > mid)prin(j,p);
			else prin(j,w);
		for(int k = m;k > s;k--)prin(p,j);
		for(int k = 1;k <= s;k++)prin(w,j);
		for(int k = s;k >= 1;k--)prin(p,w);
				v[i] = 1;
			}
		}
	solve(l,mid),solve(mid+1,r);
}
int main(){
	freopen("2020ball.in","r",stdin);
	freopen("2020ball.out","w",stdout);
	n = read(),m = read();
	p = n + 1;
	for(int i = 1;i <= n;i++)
		for(int j = 1;j <= m;j++)a[i][j] = read(),top[i] = m;
	solve(1,n);
	printf("%d\n",(int)ans.size());
	for(auto x : ans)printf("%d %d\n",x.fi,x.se);

	return 0;

}