Submission #3775637

---

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>

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]){
      v[0] = v[0]-v[1]+v[2];
      ans = (ans * fact[v[1]])%INF;
      v.erase(v.begin()+1);
      v.erase(v.begin()+1);
    }
    else if(v[0] < v[1]){
      v[1] -= v[0];
      ans = (ans * fact[v[0]])%INF;
      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