提出 #41126530

---

ソースコード 拡げる

#include <atcoder/all>
using namespace atcoder;
#include <bits/stdc++.h>
#include <cassert>
using namespace std;
using ll = long long;
const double pi = 3.14159265359;
const ll INF = 1LL << 60;

template<class T> inline bool chmin(T& a, T b){ if (a > b){a = b; return true;} return false;}
template<class T> inline bool chmax(T& a, T b){ if (a < b){a = b; return true;} return false;}

//using mint = modint998244353;
//using mint = modint1000000007;
//using mint = modint;  // mint::set_mod(p); later
//using mint = static_modint<1000000009>;

int main()
{
  cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

  // Input
  int N;
  cin >> N;
  vector<int> a(N), b(N);
  for (auto &&t : a){ cin >> t; t--; }
  for (auto &&t : b){ cin >> t; t--; }

  // 多重集合として一致するかをみる。
  vector<int> ca(N), cb(N);
  bool flg = false; // A の中に二回以上登場する要素がある
  for (int na : a){
    if (ca[na] != 0) flg = true;
    ca[na]++;
  }
  for (int nb : b){
    cb[nb]++;
  }
  for (int i = 0; i < N; i++){
    if (ca[i] != cb[i]){
      cout << "No" << endl;
      return 0;
    }
  }

  if (flg){
    cout << "Yes" << endl;
    return 0;
  }

  // この時点で、A と B は何も [0, 1, ..., N-1] の並び替え

  // A, B それぞれの転倒数の合計を求める。
  fenwick_tree<int> c(N), d(N);
  ll z = 0;
  for (int na : a){
    z += c.sum(na, N);
    c.add(na, 1);
  }
  for (int nb : b){
    z += d.sum(nb, N);
    d.add(nb, 1);
  }


  cout << (z%2 == 0 ? "Yes" : "No") << endl;
  return 0;
}

提出情報

ジャッジ結果