Problem:


Score : 1000 points

Problem Statement

Snuke arranged N colorful balls in a row.
The i-th ball from the left has color c_i and weight w_i.

He can rearrange the balls by performing the following two operations any number of times, in any order:

Operation 1: Select two balls with the same color. If the total weight of these balls is at most X, swap the positions of these balls.

Operation 2: Select two balls with different colors. If the total weight of these balls is at most Y, swap the positions of these balls.

How many different sequences of colors of balls can be obtained? Find the count modulo 10^9 + 7.

Constraints

1 ≤ N ≤ 2 × 10^5

1 ≤ X, Y ≤ 10^9

1 ≤ c_i ≤ N

1 ≤ w_i ≤ 10^9

X, Y, c_i, w_i are all integers.

Input

Input is given from Standard Input in the following format:

N X Y
c_1 w_1
:
c_N w_N

Output

Print the answer.

Sample Input 1

4 7 3
3 2
4 3
2 1
4 4

Sample Output 1

2

The sequence of colors (2,4,3,4) can be obtained by swapping the positions of the first and third balls by operation 2.

It is also possible to swap the positions of the second and fourth balls by operation 1, but it does not affect the sequence of colors.

Sample Input 2

1 1 1
1 1

Sample Output 2

1

Sample Input 3

21 77 68
16 73
16 99
19 66
2 87
2 16
7 17
10 36
10 68
2 38
10 74
13 55
21 21
3 7
12 41
13 88
18 6
2 12
13 87
1 9
2 27
13 15

Sample Output 3

129729600



Sample input:
4 7 3
3 2
4 3
2 1
4 4


Sample output:
2

Submission status: Wrong Answer

Solution code:
class UnionFindVerSize():
    def __init__(self, N):
        self._parent = [n for n in range(0, N)]
        self._size = [1] * N

    def find_root(self, x):
        if self._parent[x] == x: return x
        self._parent[x] = self.find_root(self._parent[x])
        return self._parent[x]

    def unite(self, x, y):
        gx = self.find_root(x)
        gy = self.find_root(y)
        if gx == gy: return

        if self._size[gx] < self._size[gy]:
            self._parent[gx] = gy
            self._size[gy] += self._size[gx]
        else:
            self._parent[gy] = gx
            self._size[gx] += self._size[gy]

    def get_size(self, x):
        return self._size[self.find_root(x)]

    def is_same_group(self, x, y):
        return self.find_root(x) == self.find_root(y)

    def calc_group_num(self):
        N = len(self._parent)
        ans = 0
        for i in range(N):
            if self.find_root(i) == i:
                ans += 1
        return ans

mod = 10**9+7 #出力の制限
N = 2*10**5
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

import sys,bisect

input=sys.stdin.buffer.readline

N,X,Y=map(int,input().split())
cball=[[] for i in range(N)]
ball=[]
color=[-1]*N
for i in range(N):
    c,w=map(int,input().split())
    ball.append((w,c-1,i))
    cball[c-1].append((w,i))
    color[i]=c-1

for i in range(N):
    cball[i].sort()
ball.sort()

if N==1:
    print(1)
    exit()

cmin=[10**20 for i in range(N)]
for i in range(N):
    if cball[i]:
        cmin[i]=min(cball[i][j][0] for j in range(len(cball[i])))

_cmine1=[cmin[i] for i in range(N)]
_cmine2=[cmin[i] for i in range(N)]
for i in range(1,N):
    _cmine1[i]=min(_cmine1[i],_cmine1[i-1])
for i in range(N-2,-1,-1):
    _cmine2[i]=min(_cmine2[i],_cmine2[i+1])
cmine=[0]*N
cmine[0]=_cmine2[1]
cmine[-1]=_cmine1[N-2]
for i in range(1,N-1):
    cmine[i]=min(_cmine1[i-1],_cmine2[i+1])

M=min(ball)
special=-1
for i in range(N):
    if cmine[i]!=M[0]:
        special=i

uf=UnionFindVerSize(N)
for i in range(N):
    if i!=special:
        for w,id in cball[i]:
            if Y>=w+M[0]:
                uf.unite(id,M[2])

if special!=-1:
    for i in range(len(cball[special])):
        if cmine[special]+cball[special][i][0]<=Y:
            uf.unite(cball[special][i][1],M[2])
        if M[0]+cball[special][i][0]<=X:
            uf.unite(cball[special][i][1],M[2])

connect={}
for i in range(N):
    root=uf.find_root(i)
    if root not in connect:
        connect[root]=[]
    connect[root].append(i)

ans=1
for root in connect:
    cc={}
    for i in connect[root]:
        if color[i] not in cc:
            cc[color[i]]=0
        cc[color[i]]+=1
    size=len(connect[root])
    for C in cc:
        ans*=g2[cc[C]]
        ans%=mod
    ans*=g1[size]
    ans%=mod

print(ans)

Submission status: Wrong Answer

