Submission #3305264

---

Source Code Expand

#include <iostream>
#include <stdio.h>
#include <fstream>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <limits.h>
#include <math.h>
#include <functional>
#include <bitset>

#define repeat(i,n) for (long long i = 0; (i) < (n); ++ (i))
#define debug(x) cerr << #x << ": " << x << '\n'
#define debugArray(x,n) for(long long i = 0; (i) < (n); ++ (i)) cerr << #x << "[" << i << "]: " << x[i] << '\n'
#define debugArrayP(x,n) for(long long i = 0; (i) < (n); ++ (i)) cerr << #x << "[" << i << "]: " << x[i].first<< " " << x[i].second << '\n'

using namespace std;

typedef long long ll;
typedef pair<int,int> Pii;
typedef vector<int> vint;
typedef vector<ll> vll;
const ll INF = LLONG_MAX/10;
const ll MOD = 1e9+7;

template <ll mod>
struct ModCombination{
    ll N;
    vector<ll> fact,inv,finv;

    ModCombination(ll n):N(n){
        fact.assign(n+1, 1);
        inv.assign(n+1, 1);
        finv.assign(n+1,1);
        for(int i=1;i<n;i++){
            fact[i+1] = fact[i]*(i+1)%mod;
            inv[i+1] = inv[mod%(i+1)]*(mod-mod/(i+1))%mod;
            finv[i+1] = finv[i]*inv[i+1]%mod;
        }
    }

    ll P(ll n,ll k){
        return (fact[n]*finv[n-k]%mod);
    }
};

int main(){
  int N;cin>>N;
    ModCombination<MOD> c(N+1);
  vector<pair<int,bool>> x(2*N);
  repeat(b,2){
    repeat(i,N){
      cin >> x[b*N+i].first;
      x[b*N+i].second = b;
    }
  }
  sort(x.begin(),x.end());
  ll ans=1;
  int cnt[2]={0,0};
  repeat(i,2*N){
    cnt[x[i].second]++;
    if(i==2*N-1||x[i].second!=x[i+1].second){
      int mi = min(cnt[0],cnt[1]);
      ans = (ans*c.P(cnt[!x[i].second],mi))%MOD;
      cnt[0] -= mi;
      cnt[1] -= mi;
    }
  }
  cout << ans <<endl;
}

Submission Info

Judge Result