记录编号	610250	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2020]移球游戏	最终得分	100
用户昵称	终焉折枝	是否通过	通过
代码语言	C++	运行时间	1.236 s
提交时间	2025-12-18 22:36:49	内存使用	5.48 MiB

#include<iostream>
using namespace std;

const int MAXN = 55;
const int MAXM = 405;
const int OPTION = 820005;
int a[MAXN][MAXM];
int top[MAXN];
int path[OPTION][2];
int tot = 0;
int n, m;

void Move(int x, int y){
	path[++ tot][0] = x;
	path[tot][1] = y;
	a[y][++ top[y]] = a[x][top[x] --];
}

bool cmp(int x, int y, int ball, int mid){
	if(x < y){
		return ball <= mid;
	}
	return ball > mid;
}

void order(int x, int y, int z, int mid){
	int k = 0;
	for(int i = 1;i <= m;i ++){
		if(cmp(x, y, a[x][i], mid)){
			k ++;
		}
	}
	//空出 k 个位置 便于后面分解 x 柱子的 0 / 1
	for(int i = 1;i <= k;i ++){
		Move(y, z);
	}
	//按 0 / 1 分离
	for(int i = m;i >= 1;i --){
		if(cmp(x, y, a[x][i], mid)){
			Move(x, y);
		}
		else{
			Move(x, z);
		}
	}
	for(int i = 1;i <= k;i ++){
		Move(y, x);
	}
	for(int i = 1;i <= m - k;i ++){
		Move(z, x);
	}
	for(int i = 1;i <= m - k;i ++){
		Move(y, z);
	}
	for(int i = 1;i <= m - k;i ++){
		Move(x, y);
	}
	for(int i = m;i >= 1;i --){
	    // if(top[z] == 0) break;
	    if(top[x] < m && cmp(x, y, a[z][top[z]], mid)){
	        Move(z, x);
	    }
		else{
	        Move(z, y);
	    }
	}
}

void solve(int l, int r){
	if(l == r) return;
	bool flag[MAXN] = {0};
	int mid = (l & r) + ((l ^ r) >> 1);
	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 ++){
				if(a[i][k] <= mid){
					s ++;
				}
			}
			for(int k = 1;k <= m;k ++){
				if(a[j][k] <= mid){
					s ++;
				}
			}
			if(s >= m){
				order(i, j, n + 1, mid);
				flag[i] = 1;
			}
			else{
				order(j, i, n + 1, mid);
				flag[j] = 1;
			}
		}
	}
	solve(l, mid);
	solve(mid + 1, r);
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	for(int i = 1;i <= n;i ++){
		for(int j = 1;j <= m;j ++){
			cin >> a[i][j];
		}
	}
	for(int i = 1;i <= n;i ++){
    	top[i] = m;
	}
	top[n + 1] = 0;
	solve(1, n);
	cout << tot << '\n';
	for(int i = 1;i <= tot;i ++){
		cout << path[i][0] << ' ' << path[i][1] << '\n';
	}

	return 0;
}