Solution code:
class UnionFindVerSize():
    def __init__(self, N):
        self._parent = [n for n in range(0, N)]
        self._size = [1] * N

    def find_root(self, x):
        if self._parent[x] == x: return x
        self._parent[x] = self.find_root(self._parent[x])
        return self._parent[x]

    def unite(self, x, y):
        gx = self.find_root(x)
        gy = self.find_root(y)
        if gx == gy: return

        if self._size[gx] < self._size[gy]:
            self._parent[gx] = gy
            self._size[gy] += self._size[gx]
        else:
            self._parent[gy] = gx
            self._size[gx] += self._size[gy]

    def get_size(self, x):
        return self._size[self.find_root(x)]

    def is_same_group(self, x, y):
        return self.find_root(x) == self.find_root(y)

    def calc_group_num(self):
        N = len(self._parent)
        ans = 0
        for i in range(N):
            if self.find_root(i) == i:
                ans += 1
        return ans

mod = 10**9+7 #出力の制限
N = 2*10**5
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

import sys,bisect

input=sys.stdin.buffer.readline

N,X,Y=map(int,input().split())
cball=[[] for i in range(N)]
ball=[]
color=[-1]*N
for i in range(N):
    c,w=map(int,input().split())
    ball.append((w,c-1,i))
    cball[c-1].append((w,i))
    color[i]=c-1

for i in range(N):
    cball[i].sort()
ball.sort()

if N==1:
    print(1)
    exit()

cmin=[10**20 for i in range(N)]
for i in range(N):
    if cball[i]:
        cmin[i]=min(cball[i][j][0] for j in range(len(cball[i])))

_cmine1=[cmin[i] for i in range(N)]
_cmine2=[cmin[i] for i in range(N)]
for i in range(1,N):
    _cmine1[i]=min(_cmine1[i],_cmine1[i-1])
for i in range(N-2,-1,-1):
    _cmine2[i]=min(_cmine2[i],_cmine2[i+1])
cmine=[0]*N
cmine[0]=_cmine2[1]
cmine[-1]=_cmine1[N-2]
for i in range(1,N-1):
    cmine[i]=min(_cmine1[i-1],_cmine2[i+1])

uf=UnionFindVerSize(N)
for i in range(N):
    n=len(cball[i])
    for j in range(1,n):
        id=bisect.bisect_right(cball[i],(X-cball[i][j][0],10**20))
        if id!=0:
            num1=cball[i][0][1]
            num2=cball[i][j][1]
            uf.unite(num1,num2)
        if cball[i][j][0]+cmine[i]<=Y:
            num1=cball[i][j-1][1]
            num2=cball[i][j][1]
            uf.unite(num1,num2)



for i in range(1,N):
    id=bisect.bisect_right(ball,(Y-ball[i][0],10**20))
    if id!=0:
        num1=ball[0][2]
        num2=ball[i][2]
        uf.unite(num1,num2)

connect={}
for i in range(N):
    root=uf.find_root(i)
    if root not in connect:
        connect[root]=[]
    connect[root].append(i)

ans=1
for root in connect:
    cc={}
    for i in connect[root]:
        if color[i] not in cc:
            cc[color[i]]=0
        cc[color[i]]+=1
    size=len(connect[root])
    for C in cc:
        ans*=g2[cc[C]]
        ans%=mod
    ans*=g1[size]
    ans%=mod

print(ans)

Submission status: Wrong Answer

Solution code:
class UnionFindVerSize():
    def __init__(self, N):
        self._parent = [n for n in range(0, N)]
        self._size = [1] * N

    def find_root(self, x):
        if self._parent[x] == x: return x
        self._parent[x] = self.find_root(self._parent[x])
        return self._parent[x]

    def unite(self, x, y):
        gx = self.find_root(x)
        gy = self.find_root(y)
        if gx == gy: return

        if self._size[gx] < self._size[gy]:
            self._parent[gx] = gy
            self._size[gy] += self._size[gx]
        else:
            self._parent[gy] = gx
            self._size[gx] += self._size[gy]

    def get_size(self, x):
        return self._size[self.find_root(x)]

    def is_same_group(self, x, y):
        return self.find_root(x) == self.find_root(y)

    def calc_group_num(self):
        N = len(self._parent)
        ans = 0
        for i in range(N):
            if self.find_root(i) == i:
                ans += 1
        return ans

mod = 10**9+7 #出力の制限
N = 2*10**5
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

import sys,bisect

input=sys.stdin.buffer.readline

N,X,Y=map(int,input().split())
cball=[[] for i in range(N)]
ball=[]
color=[-1]*N
for i in range(N):
    c,w=map(int,input().split())
    ball.append((w,c-1,i))
    cball[c-1].append((w,i))
    color[i]=c-1

for i in range(N):
    cball[i].sort()
ball.sort()

if N==1:
    print(1)
    exit()

