Submission #3285614

---

Source Code Expand

using System;
using System.Collections.Generic;
using System.Linq;
using System.Web;

namespace Competitive
{
    internal class Solution
    {
        public int N;
        public long MOD = 1000000007;
        public void Run()
        {
            N = Input.ReadInt();
            var ps = new List<int>();
            var cs = new List<int>();
            for (int i = 0; i < N; i++)
            {
                ps.Add(Input.ReadInt());
            }

            for (int i = 0; i < N; i++)
            {
                cs.Add(Input.ReadInt());
            }

            ps.Sort();
            cs.Sort();

            var pi = 0;
            var ci = 0;
            int p = 0;
            int c = 0;

            var comb = new FermatCombination(150000);

            long ret = 1;
            while (true)
            {
                if (ci == N || (pi != N && ps[pi] < cs[ci]))
                {
                    pi++;
                    p++;
                }
                else
                {
                    ci++;
                    c++;
                }

                if (c == p)
                {
                    var cc = comb.Permutation(c, c);
                    ret *= cc;
                    ret %= MOD;

                    c = 0;
                    p = 0;
                }

                if (pi == N && ci == N) break;
            }

            Console.WriteLine(ret);
        }
    }

    // libs ----------
    // フェルマーの定理、逆元を使う場合
    class FermatCombination
    {
        public long[] Factrial; // 階乗
        public long[] Inverse; // 逆元
        public long MOD = 1000000007;

        public FermatCombination(int n)
        {

            Factrial = new long[n + 1];
            Inverse = new long[n + 1];
            Factrial[0] = 1;
            Inverse[0] = 1;

            for (int i = 1; i <= n; i++)
            {
                Factrial[i] = (Factrial[i - 1] * i) % MOD;
            }

            for (int i = 1; i <= n; i++)
            {
                // フェルマーの小定理で逆元を求める
                Inverse[i] = Power(Factrial[i], (int)MOD - 2, MOD) % MOD;
            }
        }

        public long Permutation(int n, int k)
        {
            return Factrial[n] * Inverse[n - k] % MOD;
        }

        public long Combination(int n, int k)
        {
            return Factrial[n] * Inverse[k] % MOD * Inverse[n - k] % MOD;
        }

        public static long Power(long x, long n, long M)
        {
            long tmp = 1;

            if (n > 0)
            {
                tmp = Power(x, n / 2, M);
                if (n % 2 == 0) tmp = (tmp * tmp) % M;
                else tmp = (((tmp * tmp) % M) * x) % M;
            }

            return tmp;
        }
    }

    // common ----------

    internal static class Input
    {
        public static string ReadString()
        {
            string line = Console.ReadLine();
            return line;
        }

        public static int ReadInt()
        {
            string line = Console.ReadLine();
            return int.Parse(line);
        }

        public static int[] ReadIntArray()
        {
            string line = Console.ReadLine();
            return line.Split(' ').Select(int.Parse).ToArray();            
        }

        public static long ReadLong()
        {
            string line = Console.ReadLine();
            return long.Parse(line);
        }

        public static long[] ReadLongArray()
        {
            string line = Console.ReadLine();
            return line.Split(' ').Select(long.Parse).ToArray();
        }

        public static double[] ReadDoubleArray()
        {
            string line = Console.ReadLine();
            return line.Split(' ').Select(double.Parse).ToArray();
        }
    }
    
    internal class Program
    {
        public static void Main(string[] args)
        {
            var s = new Solution();
            s.Run();
        }
    }
}

Submission Info

Judge Result