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:
N=int(input())
C=[]
for i in range(N):
  C.append((int(input()),"a")) 
for i in range(N):
  C.append((int(input()),"b")) 
C.sort()
mod=10**9+7
a,b=0,0
ans=1
for c in C:
  if c[1]=="a":
    if b>0:
      ans=(ans*b)%mod
      b-=1
    else:
      a+=1
  if c[1]=="b":
    if a>0:
      ans=(ans*a)%mod
      a-=1
    else:
      b+=1
  print(a,b,ans)
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=[(int(input()),"a") for i in range(N)]
B=[(int(input()),"b") for i in range(N)]
C=sorted(A+B)
mod=10**9+7
a,b=0,0
ans=1
for c in C:
  if c[1]=="a":
    if b>0:
      ans*=(ans*b)%mod
      b-=1
    else:
      a+=1
  if c[1]=="b":
    if a>0:
      ans=(ans*a)%mod
      a-=1
    else:
      b+=1
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
mod = 10**9 + 7
fac = [1 for _ in range(N+1)]
for i in range(N):
    fac[i+1] = (i+1)*fac[i]%mod

a = sorted([int(input()) for _ in range(N)])
b = sorted([int(input()) for _ in range(N)])
ab = list(zip(a,b))
X = [-2, -1]
ctr = 1
H = []
for i, j in ab:
    if i > j:
        i, j = j, i 
    if i < X[1]:
        X = [i,X[1]]
        ctr += 1
    else:
        H.append(ctr)
        ctr = 1
        X = i, j
ans = fac[ctr]
for i in H:
    ans = ans*fac[i]%mod
print(ans%mod)

Submission status: Wrong Answer

Solution code:
N = int(input())
mod = 10**9 + 7
fac = [1 for _ in range(N+1)]
for i in range(N):
    fac[i+1] = (i+1)*fac[i]%mod

a = sorted([int(input()) for _ in range(N)])
b = sorted([int(input()) for _ in range(N)])
ab = list(zip(a,b))
X = [-2, -1]
ctr = 1
H = []
for i, j in ab:
    if i < X[1]:
        X = [i,X[1]]
        ctr += 1
    else:
        H.append(ctr)
        ctr = 1
        X = i, j
ans = fac[ctr]
for i in H:
    ans = ans*fac[i]%mod
print(ans%mod)

Submission status: Wrong Answer

Solution code:
N = int(input())
mod = 10**9 + 7
fac = [1 for _ in range(N+1)]
for i in range(N):
    fac[i+1] = (i+1)*fac[i]%mod

a = sorted([int(input()) for _ in range(N)])
b = sorted([int(input()) for _ in range(N)])
ab = list(zip(a,b))
X = [-2, -1]
ctr = 1
H = []
for i, j in ab:
    if i < X[1]:
        X = [i,X[1]]
        ctr += 1
    else:
        H.append(ctr)
        ctr = 1
        X = i, j
ans = ctr
for i in H:
    ans = ans*fac[i]%mod
print(ans%mod)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=[]
mod=10**9+7
for i in range(N):
    a=int(input())
    A.append((a,-1))
for i in range(N):
    a=int(input())
    A.append((a,1))
A.sort()
a=0
s=A[0][1]
ans=1
for i in range(2*N):
    if A[i][1]==s:
        a+=1
    else:
        ans*=a
        a%=mod
        a-=1
    if a==0 and i<2*N-1:
        s=A[i+1][1]
    #print(a,s,ans)
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=[]
mod=10**9+7
table=[1]*(2*N)
t=1
for i in range(1,2*N):
    t*=i
    t%=mod
    table[i]=t
for i in range(N):
    a=int(input())
    A.append((a,-1))
for i in range(N):
    a=int(input())
    A.append((a,1))