cmin=[10**20 for i in range(N)]
for i in range(N):
    if cball[i]:
        cmin[i]=min(cball[i][j][0] for j in range(len(cball[i])))

_cmine1=[cmin[i] for i in range(N)]
_cmine2=[cmin[i] for i in range(N)]
for i in range(1,N):
    _cmine1[i]=min(_cmine1[i],_cmine1[i-1])
for i in range(N-2,-1,-1):
    _cmine2[i]=min(_cmine2[i],_cmine2[i+1])
cmine=[0]*N
cmine[0]=_cmine2[1]
cmine[-1]=_cmine1[N-2]
for i in range(1,N-1):
    cmine[i]=min(_cmine1[i-1],_cmine2[i+1])

uf=UnionFindVerSize(N)
for i in range(N):
    n=len(cball[i])
    for j in range(1,n):
        id=bisect.bisect_right(cball[i],(X-cball[i][j][0],10**20))
        if i==1:
            if id!=0:
                for k in range(id):
                    num1=cball[i][k][1]
                    num2=cball[i][j][1]
                    uf.unite(num1,num2)
        if id!=0:
            num1=cball[i][id-1][1]
            num2=cball[i][j][1]
            uf.unite(num1,num2)
        if cball[i][j][0]+cmine[i]<=Y:
            num1=cball[i][j-1][1]
            num2=cball[i][j][1]
            uf.unite(num1,num2)



for i in range(1,N):
    id=bisect.bisect_right(ball,(Y-ball[i][0],10**20))
    if i==1:
        if id!=0:
            for j in range(id):
                num1=ball[j][2]
                num2=ball[i][2]
                uf.unite(num1,num2)
    if id!=0:
        num1=ball[id-1][2]
        num2=ball[i][2]
        uf.unite(num1,num2)

connect={}
for i in range(N):
    root=uf.find_root(i)
    if root not in connect:
        connect[root]=[]
    connect[root].append(i)

ans=1
for root in connect:
    cc={}
    for i in connect[root]:
        if color[i] not in cc:
            cc[color[i]]=0
        cc[color[i]]+=1
    size=len(connect[root])
    for C in cc:
        ans*=g2[cc[C]]
        ans%=mod
    ans*=g1[size]
    ans%=mod

print(ans)

Submission status: Wrong Answer

Solution code:
class UnionFindVerSize():
    def __init__(self, N):
        self._parent = [n for n in range(0, N)]
        self._size = [1] * N

    def find_root(self, x):
        if self._parent[x] == x: return x
        self._parent[x] = self.find_root(self._parent[x])
        return self._parent[x]

    def unite(self, x, y):
        gx = self.find_root(x)
        gy = self.find_root(y)
        if gx == gy: return

        if self._size[gx] < self._size[gy]:
            self._parent[gx] = gy
            self._size[gy] += self._size[gx]
        else:
            self._parent[gy] = gx
            self._size[gx] += self._size[gy]

    def get_size(self, x):
        return self._size[self.find_root(x)]

    def is_same_group(self, x, y):
        return self.find_root(x) == self.find_root(y)

    def calc_group_num(self):
        N = len(self._parent)
        ans = 0
        for i in range(N):
            if self.find_root(i) == i:
                ans += 1
        return ans

mod = 10**9+7 #出力の制限
N = 2*10**5
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

import sys,bisect

input=sys.stdin.buffer.readline

N,X,Y=map(int,input().split())
cball=[[] for i in range(N)]
ball=[]
color=[-1]*N
for i in range(N):
    c,w=map(int,input().split())
    ball.append((w,c-1,i))
    cball[c-1].append((w,i))
    color[i]=c-1

for i in range(N):
    cball[i].sort()
ball.sort()

if N==1:
    print(1)
    exit()

cmin=[10**20 for i in range(N)]
for i in range(N):
    if cball[i]:
        cmin[i]=min(cball[i][j][0] for j in range(len(cball[i])))

_cmine1=[cmin[i] for i in range(N)]
_cmine2=[cmin[i] for i in range(N)]
for i in range(1,N):
    _cmine1[i]=min(_cmine1[i],_cmine1[i-1])
for i in range(N-2,-1,-1):
    _cmine2[i]=min(_cmine2[i],_cmine2[i+1])
cmine=[0]*N
cmine[0]=_cmine2[1]
cmine[-1]=_cmine1[N-2]
for i in range(1,N-1):
    cmine[i]=min(_cmine1[i-1],_cmine2[i+1])

uf=UnionFindVerSize(N)
for i in range(N):
    n=len(cball[i])
    for j in range(1,n):
        id=bisect.bisect_right(cball[i],(X-cball[i][j][0],10**20))
        if id!=0:
            num1=cball[i][id-1][1]
            num2=cball[i][j][1]
            uf.unite(num1,num2)
        if cball[i][j][0]+cmine[i]<=Y:
            num1=cball[i][j-1][1]
            num2=cball[i][j][1]
            uf.unite(num1,num2)



