Problem:


Score : 500 points

Problem Statement

   #nck {
      width: 30px;
      height: auto;
   }

There are N computers and N sockets in a one-dimensional world.
The coordinate of the i-th computer is a_i, and the coordinate of the i-th socket is b_i.
It is guaranteed that these 2N coordinates are pairwise distinct.

Snuke wants to connect each computer to a socket using a cable.
Each socket can be connected to only one computer.

In how many ways can he minimize the total length of the cables?
Compute the answer modulo 10^9+7.

Constraints

1 ≤ N ≤ 10^5

0 ≤ a_i, b_i ≤ 10^9

The coordinates are integers.

The coordinates are pairwise distinct.

Input

The input is given from Standard Input in the following format:

N
a_1
:
a_N
b_1
:
b_N

Output

Print the number of ways to minimize the total length of the cables, modulo 10^9+7.

Sample Input 1

2
0
10
20
30

Sample Output 1

2

There are two optimal connections: 0-20, 10-30 and 0-30, 10-20.
In both connections the total length of the cables is 40.

Sample Input 2

3
3
10
8
7
12
5

Sample Output 2

1



Sample input:
2
0
10
20
30


Sample output:
2

Submission status: Wrong Answer

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools


import queue
from collections import deque


def main():
    num = int(input())
    data_pc = [int(input()) for i in range(num)]
    data_tap = [int(input()) for i in range(num)]

    data_pc.sort()
    data_tap.sort()

    ans = 1
    mod = 10 ** 9 + 7

    count_span = [0 for i in range(num + 1)]

    ind_tap = 0
    for ind_pc in range(num):
        count_tap = 0
        while ind_tap < num:
            if data_tap[ind_tap] > data_pc[ind_pc]:
                break
            count_tap += 1
            ind_tap += 1
        count_span[ind_pc] = count_tap

    count_span[num] = num - sum(count_span)

    # print(count_span)
    # num = 10
    # count_span = [10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
    # print(count_span)

    count_0 = 0
    count_tap = 0
    for i in range(num + 1):
        if count_span[i] == 0:
            count_0 += 1
        else:
            minus = min(count_0, count_tap)
            for i in range(2, minus + 1):
                ans *= i
                ans %= mod
            count_0 -= minus
            count_tap -= minus

            count_tap += count_span[i]
            minus = min(count_0, count_tap)
            for i in range(2, minus + 1):
                ans *= i
                ans %= mod
            count_0 -= minus
            count_tap -= minus



    for i in range(2, count_tap + 1):
        ans *= i
        ans %= mod

    print(ans)












if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools


import queue
from collections import deque


def main():
    num = int(input())
    data_pc = [int(input()) for i in range(num)]
    data_tap = [int(input()) for i in range(num)]

    data_pc.sort()
    data_tap.sort()

    ans = 1
    mod = 10 ** 9 + 7

    count_span = [0 for i in range(num + 1)]

    ind_tap = 0
    for ind_pc in range(num):
        count_tap = 0
        while ind_tap < num:
            if data_tap[ind_tap] > data_pc[ind_pc]:
                break
            count_tap += 1
            ind_tap += 1
        count_span[ind_pc] = count_tap

    count_span[num] = num - sum(count_span)

    # print(count_span)

    count_0 = 0
    count_tap = 0
    for i in range(num + 1):
        if count_span[i] == 0:
            count_0 += 1
        else:
            minus = min(count_0, count_tap)
            for i in range(2, minus + 1):
                ans *= i
                ans %= mod
            count_0 -= minus
            count_tap -= minus

            count_tap += count_span[i]
            minus = min(count_0, count_tap)
            for i in range(2, minus + 1):
                ans *= i
                ans %= mod
            count_0 -= minus
            count_tap -= minus



    # for i in range(2, count_tap + 1):
    #     ans *= i
    #     ans %= mod

    print(ans)












if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools


import queue
from collections import deque


def main():
    num = int(input())
    data_pc = [int(input()) for i in range(num)]
    data_tap = [int(input()) for i in range(num)]

    data_pc.sort()
    data_tap.sort()

    ans = 1
    mod = 10 ** 9 + 7

    tap_ind = 0
    count_pc = 0
    count_tap = 0
    for pc_ind in range(num):
        now_pc = data_pc[pc_ind]

        while tap_ind < num:
            if data_tap[tap_ind] >= now_pc:
                break
            tap_ind += 1
            count_tap += 1

        if count_pc and count_tap:
            minus_num = min(count_pc, count_tap)
            for i in range(2, minus_num + 1):
                ans *= i
                ans %= mod
            count_pc -= minus_num
            count_tap -= minus_num

        count_pc += 1

    for i in range(2, count_pc + 1):
        ans *= i
        ans %= mod

    print(ans)














if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, res = int(input()), 1
a = []
for i in range(n):
  a.append((int(input()), 1))
for i in range(n):
  a.append((int(input()), -1))
a.sort()
t = 0
for i in a:
  if abs(i[1] + t) != abs(i[1]) + abs(t):
    res = (res * abs(t)) % 1000000007
  t += i[1]
print(res)

Submission status: Accepted

Solution code:
N,*E=map(int,open(0))
a,c=1,0
for _,d in sorted((e,2*(i<N)-1)for i,e in enumerate(E)):
	if c*d<0:a=abs(a*c)%(10**9+7)
	c+=d
print(a)

Submission status: Accepted

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools


import queue
from collections import deque

def main():
    num = int(input())
    data_pc = sorted([int(input()) for i in range(num)])
    data_tap = sorted([int(input()) for i in range(num)])

    ans = 1
    mod = 10 ** 9 + 7

    ind_pc = 0
    ind_tap = 0
    count_pc, count_tap = 0, 0

    while ind_pc < num or ind_tap < num:
        if ind_pc >= num:
            if count_pc > 1:
                ans *= count_pc
                count_pc -= 1
            ind_tap += 1
        elif ind_tap >= num:
            if count_tap >= 1:
                ans *= count_tap
                count_tap -= 1
            ind_pc += 1
        elif data_pc[ind_pc] < data_tap[ind_tap]:
            count_pc += 1
            if count_tap >= 1:
                ans *= count_tap
                count_tap -= 1
                count_pc -= 1
            ind_pc += 1
        else:
            count_tap += 1
            if count_pc >= 1:
                ans *= count_pc
                count_pc -= 1
                count_tap -= 1
            ind_tap += 1
        ans %= mod

    print(ans)





if __name__ == '__main__':
    main()
    # test()

Submission status: Accepted

Solution code:
N,*E=map(int,open(0).read().split())
a,c=1,0
for _,d in sorted((e,2*(i<N)-1)for i,e in enumerate(E)):
	if c*d<0:a=abs(a*c)%(10**9+7)
	c+=d
print(a)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    a = sorted([I() for _ in range(n)])
    b = sorted([I() for _ in range(n)])
    r = 1
    ai = 0
    bi = 0
    sa = 0
    while ai < n or bi < n:
        if ai >= n:
            if sa > 1:
                r *= sa
            sa -= 1
            bi += 1
        elif bi >= n:
            if sa < -1:
                r *= -sa
            sa += 1
            ai += 1
        elif a[ai] < b[bi]:
            if sa < -1:
                r *= -sa
            sa += 1
            ai += 1
        else:
            if sa > 1:
                r *= sa
            sa -= 1
            bi += 1
        r %= mod

    return r




print(main())