A.sort()
s=0
x=0
ans=1
for i in range(2*N):
    s+=A[i][1]
    x+=1
    if s==0:
        b=x//2
        ans*=table[b]
        ans%=mod
        x=0
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=[]
mod=10**9+7
table=[1]*(2*N)
t=1
for i in range(1,2*N):
    t*=i
    t%=mod
    table[i]=t
for i in range(2*N):
    a=int(input())
    if i<N:
        A.append((a,-1))
    else:
        A.append((a,1))
A.sort()
s=0
t=0
ans=1
for i in range(2*N):
    s+=A[i][1]
    t+=1
    if s==0:
        ans*=table[t//2]
        ans%=mod
        t=0
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

# nの階乗のリスト
def fact(n:int, mod:int) -> list:
    fac = [1,1]
    res = 1
    for i in range(2,n+1):
        res = res*i%mod
        fac.append(res)
    return fac

MOD = 10**9+7

devices = []

n = ni()
for _ in range(n):
    a = ni()
    devices.append((a, 1))
    
for _ in range(n):
    b = ni()
    devices.append((b, -1))
    
devices.sort()

pc = [0,0]

ans = 1
for point, typ in devices:
    if typ == 1 and pc[1] > 0:
        ans = (ans * pc[1]) % MOD
        pc[1] -= 1
        
    elif typ == 1:
        pc[0] += 1
        
    elif typ == -1 and pc[0] > 0:
        ans = (ans * pc[0]) % MOD
        pc[0] -= 1
        
    elif typ == 1:
        pc[1] += 1
        
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

# nの階乗のリスト
def fact(n:int, mod:int) -> list:
    fac = [1,1]
    res = 1
    for i in range(2,n+1):
        res = res*i%mod
        fac.append(res)
    return fac

MOD = 10**9+7

devices = []

n = ni()
for _ in range(n):
    a = ni()
    devices.append((a, 1))
    
for _ in range(n):
    b = ni()
    devices.append((b, -1))
    
devices.sort()

cur = 0
ans = 1
hist = 0
fac = fact(n, MOD)
for point, typ in devices:
    cur += typ
    hist += 1
    
    if cur == 0:
        ans = (ans * fac[hist//2]) % MOD
        hist = 0
        
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

# nの階乗のリスト
def fact(n:int, mod:int) -> list:
    fac = [1,1]
    res = 1
    for i in range(2,n+1):
        res = res*i%mod
        fac.append(res)
    return fac

MOD = 10**9+7

devices = []

n = ni()
for _ in range(n):
    a = ni()
    devices.append((a, 1))
    
for _ in range(n):
    b = ni()
    devices.append((b, -1))
    
devices.sort()

cur = 0
ans = 1
hist = 0
fac = fact(n, MOD)
for point, typ in devices:
    cur += typ
    hist = max(hist, abs(cur))
    if cur == 0:
        ans = (ans * fac[hist]) % MOD
        hist = 0
        
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

# nの階乗のリスト
def fact(n:int, mod:int) -> list:
    fac = [1,1]
    res = 1
    for i in range(2,n+1):
        res = res*i%mod
        fac.append(res)
    return fac

MOD = 10**9+7

devices = []

n = ni()
for _ in range(n):
    a = ni()
    devices.append((a, 1))
    
for _ in range(n):
    b = ni()
    devices.append((b, -1))
    
devices.sort()

cur = 0
ans = 1
hist = 0
fac = fact(n, MOD)
for point, typ in devices:
    cur += typ
    hist = max(hist, abs(cur))
    if cur == 0:
        ans = (ans * fac[hist]) % MOD
        
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [('a',int(input())) for _ in range(n)]
b = [('b',int(input()))for _ in range(n)]
ab = sorted(a+b, key=lambda x: x[1])
m = []
count = 0
for k,i in ab:
    if k == 'a':
        if count < 0:
            m.append(-count)
        count += 1
    else:
        if count > 0:
            m.append(count)
        count -= 1
from itertools import accumulate as acc
from operator import mul
print(list(acc(m, mul))[-1])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())

N = int(input())
points = []
for i in range(N):
    a = int(input())
    points.append([a,True])
for i in range(N):
    b = int(input())
    points.append([b,False])
points.sort()

ans = 1
an = bn = 0
for x,c in points:
    if c:
        if bn > 0:
            ans *= bn
            bn -= 1
        else:
            an += 1
    else:
        if an > 0:
            ans *= an
            an -= 1
        else:
            bn += 1    

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())

N = int(input())
points = []
for i in range(N):
    a = int(input())
    points.append([a,True])
for i in range(N):
    b = int(input())
    points.append([b,False])
points.sort()

fac = [1]*(10**5+3)
for i in range(2,10**5+3):
    fac[i] = fac[i-1]*i%mod

tmp = MAX = 0
ans = 1
for x,c in points:
    if c:
        tmp += 1
    else:
        tmp -= 1
    MAX = max(MAX,abs(tmp))
    if tmp == 0:
        ans *= fac[MAX]
        ans %= mod
        MAX = 0

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())

