Problem - 986B - B. Petr and Permutations(排序的奇偶性)

B. Petr and Permutations

题目大意:现给定一个$n$的排列,每次可以选择一组$i,j$交换$p_i,p_j$,$A$决定交换$3n$次,$B$决定交换$7n+1$次,现在给定打乱后的排列,判断该排列是由谁打乱的.

解题思路:逆向思维一下,我们先把这个排列复原,看需要多少次交换,因为两个人的打乱次数一个是奇数次,一个是偶数次,且都大于我们复原排列的次数,那么我们只需要看交换的奇偶性来判断即可.

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define syncfalse ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
const int N = 1e6+5;
int a[N], pos[N];
int main(){
    syncfalse#ifndef ONLINE_JUDGEfreopen("in.txt","r",stdin);#endifint n;cin>>n;for (int i = 1; i <= n; ++i){
    cin>>a[i];pos[a[i]]=i;}int cnt = 0;for (int i = n; i >= 1; --i){
    int id = pos[i];if (id==i)continue;else{
    int val = a[i];swap(a[i], a[id]);pos[i]=i;pos[val]=id;cnt++;
// for (int i = 1; i <= n; ++i)cout << a[i] << " ";cout << "\n";
// for (int i = 1; i <= n; ++i)cout << pos[i] << " ";cout << "\n";}}int change1 = n*3, change2 = n*7+1;if (cnt%2==change1%2)cout << "Petr\n";else cout << "Um_nik\n";return 0;
}