308272: CF1491G. Switch and Flip
Memory Limit:256 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Switch and Flip
题意翻译
桌面上有 $n$ 枚硬币。初始时,第 $c_i$ 号硬币位于位置 $i$,正面朝上($c_1, c_2, \cdots, c_n$ 是一个 $1 \sim n$ 的排列)。你可以对这些硬币做一些操作。每次操作,你可以如下进行: * 选择两个不同的 $i$ 和 $j$。 * 交换位于 $i$ 和 $j$ 的两枚硬币。 * 把位于 $i$ 和 $j$ 的两枚硬币分别翻转。 你可以进行不超过 $n + 1$ 次操作,使得第 $i$ 号硬币位于位置 $i$,且都是正面朝上。 你**不需要**最小化操作的次数,输出任意一种方案即可。题目描述
There are $ n $ coins labeled from $ 1 $ to $ n $ . Initially, coin $ c_i $ is on position $ i $ and is facing upwards (( $ c_1, c_2, \dots, c_n) $ is a permutation of numbers from $ 1 $ to $ n $ ). You can do some operations on these coins. In one operation, you can do the following: - Choose $ 2 $ distinct indices $ i $ and $ j $ . - Then, swap the coins on positions $ i $ and $ j $ . - Then, flip both coins on positions $ i $ and $ j $ . (If they are initially faced up, they will be faced down after the operation and vice versa) Construct a sequence of at most $ n+1 $ operations such that after performing all these operations the coin $ i $ will be on position $ i $ at the end, facing up. Note that you do not need to minimize the number of operations.输入输出格式
输入格式
The first line contains an integer $ n $ ( $ 3 \leq n \leq 2 \cdot 10^5 $ ) — the number of coins. The second line contains $ n $ integers $ c_1,c_2,\dots,c_n $ ( $ 1 \le c_i \le n $ , $ c_i \neq c_j $ for $ i\neq j $ ).
输出格式
In the first line, output an integer $ q $ $ (0 \leq q \leq n+1) $ — the number of operations you used. In the following $ q $ lines, output two integers $ i $ and $ j $ $ (1 \leq i, j \leq n, i \ne j) $ — the positions you chose for the current operation.
输入输出样例
输入样例 #1
3
2 1 3
输出样例 #1
3
1 3
3 2
3 1
输入样例 #2
5
1 2 3 4 5
输出样例 #2
0