for i in range(1,N):
    id=bisect.bisect_right(ball,(Y-ball[i][0],10**20))
    if i==1:
        if id!=0:
            for j in range(id):
                num1=ball[j][2]
                num2=ball[i][2]
                uf.unite(num1,num2)
    if id!=0:
        num1=ball[id-1][2]
        num2=ball[i][2]
        uf.unite(num1,num2)

connect={}
for i in range(N):
    root=uf.find_root(i)
    if root not in connect:
        connect[root]=[]
    connect[root].append(i)

ans=1
for root in connect:
    cc={}
    for i in connect[root]:
        if color[i] not in cc:
            cc[color[i]]=0
        cc[color[i]]+=1
    size=len(connect[root])
    for C in cc:
        ans*=g2[cc[C]]
        ans%=mod
    ans*=g1[size]
    ans%=mod

print(ans)

Submission status: Wrong Answer

Solution code:
class Combination:
    def __init__(self, n_max, mod=10**9+7):
        # O(n_max + log(mod))
        self.mod = mod
        f = 1
        self.fac = fac = [f]
        for i in range(1, n_max+1):
            f = f * i % mod
            fac.append(f)
        f = pow(f, mod-2, mod)
        self.facinv = facinv = [f]
        for i in range(n_max, 0, -1):
            f = f * i % mod
            facinv.append(f)
        facinv.reverse()

import sys
N, X, Y = map(int, input().split())
CW = list(map(int, sys.stdin.read().split()))
C, W = CW[::2], CW[1::2]
mod = 10**9+7
comb = Combination(N+1)

Color_min = [10**10] * (N+1)
Color_argmin = [-1] * (N+1)
Color_2nd_min = [10**10] * (N+1)
all_min = min(W)
for i, (c, w) in enumerate(zip(C, W)):
    if Color_2nd_min[c] > w:
        Color_2nd_min[c] = w
        if Color_min[c] > w:
            Color_min[c], Color_2nd_min[c] = Color_2nd_min[c], Color_min[c]
            Color_argmin[c] = i
In_cnt = [0] * (N+1)
Out_flag= [0] * (N+1)
for i, (c, w) in enumerate(zip(C, W)):
    if (i != Color_argmin[c] and Color_min[c] + w <= X) \
     or (Color_2nd_min[c] + w <= X) \
     or all_min + w <= Y:
        In_cnt[c] += 1
    if all_min + w <= Y:
        Out_flag[c] = 1
sum_in_out = 0
ans = 1
for c, f in zip(In_cnt, Out_flag):
    if f:
        sum_in_out += c
        ans = ans * comb.facinv[c] % mod
ans = ans * comb.fac[sum_in_out] % mod
#print(In_cnt)
#print(Out_flag)
print(ans)

Submission status: Wrong Answer

Solution code:
class Combination:
    def __init__(self, n_max, mod=10**9+7):
        # O(n_max + log(mod))
        self.mod = mod
        f = 1
        self.fac = fac = [f]
        for i in range(1, n_max+1):
            f = f * i % mod
            fac.append(f)
        f = pow(f, mod-2, mod)
        self.facinv = facinv = [f]
        for i in range(n_max, 0, -1):
            f = f * i % mod
            facinv.append(f)
        facinv.reverse()

import sys
N, X, Y = map(int, input().split())
CW = list(map(int, sys.stdin.read().split()))
C, W = CW[::2], CW[1::2]
mod = 10**9+7
comb = Combination(N+1)

Color_min = [10**10] * (N+1)
all_min = min(W)
for c, w in zip(C, W):
    if Color_min[c] > w:
        Color_min[c] = w
In_cnt = [0] * (N+1)
Out_flag= [0] * (N+1)
for c, w in zip(C, W):
    if Color_min[c] + w <= X or all_min + w <= Y:
        In_cnt[c] += 1
    if all_min + w <= Y:
        Out_flag[c] = 1
sum_in_out = 0
ans = 1
for c, f in zip(In_cnt, Out_flag):
    if f:
        sum_in_out += c
        ans = ans * comb.facinv[c] % mod
ans = ans * comb.fac[sum_in_out] % mod
#print(In_cnt)
#print(Out_flag)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

mod = 10**9+7
rng = 200100
fctr = [1]
finv = [1]
for i in range(1,rng):
  fctr.append(fctr[-1]*i%mod)
for i in range(1,rng):
  finv.append(pow(fctr[i],mod-2,mod))
def cmb(n,k):
  if n<0 or k<0:
    return 0
  else:
    return fctr[n]*finv[n-k]*finv[k]%mod

import sys
input = sys.stdin.readline
n,X,Y = map(int,input().split())
cw = [list(map(int,input().split())) for i in range(n)]
cw.sort()
mnls = []
graph = [[] for i in range(n)]
notmn = set()
for i in range(n):
  if i == 0 or cw[i-1][0] != cw[i][0]:
    mnls.append((i,cw[i][0],cw[i][1]))
  else:
    if cw[i][1]+mnls[-1][2] <= X:
      graph[i].append(mnls[-1][0])
      graph[mnls[-1][0]].append(i)
    else:
      notmn.add(i)
