CF-986B Petr and Permutations 题解

题目大意

原本有一个1~n按照大小排列的序列，有两个人会交换他，P会交换$3n$次，U会交换$7n+1$次，给你交换后的数组，问是谁交换的。

每对数字只能被交换一次。

解题思路

这题是和富哥一起讨论的，主要是他得出的思路，我是被带的。。

所以还是写个题解吧。

前排提示，这个思路虽然过了，但是正确性没有证明。

按照他给的交换后的排序，我们先考虑把这个序列交换回原来的序列，并记录次数。

因为这个序列是按照步骤最少的交换来还原的，所以这个次数肯定比他们所交换的次数要少。

但是可以将剩下的次数理解为是让他们两两交换，并且使交换后的序列仍然是完好的。

这个交换的次数肯定是偶数。

所以当n与cnt奇偶的时候，必定是P交换的。

完整代码

#include <iostream>
using namespace std;
typedef long long ll;

const int N = 1e6 + 5;
int num[N],pos[N];

int main() {
	int n; cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> num[i];
		pos[num[i]] = i;
	}
	ll cnt = 0;
	for (int i = 1; i <= n; i++) {
		if (pos[i] != i) {
			swap(num[i], num[pos[i]]);
			swap(pos[i], pos[num[pos[i]]]);
			cnt++;
		}
		
	}
	if ((cnt & 1) == (n & 1))	cout << "Petr" << endl;
	else cout << "Um_nik" << endl;
}