Submission #4027411


Source Code Expand

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
ll mod=1000000007;
ll gyaku(ll n){
  ll y=mod-2;
  ll now=n;
  ll ret=1;
  while(y>0){
    if(y%2==1)ret*=now;
    now*=now;
    ret%=mod;
    now%=mod;
    y/=2;
  }
  return ret;
}
ll nck(ll n,ll k){
  if(2*k>n)k=n-k;
  ll ret=1;
  for(ll i=0;i<k;i++){
    ret*=n-i;
    ret%=mod;
    ret*=gyaku(i+1);
    ret%=mod;
  }
  return ret;
}
int main(){
  ll n;cin>>n;
  vector<pll> v;
  ll a[n],b[n];
  ll kai[100001];
  kai[0]=1;
  for(ll i=0;i<n;i++){
    cin>>a[i];
    v.push_back(make_pair(a[i],(ll)0));
  }
  for(ll i=0;i<n;i++){
    cin>>b[i];
    v.push_back(make_pair(b[i],(ll)1));
  }
  sort(v.begin(),v.end());
  for(ll i=1;i<=100000;i++){
    kai[i]=kai[i-1]*i;
    kai[i]%=mod;
  }
  ll ans=1;
  ll c[2];
  c[0]=0;c[1]=0;
  for(ll i=0;i<v.size();i++){
    ll t=v[i].second;
    ll s=(t+1)%2;
    c[t]++;
    if(c[t]>c[s]&&c[s]>0){
      ans*=nck(c[t]-1,c[s]);
      ans%=mod;
      ans*=kai[c[s]];
      ans%=mod;
      c[t]-=c[s];
      c[s]=0;
    }
   // cout<<c[0]<<" "<<c[1]<<endl;
  }
  ans*=kai[c[0]];
  ans%=mod;
  cout<<ans<<endl;
}
                

Submission Info

Submission Time
Task A - 1D Matching
User ttttan
Language C++14 (GCC 5.4.1)
Score 500
Code Size 1229 Byte
Status AC
Exec Time 161 ms
Memory 7152 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
AC × 2
AC × 14
Set Name Test Cases
Sample example0.txt, example1.txt
All 000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, example0.txt, example1.txt
Case Name Status Exec Time Memory
000.txt AC 99 ms 3952 KB
001.txt AC 38 ms 2164 KB
002.txt AC 51 ms 2548 KB
003.txt AC 57 ms 2932 KB
004.txt AC 144 ms 7024 KB
005.txt AC 160 ms 6640 KB
006.txt AC 161 ms 7152 KB
007.txt AC 161 ms 7024 KB
008.txt AC 161 ms 6768 KB
009.txt AC 161 ms 5868 KB
010.txt AC 99 ms 6384 KB
011.txt AC 101 ms 5872 KB
example0.txt AC 3 ms 1024 KB
example1.txt AC 3 ms 1024 KB