mnls.sort(key = lambda x:x[2])
for i,x in enumerate(mnls):
  if i == 0:
    continue
  if x[2]+mnls[0][2] <= Y:
    graph[x[0]].append(mnls[0][0])
    graph[mnls[0][0]].append(x[0])
for i in notmn:
  if mnls[0][1] != cw[i][0]:
    if mnls[0][2]+cw[i][1] <= Y:
      graph[i].append(mnls[0][0])
      graph[mnls[0][0]].append(i)
  else:
    if len(mnls) >= 2 and mnls[1][1]+cw[i][0] <= Y:
      graph[i].append(mnls[1][0])
      graph[mnls[1][0]].append(i)
vis = [0 for i in range(n)]
ans = 1
for i in range(n):
  if vis[i]:
    continue
  vis[i] = 1
  stack = [i]
  color = defaultdict(int)
  while stack:
    x = stack.pop()
    color[cw[x][0]] += 1
    for y in graph[x]:
      if vis[y] == 0:
        vis[y] = 1
        stack.append(y)
  sm = sum(color.values())
  for v in color.values():
    ans = ans*cmb(sm,v)%mod
    sm -= v
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

mod = 10**9+7
rng = 200100
fctr = [1]
finv = [1]
for i in range(1,rng):
  fctr.append(fctr[-1]*i%mod)
for i in range(1,rng):
  finv.append(pow(fctr[i],mod-2,mod))
def cmb(n,k):
  if n<0 or k<0:
    return 0
  else:
    return fctr[n]*finv[n-k]*finv[k]%mod

import sys
input = sys.stdin.readline
n,X,Y = map(int,input().split())
cw = [list(map(int,input().split())) for i in range(n)]
cw.sort()
mnls = []
graph = [[] for i in range(n)]
notmn = set()
for i in range(n):
  if i == 0 or cw[i-1][0] != cw[i][0]:
    mnls.append((i,cw[i][0],cw[i][1]))
  else:
    if cw[i][1]+mnls[-1][2] <= X:
      graph[i].append(mnls[-1][0])
      graph[mnls[-1][0]].append(i)
    else:
      notmn.add(i)
mnls.sort(key = lambda x:x[2])
for i,x in enumerate(mnls):
  if i == 0:
    continue
  if x[2]+mnls[0][2] <= Y:
    graph[x[0]].append(mnls[0][0])
    graph[mnls[0][0]].append(x[0])
for i in notmn:
  if mnls[0][1] != cw[i][0]:
    if mnls[0][2]+cw[i][1] <= Y:
      graph[i].append(mnls[0][0])
      graph[mnls[0][0]].append(i)
  else:
    if len(mnls) >= 2 and mnls[1][1] != cw[i][0]:
      graph[i].append(mnls[1][0])
      graph[mnls[1][0]].append(i)
vis = [0 for i in range(n)]
ans = 1
for i in range(n):
  if vis[i]:
    continue
  vis[i] = 1
  stack = [i]
  color = defaultdict(int)
  while stack:
    x = stack.pop()
    color[cw[x][0]] += 1
    for y in graph[x]:
      if vis[y] == 0:
        vis[y] = 1
        stack.append(y)
  sm = sum(color.values())
  for v in color.values():
    ans = ans*cmb(sm,v)%mod
    sm -= v
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

mod = 10**9+7
rng = 200100
fctr = [1]
finv = [1]
for i in range(1,rng):
  fctr.append(fctr[-1]*i%mod)
for i in range(1,rng):
  finv.append(pow(fctr[i],mod-2,mod))
def cmb(n,k):
  if n<0 or k<0:
    return 0
  else:
    return fctr[n]*finv[n-k]*finv[k]%mod

import sys
input = sys.stdin.readline
n,X,Y = map(int,input().split())
cw = [list(map(int,input().split())) for i in range(n)]
cw.sort()
mnls = []
graph = [[] for i in range(n)]
notmn = set()
for i in range(n):
  if i == 0 or cw[i-1][0] != cw[i][0]:
    mnls.append((i,cw[i][0],cw[i][1]))
  else:
    if cw[i][1]+mnls[-1][2] <= X:
      graph[i].append(mnls[-1][0])
      graph[mnls[-1][0]].append(i)
    else:
      notmn.add(i)
mnls.sort(key = lambda x:x[2])
for i,x in enumerate(mnls):
  if i == 0:
    continue
  if x[2]+mnls[0][2] <= Y:
    graph[x[0]].append(mnls[0][0])
    graph[mnls[0][0]].append(x[0])
for i in notmn:
  if mnls[0][1] != cw[i][0] and mnls[0][2]+cw[i][1] <= Y:
    graph[i].append(mnls[0][0])
    graph[mnls[0][0]].append(i)
