[RC-06] Operation Sequence

Luogu
IDLGP8910
Time1000ms
Memory512MB
DifficultyP3
Special JudgeO2优化
给出 $n$,以及一个长度为 $n+1$ 的数组 $[a_1,a_2,\dots,a_{n+1}]$,初始时 $a_i=i\ (1\le i\le n)$,$a_{n+1}=0$。 你只能进行以下一种操作,通过输出特定字符串完成操作: - 输出 `i j` :其中 $i,j$ 为正整数,要求 $1\le i,j\le n+1$,表示把 $a_i$ 赋值为 $a_j$。 请把 $a$ 数组**的前 $n$ 位**向**右**循环移位 $K$ 位;即,在执行完毕你输出的所有操作后,要求 $a$ 数组第 $i\ (1\le i\le K)$ 位等于 $n-K+i$;第 $i\ (K+1\le i\le n)$ 位等于 $i-K$,第 $n+1$ 位任意。你只能进行至多 $T=\lfloor1.5n\rfloor$ 次赋值操作。 如果你进行的操作数多于 $T$ 也可以获得部分分,具体地,设你的操作次数为 $S$: - 如果 $S\le T$,得 $100$ 分。 - 如果 $T<S\le 4T$,得 $50$ 分。 - 如果 $S>4T$,得 $0$ 分。 你在本题的得分是所有测试点中所有数据里得分的最小值。 ## Input 本题单个测试点内有多组数据。 第一行是数据组数 $T$。 对于每组数据: 第一行两个正整数 $n,K$。 ## Output 对于每组数据: 在第一行输出操作数 $k\ (0\le k\le 4T)$。**请注意,不需要最小化 $k$。** 接下来 $k$ 行,每行输出两个正整数 $i,j$,表示一次操作。$(1\le i,j\le n+1)$ [samples] ## Note 所有数据均满足:$1\le T\le 10^4$,$1\le n\le 10^5$,$0\le K\le n-1$。保证同一个测试点中所有 $n$ 的和不超过 $5\times 10^5$。
Samples
Input #1
2
3 0
2 1
Output #1
0
3
3 1
1 2
2 3
API Response (JSON)
{
  "problem": {
    "name": "[RC-06] Operation Sequence",
    "description": {
      "content": "给出 $n$,以及一个长度为 $n+1$ 的数组 $[a_1,a_2,\\dots,a_{n+1}]$,初始时 $a_i=i\\ (1\\le i\\le n)$,$a_{n+1}=0$。 你只能进行以下一种操作,通过输出特定字符串完成操作: - 输出 `i j` :其中 $i,j$ 为正整数,要求 $1\\le i,j\\le n+1$,表示把 $a_i$ 赋值为 $a_j$。 请把 $a$ 数组**",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8910"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给出 $n$,以及一个长度为 $n+1$ 的数组 $[a_1,a_2,\\dots,a_{n+1}]$,初始时 $a_i=i\\ (1\\le i\\le n)$,$a_{n+1}=0$。\n\n你只能进行以下一种操作,通过输出特定字符串完成操作:\n\n- 输出 `i j` :其中 $i,j$ 为正整数,要求 $1\\le i,j\\le n+1$,表示把 $a_i$ 赋值为 $a_j$。\n\n请把 $a$ 数组**...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments