{"problem":{"name":"[语言月赛 202210] 军训","description":{"content":"某 E 刚结束军训，军训教官将所有同学排成了 $n$ 行 $m$ 列。 教官组织同学们进行分列式练习，同学们将按行为单位进行练习。第 $i$ 行第 $j$ 名同学摆臂的高度为 $a_{i,j}$，踢腿的高度为 $b_{i,j}$。 教官认为，每一行同学的不整齐度为摆臂高度方差与踢腿高度方差之和。形式化的，第 $i$ 行同学的不整齐度为  $$ \\dfrac{1}{m} \\times \\sum\\","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":131072},"difficulty":{"LuoguStyle":"P3"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGB3675"},"statements":[{"statement_type":"Markdown","content":"某 E 刚结束军训，军训教官将所有同学排成了 $n$ 行 $m$ 列。\n\n教官组织同学们进行分列式练习，同学们将按行为单位进行练习。第 $i$ 行第 $j$ 名同学摆臂的高度为 $a_{i,j}$，踢腿的高度为 $b_{i,j}$。\n\n教官认为，每一行同学的不整齐度为摆臂高度方差与踢腿高度方差之和。形式化的，第 $i$ 行同学的不整齐度为 \n$$\n\\dfrac{1}{m} \\times \\sum\\limits_{j=1}^{m}{\\Bigg(a_{i,j}-\\dfrac{\\sum\\limits_{k=1}^{m}{a_{i,k}}}{m}\\Bigg)^2} + \\dfrac{1}{m} \\times \\sum\\limits_{j=1}^{m}{\\Bigg(b_{i,j}-\\dfrac{\\sum\\limits_{k=1}^{m}{b_{i,k}}}{m}\\Bigg)^2}\n$$\n\n其中，$\\sum\\limits_{j=1}^m{a_{i,j}}$ 代表 $a_{i,1}+a_{i,2}+a_{i,3}+\\cdots+a_{i,m}$。\n\n教官希望对若干行进行位置上的对调，使得最终排出的方阵中，从第 $1$ 行至第 $n$ 行不整齐度依次递增。若有两行不整齐度相同，可以任意安排其顺序。\n\n请你编写程序，给出一种交换方案。请注意，每一步交换是即刻完成的。\n\n例如，给出如下的交换方案：\n\n第一步，交换第 $1$ 行和第 $2$ 行；第二步，交换第 $2$ 行和第 $3$ 行。\n\n初始：\n\n| 当前行数 | 初始行号 |\n|:---: | :---: |\n| $1$ | $1$ |\n| $2$ | $2$ |\n| $3$ | $3$ |\n\n第一步完成后：\n\n| 当前行数 | 初始行号 |\n|:---: | :---: |\n| $1$ | $2$ |\n| $2$ | $1$ |\n| $3$ | $3$ |\n\n第二步完成后：\n\n| 当前行数 | 初始行号 |\n|:---: | :---: |\n| $1$ | $2$ |\n| $2$ | $3$ |\n| $3$ | $1$ |\n\n**提示：例如，将第 $1$ 行与第 $3$ 行交换后，原第 $1$ 行将被叫做第 $3$ 行，而不是仍被叫做第 $1$ 行。**\n\n**具体解释可参照样例 #2 解释。**\n\n## Input\n\n输入共 $2n+1$ 行。\n\n输入的第一行为两个整数 $m,n$，分别代表列数和行数。\n\n接下来 $n$ 行，每行 $m$ 个整数，第 $i$ 行第 $j$ 个代表 $a_{i,j}$。\n\n接下来 $n$ 行，每行 $m$ 个整数，第 $i$ 行第 $j$ 个代表 $b_{i,j}$。\n\n## Output\n\n输出若干行。\n\n输出的第一行为一个整数 $K$，代表你交换方案中交换的次数。\n\n接下来 $K$ 行，每行输出两个整数 $x,y$，代表将第 $x$ 行与第 $y$ 行的同学进行交换。\n\n**注意：$K$ 应当不超过 $n^2$**。\n\n[samples]\n\n## Note\n\n### 样例 #2 解释\n\n仅考虑摆臂高度，在前两次交换后，阵列变成如下的样子：\n\n$\\begin{matrix} 1: & 2 & 4 & 6 \\\\ 2: & 1 & 2 & 3 \\\\ 3: & 3 & 6 & 9 \\end{matrix}$\n\n此时，原第 $3$ 行现被叫做第 $2$ 行，原第 $2$ 行现被叫做第 $1$ 行。如果我们想要将它们交换，应该输出 `1 2` 而不是 `2 3`。\n\n### 数据规模与约定\n\n对于 $30\\%$ 的数据，所有 $a_{i,j}$ 均相同，$b_{i,j}$ 均相同。  \n\n对于另外 $20\\%$ 的数据，满足 $n\\le 100$，$m\\le 100$。\n\n对于 $100\\%$ 的数据，$1 \\le n,m \\le 1000$，$1 \\le a_{i,j},b_{i,j} \\le 100$。\n\n### Special Judge\n\n本题答案不唯一，将有 Special Judge 对你的答案进行检查，所有合法答案均可以得分。\n\nProblem Assigned by 览遍千秋 | 七海","is_translate":false,"language":"English"}],"meta":{"iden":"LGB3675","tags":["2022","Special Judge","O2优化","排序","构造","语言月赛"],"sample_group":[["3 3\n1 1 1\n1 1 1\n1 1 1\n1 1 1\n1 1 1\n1 1 1","3\n1 2\n1 3\n2 3"],["3 3\n3 6 9\n2 4 6\n1 2 3\n1 1 1\n1 1 1\n1 1 1","3\n1 2\n2 3\n1 2"]],"created_at":"2026-03-03 11:09:25"}}