vis = [0 for i in range(n)]
ans = 1
for i in range(n):
  if vis[i]:
    continue
  vis[i] = 1
  stack = [i]
  color = defaultdict(int)
  while stack:
    x = stack.pop()
    color[cw[x][0]] += 1
    for y in graph[x]:
      if vis[y] == 0:
        vis[y] = 1
        stack.append(y)
  sm = sum(color.values())
  for v in color.values():
    ans = ans*cmb(sm,v)%mod
    sm -= v
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

mod = 10**9+7
rng = 200100
fctr = [1]
finv = [1]
for i in range(1,rng):
  fctr.append(fctr[-1]*i%mod)
for i in range(1,rng):
  finv.append(pow(fctr[i],mod-2,mod))
def cmb(n,k):
  if n<0 or k<0:
    return 0
  else:
    return fctr[n]*finv[n-k]*finv[k]%mod

import sys
input = sys.stdin.readline
n,X,Y = map(int,input().split())
cw = [list(map(int,input().split())) for i in range(n)]
cw.sort()
mnls = []
graph = [[] for i in range(n)]
notmn = set()
for i in range(n):
  if i == 0 or cw[i-1][0] != cw[i][0]:
    mnls.append((i,cw[i][0],cw[i][1]))
  else:
    if cw[i][1]+mnls[-1][2] <= X:
      graph[i].append(mnls[-1][0])
      graph[mnls[-1][0]].append(i)
    else:
      notmn.add(i)
mnls.sort(key = lambda x:x[2])
for i,x in enumerate(mnls):
  if i == 0:
    continue
  if x[2]+mnls[0][2] <= Y:
    graph[x[0]].append(mnls[0][0])
    graph[mnls[0][0]].append(x[0])
for i in notmn:
  if mnls[0][2]+cw[i][1] <= Y:
    graph[i].append(mnls[0][0])
    graph[mnls[0][0]].append(i)
vis = [0 for i in range(n)]
ans = 1
for i in range(n):
  if vis[i]:
    continue
  vis[i] = 1
  stack = [i]
  color = defaultdict(int)
  while stack:
    x = stack.pop()
    color[cw[x][0]] += 1
    for y in graph[x]:
      if vis[y] == 0:
        vis[y] = 1
        stack.append(y)
  sm = sum(color.values())
  for v in color.values():
    ans = ans*cmb(sm,v)%mod
    sm -= v
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
n,x,y=map(int,input().split())
mod=10**9+7
f=[1]
for i in range(1,n+7):f.append(f[-1]*i%mod)
wc=[list(map(int,input().split()))[::-1]for _ in range(n)]
if n==1:exit(print(1))
if len(set(c for w,c in wc))==1:exit(print(1))
wc.sort()
mw,mc=wc[0]
i=1
while wc[i][1]==mc:i+=1
mmw,mmc=wc[i]
flag=False
if mmw+mw<=y:flag=True
for w,c in wc:
  if ((c==mc and w+mw<=x)or(c!=mc and w+mw<=y))and((c==mmc and w+mmw<=x)or(c!=mmc and w+mmw<=y)):flag=True
if flag:
  d=defaultdict(int)
  dc=0
  for w,c in wc:
    if [w,c]==[mw,mc]:
      d[c]+=1
      dc+=1
    elif(c==mc and w+mw<=x)or(c!=mc and w+mw<=y)or(c==mmc and w+mmw<=x)or(c!=mmc and w+mmw<=y):
      d[c]+=1
      dc+=1
  ans=f[dc]
  for i in d:
    ans*=pow(f[d[i]],mod-2,mod)
    ans%=mod
else:
  d=defaultdict(int)
  dc=0
  md=defaultdict(int)
  mdc=0
  for w,c in wc:
    if [w,c]==[mw,mc]:
      d[c]+=1
      dc+=1
    elif [w,c]==[mmw,mmc]:
      md[c]+=1
      mdc+=1
    elif (c==mc and w+mw<=x)or(c!=mc and w+mw<=y):
      d[c]+=1
      dc+=1
    elif (c==mmc and w+mmw<=x)or(c!=mmc and w+mmw<=y):
      md[c]+=1
      mdc+=1
  ans=f[dc]
  for i in d:
    ans*=pow(f[d[i]],mod-2,mod)
    ans%=mod
  anss=f[mdc]
  for i in md:
    anss*=pow(f[md[i]],mod-2,mod)
    anss%=mod
  ans=(ans*anss)%mod
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
n,x,y=map(int,input().split())
mod=10**9+7
f=[1]
for i in range(1,n+7):f.append(f[-1]*i%mod)
wc=[list(map(int,input().split()))[::-1]for _ in range(n)]
if n==1:exit(print(1))
if len(set(c for w,c in wc))==1:exit(print(1))
wc.sort()
mw,mc=wc[0]
i=1
while wc[i][1]==mc:i+=1
mmw,mmc=wc[i]
flag=False
if mmw+mw<=y:flag=True
for w,c in wc:
  if ((c==mc and w+mw<=x)or(c!=mc and w+mw<=y))and((c==mmc and w+mmw<=x)or(c!=mmc and w+mmw<=y)):flag=True
