Submission #1000854

---

Source Code Expand

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;

ll a[100001];
ll b[100001];
const int MOD = 1e9 + 7;
ll fact[100001];

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin>>n;
	fact[0]=1;
	for(int i = 1; i <= n; i++)
	{
		fact[i]=(fact[i-1]*i)%MOD;
	}
	ll sum = 0;
	for(int i =0;i<n;i++) 
	{
		cin>>a[i];
		sum+=a[i];
	}
	for(int i=0;i<n;i++) 
	{
		cin>>b[i];
		sum-=b[i];
	}
	if(sum<0) swap(a,b);
	sort(a,a+n);
	sort(b,b+n);
	ll ans = 1;
	/*
	int ptr = 0;
	ll avi = 0;
	ll cnt = 0;
	for(int i = 0; i < n; i++)
	{
		while(ptr<n&&b[ptr]<a[i])
		{
			ptr++;
			avi++;
		}
		if(avi>0)
		{
			ans=(ans*fact[cnt])%MOD;
			avi-=cnt;
			cnt=0;
		}
		if(avi>0)
		{
			ans=(ans*avi)%MOD;
			avi--;
			cnt=0;
		}
		else
		{
			cnt++;
		}
	}
	ans=(ans*fact[cnt])%MOD;
	*/
	/*
	ll run = 1;
	for(int i = 1; i < n; i++)
	{
		if((a[i]>b[i])==(a[i-1]>b[i-1]))
		{
			run++;
		}
		else
		{
			ans=(ans*fact[run])%MOD;
			run = 1;
		}
	}
	*/
	vector<ii> vec2;
	for(int i = 0; i < n; i++) vec2.pb(mp(a[i],0));
	for(int i = 0; i < n; i++) vec2.pb(mp(b[i],1));
	sort(vec2.begin(),vec2.end());
	vi runs;
	int cur = 0;
	for(int i = 0; i < 2*n; i++)
	{
		if(i==0)
		{
			cur++;
			continue;
		}
		if(vec2[i].se!=vec2[i-1].se)
		{
			runs.pb(cur);
			cur=1;
		}
		else
		{
			cur++;
		}
	}
	if(cur>0) runs.pb(cur);
	int ext = runs[0];
	for(int i = 1; i < runs.size(); i++)
	{
		ll tmp = min(ext, runs[i]);
		ans=(ans*fact[tmp])%MOD;
		ext += runs[i]-tmp;
		ext -= tmp;
	}
	cout<<ans<<'\n';
}

Submission Info

Judge Result