N = int(input())
points = []
for i in range(N):
    a = int(input())
    points.append([a,True])
for i in range(N):
    b = int(input())
    points.append([b,False])
points.sort()

fac = [1]*(10**5+3)
for i in range(2,10**5+3):
    fac[i] = fac[i-1]*i%mod

tmp = MAX = 0
ans = 1
for x,c in points:
    if c:
        tmp += 1
    else:
        tmp -= 1
    MAX = max(MAX,abs(tmp))
    if tmp == 0:
        ans *= fac[MAX]
        ans %= mod

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
a = [(int(input()), 1) for _ in range(N)]
b = [(int(input()), 0) for _ in range(N)]
X = sorted(a + b)

ls = 0
stack = []
ans = 1
for v, f in X:
    if stack and stack[-1] != f:
        ans *= ls
        stack.pop()
        ls -= 1
    else:
        stack.append(f)
        ls += 1

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [(int(input()), 0) for i in range(N)]
B = [(int(input()), 1) for i in range(N)]
Object = sorted(A + B)
mod = 10 ** 9 + 7

ans = 1
memo = [0, 0]
for n, x in Object:
    if memo[1 - x] > 0:
        ans *= memo[1 - x] % mod
        memo[1 - x] -= 1
    else:
        memo[x] += 1

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
a = [int(input()) for i in range(N)]
a.sort()
b = [int(input()) for i in range(N)]
b.sort()
MOD = 10**9+7

f = [1]
def factorial(n):
    while len(f) <= n:
        f.append((f[-1] * len(f)) % MOD)
    return f[n]

ans = 1
ai = bi = sec = 0
while ai + bi < 2*N:
    if ai == N:
        bi += 1
    elif bi == N:
        ai += 1
    elif a[ai] < b[bi]:
        ai += 1
    else:
        bi += 1
    if ai == bi:
        n = ai - sec
        ans = (ans * factorial(n)) % MOD
        sec = ai
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = sorted([int(input()) for i in range(n)])
b = sorted([int(input()) for i in range(n)])
ans = 1
MOD = 1000000007
cnt = 0
for i in range(n - 1):
    if a[i + 1] < b[i]:
        cnt += 1
    else:
        ans *= pow(2, cnt, MOD)
        ans %= MOD
        cnt = 0
ans *= pow(2, cnt, MOD)
ans %= MOD      
print(ans)

Submission status: Wrong Answer

Solution code:
from math import factorial
from collections import deque
mod=10**9+7
n=int(raw_input())
a=[int(raw_input()) for _ in xrange(n)]
b=[int(raw_input()) for _ in xrange(n)]
d={}
a.sort()
b.sort()
ab=sorted(a+b)
for i in xrange(n):
    d[a[i]]="a"
    d[b[i]]="b"