if flag:
  d=defaultdict(int)
  dc=0
  for w,c in wc:
    if(c==mc and w+mw<=x)or(c!=mc and w+mw<=y)or(c==mmc and w+mmw<=x)or(c!=mmc and w+mmw<=y):
      d[c]+=1
      dc+=1
  ans=f[dc]
  for i in d:
    ans*=pow(f[d[i]],mod-2,mod)
    ans%=mod
else:
  d=defaultdict(int)
  dc=0
  md=defaultdict(int)
  mdc=0
  for w,c in wc:
    if (c==mc and w+mw<=x)or(c!=mc and w+mw<=y):
      d[c]+=1
      dc+=1
    if (c==mmc and w+mmw<=x)or(c!=mmc and w+mmw<=y):
      md[c]+=1
      mdc+=1
  ans=f[dc]
  for i in d:
    ans*=pow(f[d[i]],mod-2,mod)
    ans%=mod
  anss=f[mdc]
  for i in md:
    anss*=pow(f[md[i]],mod-2,mod)
    anss%=mod
  ans=(ans*anss)%mod
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
n,x,y=map(int,input().split())
mod=10**9+7
f=[1]
for i in range(1,n+7):f.append(f[-1]*i%mod)
wc=[list(map(int,input().split()))[::-1]for _ in range(n)]
if n==1:exit(print(1))
if len(set(c for w,c in wc))==1:exit(print(1))
wc.sort()
mw,mc=wc[0]
i=1
while wc[i][1]==mc:i+=1
mmw,mmc=wc[i]
flag=False
for w,c in wc:
  if ((c==mc and w+mw<=x)or(c!=mc and w+mw<=y))and((c==mmc and w+mmw<=x)or(c!=mmc and w+mmw<=y)):flag=True
if flag:
  d=defaultdict(int)
  dc=0
  for w,c in wc:
    if(c==mc and w+mw<=x)or(c!=mc and w+mw<=y)or(c==mmc and w+mmw<=x)or(c!=mmc and w+mmw<=y):
      d[c]+=1
      dc+=1
  ans=f[dc]
  for i in d:
    ans*=pow(f[d[i]],mod-2,mod)
    ans%=mod
else:
  d=defaultdict(int)
  dc=0
  md=defaultdict(int)
  mdc=0
  for w,c in wc:
    if (c==mc and w+mw<=x)or(c!=mc and w+mw<=y):
      d[c]+=1
      dc+=1
    if (c==mmc and w+mmw<=x)or(c!=mmc and w+mmw<=y):
      md[c]+=1
      mdc+=1
  ans=f[dc]
  for i in d:
    ans*=pow(f[d[i]],mod-2,mod)
    ans%=mod
  anss=f[mdc]
  for i in md:
    anss*=pow(f[md[i]],mod-2,mod)
    anss%=mod
  ans=(ans*anss)%mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys;sys.setrecursionlimit(10**9)
class UnionFind:
  def __init__(self,n):
    self.n=[-1]*n
    self.r=[0]*n
    self.siz=n
  def find_root(self,x):
    if self.n[x]<0:
      return x
    else:
      self.n[x]=self.find_root(self.n[x])
      return self.n[x]
  def unite(self,x,y):
    x=self.find_root(x)
    y=self.find_root(y)
    if x==y:return
    elif self.r[x]>self.r[y]:
      self.n[x]+=self.n[y]
      self.n[y]=x
    else:
      self.n[y]+=self.n[x]
      self.n[x]=y
      if self.r[x]==self.r[y]:
        self.r[y]+=1
    self.siz-=1
  def root_same(self,x,y):
    return self.find_root(x)==self.find_root(y)
  def count(self,x):
    return -self.n[self.find_root(x)]
  def size(self):
    return self.siz

from collections import defaultdict
n,x,y=map(int,input().split())
mod=10**9+7
f=[1]
for i in range(1,n+7):f.append(f[-1]*i%mod)
cw=[list(map(int,input().split()))for _ in range(n)]
if n==1:exit(print(1))
if len(set(c for c,w in cw))==1:exit(print(1))
for i in range(n):cw[i][0]-=1
miw=[10**10]*n
miwi=[0]*n
for i in range(n):
  c,w=cw[i]
  if miw[c]>w:
    miw[c]=w
    miwi[c]=i
mminc=miw.index(min(miw))
temp=10**10
for i in range(n):
  if i!=mminc:temp=min(temp,miw[i])
sminc=miw.index(temp)
u=UnionFind(n)
for i in range(n):
  c,w=cw[i]
  if c==mminc:tc=sminc
  else:tc=mminc
  if miw[c]+w<=x:u.unite(miwi[c],i)
  if miw[tc]+w<=y:u.unite(miwi[tc],i)
