けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

Codeforces #485 (Div. 1) B. Petr and Permutations (R1800)

TL 見て面白そうだったから解いてみた!

問題概要

サイズ N の順列が与えられる。これは以下のいずれかによってつくられたものである。

  • Petr: (1, 2, ..., N) から出発して、ランダムに 2 要素を選んで swap する操作を 3N 回繰り返す
  • Um_nik: (1, 2, ..., N) から出発して、ランダムに 2 要素を選んで swap する操作を 7N + 1 回繰り返す

どちらの方法でつくられたものかを判定せよ。

制約

  • 103 <= N <= 106

解法

(7N + 1) - 3N = 4N + 1 より偶奇が異なる。それゆえ、Petr 方式と Um_nik 方式とでは、最終的に得られる順列の転倒数の偶奇が異なることになる。

BIT を用いて転倒数を求める

#include <iostream>
#include <vector>
using namespace std;


template <class Abel> struct BIT {
    vector<Abel> dat;
    Abel UNITY_SUM = 0;                        // to be set

    /* [1, n] */
    BIT(int n) { init(n); }
    void init(int n) {
        dat.resize(n + 1);
        for (int i = 0; i < (int)dat.size(); ++i) dat[i] = UNITY_SUM;
    }

    /* a is 1-indexed */
    inline void add(int a, Abel x) {
        for (int i = a; i < (int)dat.size(); i += i & -i)
            dat[i] = dat[i] + x;
    }

    /* [1, a], a is 1-indexed */
    inline Abel sum(int a) {
        Abel res = UNITY_SUM;
        for (int i = a; i > 0; i -= i & -i)
            res = res + dat[i];
        return res;
    }

    /* [a, b), a and b are 1-indexed */
    inline Abel sum(int a, int b) {
        return sum(b - 1) - sum(a - 1);
    }

    void print() {
        for (int i = 1; i < (int)dat.size(); ++i) cout << sum(i, i + 1) << ",";
        cout << endl;
    }
};


int main() {
  int n;
  cin >> n;
  vector<int> P(n);
  for (int i = 0; i < n; ++i) cin >> P[i];
  BIT<int> bit(n+1);
  long long tentou = 0;
  for (int i = 0; i < n; ++i) {
    long long tmp = bit.sum(P[i]+1, n+1);
    tentou += tmp;
    bit.add(P[i], 1);
  }

  if (n & 1) {
    if (tentou & 1) cout << "Petr" << endl;
    else cout << "Um_nik" << endl;
  }
  else {
    if (tentou & 1) cout << "Um_nik" << endl;
    else cout << "Petr" << endl;
  }
}