stack=deque()
tmp=0
ans=1
for i in xrange(2*n):
    if len(stack)==0:
        ans=ans*factorial(tmp)%mod
        tmp=0
        stack.append(d[ab[i]])
        continue
    if d[ab[i]]=="a":
        if stack[-1]=="a":
            ans=ans*factorial(tmp)%mod
            tmp=0
            stack.append("a")
        else:
            tmp+=1
            stack.popleft()
    if d[ab[i]]=="b":
        if stack[-1]=="b":
            ans=ans*factorial(tmp)%mod
            tmp=0
            stack.append("b")
        else:
            tmp+=1
            stack.popleft()
ans=ans*factorial(tmp)%mod
print ans

Submission status: Wrong Answer

Solution code:
import math as m
import functools


def int_reverse(num):
    num_len = len(bin(num))-2
    f = 2**num_len-1
    return num ^ f

n = int(input())
A = [int(input()) for i in range(n)]
lsbs = [[i for i in range(int(m.log2(a))+1) if (a>>i)&1][0] for a in A]
nim = functools.reduce(lambda x,y:x^y, A)

cnt = 0
for lsb in reversed(sorted(lsbs)):
    if nim == 0:
        break
    if int(m.log2(nim)) == lsb:
        nim = int_reverse(nim)
        cnt += 1

ans = cnt if(nim == 0) else -1
print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heapify, heappush, heappop
n = input()
ps = [(int(raw_input()), i<n) for i in xrange(2*n)]
ps.sort()

cnt = 0
ans = 1
for p, v in ps:
    if v == 0:
        if cnt > 0:
            ans *= cnt
        cnt -= 1
    else:
        if cnt < 0:
            ans *= -cnt
        cnt += 1
print ans

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(input()) for _ in range(N)]
B = [int(input()) for _ in range(N)]
A.sort()
B.sort()
ans = [0] * N
mod = 10**9 + 7

for i in range(N):
    for j in range(N):
        ans[j-i] += (abs(A[i]-B[j])) % mod

print(ans.count(min(ans)))

Submission status: Time Limit Exceeded

Solution code:
from bisect import *
N=int(input())
A=[int(input()) for _ in range(N)]
B=[int(input()) for _ in range(N)]
A=sorted(A)
B=sorted(B)
ans=1
mod=10**9+7
for a,b in zip(A,B):
  if a>b:
    a,b=b,a
  ans*=(bisect_right(A,b)-bisect_left(A,a))
print(ans%mod)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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(c)
	c+=d