d=[0]*n
for i in range(n):
  if i==u.find_root(i):d[i]=defaultdict(int)
for i in range(n):
  c,w=cw[i]
  d[u.find_root(i)][c]+=1
ans=1
for i in range(n):
  if i==u.find_root(i):
    anss=1
    co=0
    for j in d[i]:
      anss*=pow(f[d[i][j]],mod-2,mod)
      anss%=mod
      co+=d[i][j]
    anss*=f[co]
    ans=(ans*anss)%mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, X, Y = map( int, input().split() )

C = []
W = []
for i in range( N ):
  c, w = map( int, input().split() )
  C.append( c - 1 )
  W.append( w )

c2w = [ [] for i in range( N ) ]
for i in range( N ):
  c2w[ C[ i ] ].append( W[ i ] )
for i in range( N ):
  c2w[ C[ i ] ].sort()

minw, _minwp = 2e9, -1
for i in range( N ):
  if len( c2w[ i ] ) == 0: continue
  if minw > c2w[ i ][ 0 ]:
    minw = c2w[ i ][ 0 ]
    _minwp = i
minw2 = 2e9
for i in range( N ):
  if len( c2w[ i ] ) == 0: continue
  if i == _minwp: continue
  if minw2 > c2w[ i ][ 0 ]:
    minw2 = c2w[ i ][ 0 ]

merged = [ False for i in range( N ) ]
hi = [ 1 for i in range( N ) ]
for i in range( N ):
  if len( c2w[ i ] ) == 0: continue
  lb, ub = 2, len( c2w[ i ] )
  while lb <= ub:
    mid = lb + ub >> 1
    if c2w[ i ][ 0 ] + c2w[ i ][ mid - 1 ] <= X:
      hi[ i ] = max( hi[ i ], mid )
      lb = mid + 1
    else:
      ub = mid - 1
  lb, ub = 1, len( c2w[ i ] )
  www = minw2 if minw != minw2 and c2w[ i ][ 0 ] == minw else minw
  while lb <= ub:
    mid = lb + ub >> 1
    if www + c2w[ i ][ mid - 1 ] <= Y:
      hi[ i ] = max( hi[ i ], mid )
      merged[ i ] = True
      lb = mid + 1
    else:
      ub = mid - 1

MOD = int( 1e9 + 7 )

fact = [ 1 ]
inv_fact = [ 1 ]
for i in range( 1, N + 1, 1 ):
  fact.append( fact[ i - 1 ] * i % MOD )
  inv_fact.append( pow( fact[ i ], MOD - 2, MOD ) )

ans = fact[ sum( merged[ i ] * hi[ i ] for i in range( N ) ) ]
for i in range( N ):
  if not merged[ i ]: continue
  ans = ans * inv_fact[ hi[ i ] ] % MOD

print( ans )

Submission status: Time Limit Exceeded

Solution code:
N, X, Y = map( int, input().split() )

C = []
W = []
for i in range( N ):
  c, w = map( int, input().split() )
  C.append( c - 1 )
  W.append( w )

c2w = [ [] for i in range( N ) ]
for i in range( N ):
  c2w[ C[ i ] ].append( W[ i ] )
for i in range( N ):
  c2w[ C[ i ] ].sort()

W.sort()
minw, minw2 = W[ 0 ], W[ 1 ] if 1 < N else W[ 0 ]

merged = [ False for i in range( N ) ]
hi = [ 1 for i in range( N ) ]
for i in range( N ):
  if len( c2w[ i ] ) == 0: continue
  lb, ub = 2, len( c2w[ i ] )
  while lb <= ub:
    mid = lb + ub >> 1
    if c2w[ i ][ 0 ] + c2w[ i ][ mid - 1 ] <= X:
      hi[ i ] = max( hi[ i ], mid )
      lb = mid + 1
    else:
      ub = mid - 1
  lb, ub = 1, len( c2w[ i ] )
  www = minw2 if minw != minw2 and c2w[ i ][ 0 ] == minw else minw
  while lb <= ub:
    mid = lb + ub >> 1
    if www + c2w[ i ][ mid - 1 ] <= Y:
      hi[ i ] = max( hi[ i ], mid )
      merged[ i ] = True
      lb = mid + 1
    else:
      ub = mid - 1

MOD = int( 1e9 + 7 )

fact = [ 1 ]
inv_fact = [ 1 ]
for i in range( 1, N + 1, 1 ):
  fact.append( fact[ i - 1 ] * i % MOD )
  inv_fact.append( pow( fact[ i ], MOD - 2, MOD ) )

ans = fact[ sum( merged[ i ] * hi[ i ] for i in range( N ) ) ]
for i in range( N ):
  if not merged[ i ]: continue
  ans = ans * inv_fact[ hi[ i ] ] % MOD

print( ans )