Submission #1990518


Source Code Expand

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
 
class TEST{
	static void Main(){
		Sol mySol =new Sol();
		mySol.Solve();
	}
}
 
class Sol{
	public void Solve(){
		
		long mod = (long) 1e9 + 7;
		long[] frac = new long[N+1];
		frac[0] = 1;
		for(int i=1;i<=N;i++) frac[i] = (frac[i-1] * i) % mod;
		List<Pair> L = new List<Pair>();
		for(int i=0;i<N;i++){
			L.Add(new Pair(A[i], 1));
		}
		for(int i=0;i<N;i++){
			L.Add(new Pair(B[i], -1));
		}
		
		L.Sort((p, q) => p.Val.CompareTo(q.Val));
		long ans = 1;
		List<Pair> tot = new List<Pair>();;
		long sig = 0;
		foreach(var p in L){
			sig += p.Sig;
			tot.Add(p);
			if(sig == 0){
				int[] sum = new int[tot.Count + 1];
				for(int i=0;i<tot.Count;i++){
					int inc = tot[i].Sig == tot[0].Sig ? 0 : 1;
					sum[i+1] = sum[i] + inc;
				}
				int NN = tot.Count / 2;
				
				long pat = 1;
				int cnt = 0;
				for(int i=tot.Count - 1;i>=0;i--){
					if(tot[i].Sig != tot[0].Sig) continue;
					pat *= NN - sum[i] - cnt;
					pat %= mod;
					cnt++;
				}
				
				ans *= pat;
				ans %= mod;
				tot.Clear();
			}
		}
		
		Console.WriteLine(ans);
		
		
	}
	
	class Pair{
		public int Val, Sig;
		public Pair(int val, int sig){
			Val = val; Sig = sig; 
		}
	}
	
	
	int N;
	int[] A,B;
	public Sol(){
		N = ri();
		A = new int[N];
		for(int i=0;i<N;i++) A[i] = ri();
		B = new int[N];
		for(int i=0;i<N;i++) B[i] = ri();
	}
 
	static String rs(){return Console.ReadLine();}
	static int ri(){return int.Parse(Console.ReadLine());}
	static long rl(){return long.Parse(Console.ReadLine());}
	static double rd(){return double.Parse(Console.ReadLine());}
	static String[] rsa(char sep=' '){return Console.ReadLine().Split(sep);}
	static int[] ria(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>int.Parse(e));}
	static long[] rla(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>long.Parse(e));}
	static double[] rda(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>double.Parse(e));}
}

Submission Info

Submission Time
Task A - 1D Matching
User kuuso
Language C# (Mono 4.6.2.0)
Score 500
Code Size 2158 Byte
Status AC
Exec Time 320 ms
Memory 30676 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 175 ms 18652 KB
001.txt AC 81 ms 15712 KB
002.txt AC 94 ms 13408 KB
003.txt AC 115 ms 19292 KB
004.txt AC 251 ms 21336 KB
005.txt AC 300 ms 25940 KB
006.txt AC 317 ms 30676 KB
007.txt AC 292 ms 26068 KB
008.txt AC 287 ms 27092 KB
009.txt AC 320 ms 26068 KB
010.txt AC 285 ms 28756 KB
011.txt AC 292 ms 27220 KB
example0.txt AC 22 ms 11348 KB
example1.txt AC 22 ms 11348 KB