print(a%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
p=1
s=[0]*2
n=int(input())
q=sorted([[int(input()),i//n]for i in range(2*n)])
for i in q:
    if s[1-i[1]]==0:
        s[i[1]]+=1
    else:
        p*=s[1-i[1]]
        s[1-i[1]]-=1
print(p%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
p=1
s=[0]*2
n=int(input())
q=sorted([[int(input()),0]for i in range(n)]+[[int(input()),1]for i in range(n)])
for i in q:
    if s[(i[1]+1)%2]==0:
        s[i[1]]+=1
    else:
        p*=s[(i[1]+1)%2]
        s[(i[1]+1)%2]-=1
print(p%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
mod=10**9+7
X=[]
for i in range(n):
  X.append([int(input()),0])
for i in range(n):
  X.append([int(input()),1])
X.sort(key=lambda x:x[0])
ct=0
Y=[]
for a,b in X:
  if b==0:
    ct+=1
  else:
    ct-=1
  Y.append(ct)
ans=1
m,mm=0,1
key=0
for i in range(2*n):
  if Y[i]==0:
    ans*=mm
    m,mm=0,1
  elif m==0:
    m=1
    key=X[i][1]
  else:
    if X[i][1]==key:
      m+=1
      mm*=m
    else:
      m-=1
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
mod=10**9+7
X=[]
for i in range(n):
  X.append([int(input()),0])
for i in range(n):
  X.append([int(input()),1])
X.sort(key=lambda x:x[0])
ct=0
Y=[]
for a,b in X:
  if b==0:
    ct+=1
  else:
    ct-=1
  Y.append(ct)
ans=1
m,mm=0,1
key=0
for i in range(2*n):
  if Y[i]==0:
    ans*=mm
    m,mm=0,1
  elif m==0:
    m=1
    key=X[i][1]
  else:
    if X[i][1]==key:
      m+=1
      mm*=m
    else:
      m-=1
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
alist = list(reversed(sorted([int(input()) for _ in range(n)])))
blist = list(reversed(sorted([int(input()) for _ in range(n)])))
INF = pow(10, 9) + 7
a = alist.pop()
b = blist.pop()
aset, bset = 0, 0
ans = 1
while len(alist) > 0 or len(blist) > 0:
  if a < b:
    if bset > 0:
      ans *= bset
      bset -= 1
    else:
      aset += 1
    a = INF
    if len(alist) > 0:
      a = alist.pop()
  else:
    if aset > 0:
      ans *= aset
      aset -= 1
    else:
      bset += 1
    b = INF
    if len(blist) > 0:
      b = blist.pop()
print(ans % INF)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
alist = sorted([int(input()) for _ in range(n)])[::-1]
blist = sorted([int(input()) for _ in range(n)])[::-1]

a = alist.pop()
b = blist.pop()
aset, bset = 0, 0
ans = 1
while len(alist) > 0 or len(blist) > 0:
  if a < b:
    if bset > 0:
      ans *= bset
      bset -= 1
    else:
      aset += 1
    if alist:
      a = alist.pop()
    else:
      a = pow(10, 9) + 7
  else:
    if aset > 0:
      ans *= aset
      aset -= 1
    else:
      bset += 1
    if blist:
      b = blist.pop()
    else:
      b = pow(10, 9) + 7
print(ans % (pow(10, 9) + 7))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
alist = sorted([int(input()) for _ in range(n)])[::-1]
blist = sorted([int(input()) for _ in range(n)])[::-1]

a = alist.pop()
b = blist.pop()
aset, bset = [], []
ans = 1
while len(alist) > 0 or len(blist) > 0:
  if a < b:
    if bset:
      ans *= len(bset)
      del bset[0]
    else:
      aset.append(a)
    if alist:
      a = alist.pop()
    else:
      a = pow(10, 9) + 7
  else:
    if aset:
      ans *= len(aset)
      del aset[0]
    else:
      bset.append(b)
    if blist:
      b = blist.pop()
    else:
      b = pow(10, 9) + 7
print(ans % (pow(10, 9) + 7))

Submission status: Time Limit Exceeded

Solution code:
import bisect
N = int(input())
A = sorted(int(input()) for _ in range(N))
B = sorted(int(input()) for _ in range(N))
mod = 10**9 + 7
ans = 1
b = bisect.bisect
for i in range(N):
    if A[i] < B[i]:
        ans *= 1 + i - b(B[:i], A[i])
    else:
        ans *= 1 + i - b(A[:i], B[i])
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
n=int(input())
a=[[int(input()),1] for i in range(n)]+[[int(input()),-1] for i in range(n)]
a.sort()
c=0
b=a[0][1]
d=[]
for i,j in a:
    if j!=b and c*j<0:d.append(abs(c))
    c+=j
    b=j
ans=1
for i in d:
    ans*=math.factorial(i)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

time=input()

comp=[]
outl=[]

for i in range(time):
	comp.append(input())


for i in range(time):
	outl.append(input())

length=[]

for i in range(time):
	com_length=[]
	for j in range(time):
		com_length.append(math.fabs(comp[i]-outl[j]))
	length.append(com_length)

count=1

for i in range(time):
	for j in range(time-i-1):
		if length[i][i]+length[i+j+1][i+j+1]==length[i][i+j+1]+length[i+j+1][i]:
			count+=1

print count

Submission status: Time Limit Exceeded

Solution code:
import itertools
n=int(input())
a=[int(input()) for i in range(n)]
b=[int(input()) for i in range(n)]
length=[]
for per in itertools.permutations(range(n)):
    s=0
    for idx_a,idx_b in enumerate(per):
        s+=abs(a[idx_a]-b[idx_b])
    length.append(s)
length.sort()
print(length.count(length[0]))

Submission status: Accepted

Solution code:
n = int(input())
mod = pow(10, 9) + 7
x = []
for i in range(2 * n):
    if i < n:
        x.append([int(input()), 0])
    else:
        x.append([int(input()), 1])
x.sort()
ans, cnt0, cnt1 = 1, 0, 0
for i in range(2 * n):
    if x[i][1] == 0:
        if cnt1 >= 1:
            ans *= cnt1
            ans %= mod
            cnt1 -= 1
        else:
            cnt0 += 1
    else:
        if cnt0 >= 1:
            ans *= cnt0
            ans %= mod
            cnt0 -= 1
        else:
            cnt1 += 1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
M = 10**9+7
L = []
for _ in range(n):
  a = int(input())
  L.append((a, 1))
for _ in range(n):
  b = int(input())
  L.append((b, 0))
L.sort()
C = [0, 0]
ans = 1
for d, f in L:
  if C[f^1]:
    ans *= C[f^1]
    ans %= M
    C[f^1] -= 1
  else:
    C[f] += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
a = [(int(input()),1) for i in range(n)]
a += [(int(input()),2) for i in range(n)]
a.sort()
b = list(zip(*a))[1]
mod = 10**9+7
ans = 1
stack = []
for i in range(2*n):
  if not stack or stack[-1] == b[i]:
    stack.append(b[i])
  else:
    ans *= len(stack)
    ans %= mod
    stack.pop()
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())

white = 0  # 前者
black = 0  # 後者

ans = 1

mod = 10**9 + 7
que = []
for i in range(N):
    x = int(input())
    que.append((x, 0))
for i in range(N):
    y = int(input())
    que.append((y, 1))
que.sort(reverse=True)
for i in range(2*N):
    value, index = que[i]
    if index == 0:
        white += 1
        if black > 0:
            ans *= black
            ans %= mod
            black -= 1
            white -= 1
    else:
        black += 1
        if white > 0:
            ans *= white
            ans %= mod
            white -= 1
            black -= 1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = [(int(input()),0) for i in range(n)]
b = [(int(input()),1) for i in range(n)]
diff = 0
ans = 1
mod = 10 ** 9 + 7
ab = sorted(a+b)
prev = 0
for x,now in ab:
  if prev != now:
    diff = -diff
  if diff > 0:
    ans *= diff
    ans %= mod
  diff -= 1
  prev = now
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
mod = 10 ** 9 + 7

N = int(input())
AB = []
for _ in range(N):
    AB.append((int(input()), 0))
for _ in range(N):
    AB.append((int(input()), 1))
AB.sort(reverse=True)

ans = 1
Aset = 0
Bset = 0

while AB:
    _, x = AB.pop()
    if x:
        if Bset:
            ans *= Bset
            ans %= mod
            Bset -= 1
        else:
            Aset += 1
    else:
        if Aset:
            ans *= Aset
            ans %= mod
            Aset -= 1
        else:
            Bset += 1

print(ans)

Submission status: Accepted

Solution code:
# A - 1D Matching
def calculate_cables_length(x: int, y: int, total: int) -> tuple:
    MOD = 10 ** 9 + 7
    if y:
        total = (total * y) % MOD
        y -= 1
    else:
        x += 1
    return x, y, total


def main():
    # sort A, B and the lines between A, B shouldn't cross
    # cross <-> not min distance
    N, *AB = map(int, open(0))
    C = [(i, 1) for i in AB[:N]] + [(i, 0) for i in AB[N:]]
    C.sort()
    ans, a, b = 1, 0, 0
    for i, t in C:
        if t:  # laptop
            a, b, ans = calculate_cables_length(a, b, ans)
        else:  # power sources
            b, a, ans = calculate_cables_length(b, a, ans)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())

mod = int(1e9+7)

A = []
for _ in range(N):
  A.append([int(input()),1])
for _ in range(N):
  A.append([int(input()),2])
A.sort()

ans = 1
ca,cb = 0,0
for a in A:
  if a[1] == 1:
    if cb == 0:
      ca += 1
    else:
      ans = ans * cb % mod
      cb -= 1      
  else:
    if ca == 0:
      cb += 1
    else:
      ans = ans * ca % mod
      ca -= 1
    
print(ans)

Submission status: Accepted

Solution code:
import sys
from operator import itemgetter

read = sys.stdin.read

N, *ab = map(int, read().split())
mod = 10 ** 9 + 7
ab = list(zip(ab, [0] * N + [1] * N))
ab.sort(key=itemgetter(0))

remain_pc = 0
remain_power = 0
answer = 1

for x, p in ab:
    if p == 0:
        if remain_power == 0:
            remain_pc += 1
            continue
        answer *= remain_power
        remain_power -= 1
    else:
        if remain_pc == 0:
            remain_power += 1
            continue
        answer *= remain_pc
        remain_pc -= 1
    answer %= mod

print(answer)

Submission status: Accepted

Solution code:
import sys
from operator import itemgetter

read = sys.stdin.read

N, *ab = map(int, read().split())
mod = 10 ** 9 + 7
ab = list(zip(ab[:N], [0] * N)) + list(zip(ab[N:], [1] * N))
ab.sort(key=itemgetter(0))

remain_pc = 0
remain_power = 0
answer = 1

for x, p in ab:
    if p == 0:
        if remain_power == 0:
            remain_pc += 1
            continue
        answer *= remain_power
        remain_power -= 1
    else:
        if remain_pc == 0:
            remain_power += 1
            continue
        answer *= remain_pc
        remain_pc -= 1
    answer %= mod

print(answer)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read

N, *ab = map(int, read().split())
mod = 10 ** 9 + 7
ab = list(zip(ab[:N], [0] * N)) + list(zip(ab[N:], [1] * N))
ab.sort()

remain_pc = 0
remain_power = 0
answer = 1

for x, p in ab:
    if p == 0:
        if remain_power == 0:
            remain_pc += 1
            continue
        answer *= remain_power
        remain_power -= 1
    else:
        if remain_pc == 0:
            remain_power += 1
            continue
        answer *= remain_pc
        remain_pc -= 1
    answer %= mod

print(answer)

Submission status: Accepted

Solution code:
mod = 1000000007
N = int(input())
A = []
B = []
for i in range(N):
	A.append(int(input()))
for i in range(N):
	B.append(int(input()))

A.sort()
B.sort()
A.append(mod)
B.append(mod)

ans = 1
a = 0
b = 0

while a != N or b != N:
	if A[a] < B[b]:
		a += 1
		if a > b:
			ans = ans * (a - b) % mod
	else:
		b += 1
		if b > a:
			ans = ans * (b - a) % mod
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getlist():
    return list(map(int, input().split()))
import math
import heapq
from collections import defaultdict, Counter, deque
MOD = 10**9 + 7
INF = 10**15


def main():
    n = getN()
    line = []
    for i in range(n):
        line.append((getN(), "P"))
    for i in range(n):
        line.append((getN(), "C"))

    line.sort()
    pc = 0
    cn = 0
    ans = 1
    # print(line)
    for point in line:
        pt, st = point
        if st == "P":
            if pc == 0 and cn != 0:
                ans *= cn
                ans %= MOD
                cn -= 1
            else:
                pc += 1

        else:
            if cn == 0 and pc != 0:
                ans *= pc
                ans %= MOD
                pc-=1
            else:
                cn += 1

    print(ans)



if __name__ == '__main__':
    main()

"""
9999
3

2916
"""

Submission status: Accepted

Solution code:
n = int(input())
a = [[int(input()),0] for _ in range(n)]
b = [[int(input()),1] for _ in range(n)]
mod = 10**9 + 7
ab = sorted(a+b)
ans = 1
now = [0,0]
for x,y in ab:
    if now[1-y] > 0:
        ans *= now[1-y]
        ans %= mod
        now[1-y] -= 1
    else:
        now[y] += 1

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=[int(input())for _ in range(n)]+[10**9]
b=[int(input())for _ in range(n)]+[10**9]
a.sort(reverse=1)
b.sort(reverse=1)
aa=0
bb=0
if a[-1]>b[-1]:
  bb=1
  b.pop()
else:
  aa=1
  a.pop()
ans=1
while len(a)!=1 or len(b)!=1:
  if a[-1]>b[-1]:
    bb+=1
    b.pop()
  else:
    aa+=1
    a.pop()
  if aa*bb:
    ans*=max(aa,bb)
    ans%=10**9+7
    aa-=1
    bb-=1
print(ans)

Submission status: Accepted

Solution code:

N = int(input())
mod = 10**9+7

lis = []

for i in range(N):

    a = int(input())
    lis.append([a,1])

for i in range(N):

    b = int(input())
    lis.append([b,-1])

ans = 1

lis.sort()

now = 0
for i in range(2*N):

    nex = lis[i][1]

    if nex == 1:

        if now >= 0:
            now += 1
        else:
            ans *= abs(now)
            now += 1

    else:

        if now <= 0:
            now -= 1
        else:
            ans *= abs(now)
            now -= 1

    ans %= mod

print (ans)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
def mod_fact(n):
  ret = 1
  for i in range(1, n + 1):
    ret = (ret * i) % MOD
  return ret

n = int(input())
AB = []
for i in range(2 * n):
  AB.append((int(input()), i//n)) # i//n: 0=a, 1=b

AB.sort()

a, b = 0, 0
ans = 1
for i, j in AB:
  if j == 0:
    if b == 0:
      a += 1
    else:
      ans = (ans * b) % MOD
      b -= 1
  else:
    if a == 0:
      b += 1
    else:
      ans = (ans * a) % MOD 
      a -= 1
print(ans % MOD)

Submission status: Accepted

Solution code:
def main():
    from bisect import bisect_left as bl
    n = int(input())
    a = [int(input()) for _ in [0]*n]
    b = [int(input()) for _ in [0]*n]
    a.sort()
    b.sort()
    for i in range(n):
        if a[i] > b[i]:
            a[i], b[i] = b[i], a[i]
    # print(a)
    # print(b)
    mod = 10**9+7
    ans = 1
    for i in range(n):
        ans = ans*(i+1-bl(b, a[i])) % mod
    print(ans)


main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

mod = 10**9+7

N = int(input())
A = [int(input()) for _ in range(N)]
B = [int(input()) for _ in range(N)]

A.sort(reverse=True)
B.sort(reverse=True)

P = []
while A or B:
    if len(A) == 0:
        b = B.pop()
        P.append(0)
    elif len(B) == 0:
        a = A.pop()
        P.append(1)
    else:
        a = A.pop()
        b = B.pop()
        if a > b:
            P.append(0)
            A.append(a)
        else:
            P.append(1)
            B.append(b)

a = 0
b = 0
ans = 1
for p in P:
    if p == 0:
        if b > 0:
            ans = ans * b % mod
            b -= 1
        else:
            a += 1
    else:
        if a > 0:
            ans = ans * a % mod
            a -= 1
        else:
            b += 1
print(ans)