【链接】 我是链接,点我呀:)
【题意】
题意
【题解】
n为奇数时3*n和7*n+1奇偶性不同
n为偶数时也是如此
然后交换任意一对数
逆序对的对数的奇偶性会发生改变一次
求出逆序对 对n讨论得出答案。
【代码】
import java.io.*;
import java.util.*;
public class Main {
static InputReader in;
static PrintWriter out;
public static void main(String[] args) throws IOException{
//InputStream ins = new FileInputStream("E:\\rush.txt");
InputStream ins = System.in;
in = new InputReader(ins);
out = new PrintWriter(System.out);
//code start from here
new Task().solve(in, out);
out.close();
}
static int N = (int)1e6;
static class Task{
int n;
int a[] = new int[N+10];
int temp[] = new int[N+10];
int ans = 0;
public void mergesort(int l,int r) {
if (l>=r) return;
int mid = (l+r)/2;
mergesort(l,mid);mergesort(mid+1,r);
int k = l,i = l,j = mid+1;
while (i <= mid && j <= r) {
if (a[i]>a[j]) {
ans = ans + mid-i+1;
ans = ans % 2;
temp[k++] = a[j];
j++;
}else {
temp[k++] = a[i];
i++;
}
}
while (i<=mid) {
temp[k++] = a[i];
i++;
}
while (j<=r) {
temp[k++] = a[j];
j++;
}
for (i = l;i <= r;i++) a[i] = temp[i];
}
public void solve(InputReader in,PrintWriter out) {
n = in.nextInt();
for (int i = 1;i <= n;i++) {
a[i] = in.nextInt();
}
mergesort(1,n);
if (n%2==1) {
if (ans==1) {
out.println("Petr");
}else {
out.println("Um_nik");
}
}else {
if (ans==1) {
out.println("Um_nik");
}else {
out.println("Petr");
}
}
}
}
static class InputReader{
public BufferedReader br;
public StringTokenizer tokenizer;
public InputReader(InputStream ins) {
br = new BufferedReader(new InputStreamReader(ins));
tokenizer = null;
}
public String next(){
while (tokenizer==null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(br.readLine());
}catch(IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
}
}