Submission #3775704

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

#define REP(i,m) for(int i=0; i<m; i++)
#define FOR(i,n,m) for(int i=n; i<m; i++)
#define INF 1000000007
#define INFL (1LL << 60)
#define MOD 998244353
#define ALL(v) v.begin(),v.end()
#define pb push_back
#define ll long long int
#define P pair<ll, ll>

ll POW(ll a, ll b){
  if(b == 0) return 1LL;
  if(b == 1) return a;
  if(b%2 == 1) return (a*POW(a, b-1))%INF;
  ll x = POW(a, b/2);
  return (x*x)%INF;
}

int main(){
  int n;
  cin >> n;
  P p[2*n];
  REP(i, n){
    int a;
    cin >> a;
    p[i] = {a, 0};
  }
  REP(i, n){
    int a;
    cin >> a;
    p[n+i] = {a, 1};
  }
  sort(p, p+2*n);
  vector<int> v;
  int c = 1;
  REP(i, 2*n-1){
    if(p[i].second == p[i+1].second) c++;
    else{
      v.pb(c);
      c = 1;
    }
  }
  v.pb(c);
  ll ans = 1;
  ll fact[100010];
  fact[0] = 1;
  REP(i, 100009) fact[i+1] = (fact[i] * (i+1))%INF; 
  while(v.size()!=0){
    if(v[0] > v[1]){
      ans = (ans * fact[v[1]])%INF;
      ans = (ans * POW(fact[v[0]-v[1]], INF-2))%INF;
      v[0] = v[0]-v[1]+v[2];
      v.erase(v.begin()+1);
      v.erase(v.begin()+1);
    }
    else if(v[0] < v[1]){
      ans = (ans * fact[v[0]])%INF;
      ans = (ans * POW(fact[v[1]-v[0]], INF-2))%INF;
      v[1] -= v[0];
      v.erase(v.begin());
    }
    else{
      ans = (ans * fact[v[0]])%INF;
      v.erase(v.begin());
      v.erase(v.begin());
    }
  }
  cout << ans << endl;
}

Submission Info

Judge Result