RUPC day1 B: 写像

問題ページ
Aizu Online Judge Arena

解法

写像fが全射であれば問題の条件を必ず満たす。
もし全射でなければf(x)として現れない数が必ず存在している。そのような数zについてg(z) != h(z)となるように構成すればよい。

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)

signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  int n;
  cin >> n;
  VI a(n), b(n);
  REP(i, n) cin >> a[i];
  REP(i, n) cin >> b[i];

  set<int> st;
  REP(i, n) st.insert(a[i]);
  REP(i, n) {
    if(st.find(b[i]) != st.end()) {
      st.erase(b[i]);
    }
  }

  if(st.size() == 0) {
    cout << "Yes" << endl;
    return 0;
  }

  // stに残っているところを not equal にする
  VI c(n), d(n);
  REP(i, n) {
    if(st.find(a[i]) == st.end()) {
      c[i] = a[i], d[i] = a[i];
    } else {
      // n=1であれば必ずyesなので配列外参照はしない
      c[i] = a[0], d[i] = a[1];
    }
  }

  cout << "No" << endl;
  REP(i, n) cout << c[i] << (i==n-1?"\n":" ");
  REP(i, n) cout << d[i] << (i==n-1?"\n":" ");

  return 0;
}