Problem:


Score : 400 points

Problem Statement

On a two-dimensional plane, there are N red points and N blue points.
The coordinates of the i-th red point are (a_i, b_i), and the coordinates of the i-th blue point are (c_i, d_i).

A red point and a blue point can form a friendly pair when, the x-coordinate of the red point is smaller than that of the blue point, and the y-coordinate of the red point is also smaller than that of the blue point.

At most how many friendly pairs can you form? Note that a point cannot belong to multiple pairs.

Constraints

All input values are integers.

1 \leq N \leq 100

0 \leq a_i, b_i, c_i, d_i < 2N

a_1, a_2, ..., a_N, c_1, c_2, ..., c_N are all different.

b_1, b_2, ..., b_N, d_1, d_2, ..., d_N are all different.

Input

Input is given from Standard Input in the following format:

N
a_1 b_1
a_2 b_2
:
a_N b_N
c_1 d_1
c_2 d_2
:
c_N d_N

Output

Print the maximum number of friendly pairs.

Sample Input 1

3
2 0
3 1
1 3
4 2
0 4
5 5

Sample Output 1

2

For example, you can pair (2, 0) and (4, 2), then (3, 1) and (5, 5).

Sample Input 2

3
0 0
1 1
5 2
2 3
3 4
4 5

Sample Output 2

2

For example, you can pair (0, 0) and (2, 3), then (1, 1) and (3, 4).

Sample Input 3

2
2 2
3 3
0 0
1 1

Sample Output 3

0

It is possible that no pair can be formed.

Sample Input 4

5
0 0
7 3
2 2
4 8
1 6
8 5
6 9
5 4
9 1
3 7

Sample Output 4

5

Sample Input 5

5
0 0
1 1
5 5
6 6
7 7
2 2
3 3
4 4
8 8
9 9

Sample Output 5

4



Sample input:
3
2 0
3 1
1 3
4 2
0 4
5 5


Sample output:
2

Submission status: Wrong Answer

Solution code:
from operator import itemgetter

n = int(input())
ab = [list(map(int, input().split())) for _ in range(n)]
cd = [list(map(int, input().split())) for _ in range(n)]
ans = 0
dp_ab = [False] * n
dp_cd = [False] * n

ab.sort(key = itemgetter(1))
cd.sort(key = itemgetter(1))
ab.sort()
cd.sort()

for i in range(n):
    count = 0
    for j in range(n):
        if cd[i][0] > ab[j][0] and cd[i][1] > ab[j][1]:
            count += 1
    cd[i].append(count)

cd.sort(key = itemgetter(2))

for i in range(n):
    count = 0
    for j in range(n):
        if ab[i][0] < cd[j][0] and ab[i][1] < cd[j][1]:
            count += 1
    ab[i].append(count)

ab.sort(key = itemgetter(2))

for i in range(n):
    for j in range(n):
        if cd[i][0] > ab[j][0] and cd[i][1] > ab[j][1] and dp_cd[i] == False and dp_ab[j] == False:
            dp_cd[i] = True
            dp_ab[j] = True
            ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter

n = int(input())
ab = [list(map(int, input().split())) for _ in range(n)]
cd = [list(map(int, input().split())) for _ in range(n)]
ans = 0
dp_ab = [False] * n
dp_cd = [False] * n

for i in range(n):
    count = 0
    for j in range(n):
        if cd[i][0] > ab[j][0] and cd[i][1] > ab[j][1]:
            count += 1
    cd[i].append(count)

cd.sort(key = itemgetter(2))

for i in range(n):
    count = 0
    for j in range(n):
        if ab[i][0] < cd[j][0] and ab[i][1] < cd[j][1]:
            count += 1
    ab[i].append(count)

ab.sort(key = itemgetter(2))

for i in range(n):
    for j in range(n):
        if cd[i][0] > ab[j][0] and cd[i][1] > ab[j][1] and dp_cd[i] == False and dp_ab[j] == False:
            dp_cd[i] = True
            dp_ab[j] = True
            ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
n  = int(input())
red = [list(map(int,input().split())) for i in range(n)]
blue = [list(map(int,input().split())) for i in range(n)]

red.sort(reverse=True)
blue.sort()

ans = 0
for i in range(n):
    x = red[i][0]
    y = red[i][1]
    index = -1
    now_by = 101
    for j in range(len(blue)):
        if x < blue[j][0] and y < blue[j][1] and now_by > blue[j][1]:
            index = j
            now_by = blue[j][1]
    if index >= 0:
        ans += 1
        blue.pop(index)


print(ans)

Submission status: Wrong Answer

Solution code:
n  = int(input())
red = [list(map(int,input().split())) for i in range(n)]
blue = [list(map(int,input().split())) for i in range(n)]

red.sort(reverse=True)
blue.sort(reverse=True)

ans = 0
for i in range(n):
    x = red[i][0]
    y = red[i][1]
    for j in range(len(blue)):
        if x < blue[j][0] and y < blue[j][1]:
            ans += 1
            blue.pop(j)
            break

print(ans)

Submission status: Wrong Answer

Solution code:
n  = int(input())
red = [list(map(int,input().split())) for i in range(n)]
blue = [list(map(int,input().split())) for i in range(n)]

red.sort()
blue.sort()

ans = 0
for i in range(n):
    x = red[i][0]
    y = red[i][1]
    for j in range(len(blue)):
        if x < blue[j][0] and y < blue[j][1]:
            ans += 1
            blue.pop(j)
            break

print(ans)

Submission status: Wrong Answer

Solution code:
NumPoints = int(input())
RedPoints = [[int(_) for _ in input().split()] for i in range(NumPoints)]
BluePoints = [[int(_) for _ in input().split()] for i in range(NumPoints)]

RedPoints.sort(key=lambda x: (-x[0], -x[1]))
BluePoints.sort(key=lambda x: (-x[0], -x[1]))

establish_pair = 0

def find_pair():
    global establish_pair
    for i_blue_y, i_blue_x in BluePoints:
        count_pair = 0
        for i_red_y, i_red_x in RedPoints:
            if i_red_y < i_blue_y and i_red_x < i_blue_x:
                count_pair += 1
                candidate_y, candidate_x = i_red_y, i_red_x

        if count_pair != 1:
            continue
        establish_pair += 1
        BluePoints.remove([i_blue_y, i_blue_x])
        RedPoints.remove([candidate_y, candidate_x])
        return
    
    else:
        for i_blue_y, i_blue_x in BluePoints:
            for i_red_y, i_red_x in RedPoints:
                if i_red_y < i_blue_y and i_red_x < i_blue_x:
                    establish_pair += 1
                    BluePoints.remove([i_blue_y, i_blue_x])
                    RedPoints.remove([i_red_y, i_red_x])
                    return
    return

while len(BluePoints) > 0:
    pre_establish_pair = establish_pair
    find_pair()

    if pre_establish_pair == establish_pair:
        break

print(establish_pair)

Submission status: Wrong Answer

Solution code:
n = int(input())
AB = [list(map(int,input().split())) for _ in range(n)]
CD = [list(map(int,input().split())) for _ in range(n)]

que = [[] for _ in range(n)]
for i in range(n):
  for j in range(n):
    if AB[i][0] < CD[j][0] and AB[i][1] < CD[j][1]:
      que[j].append(i)

def dfs(i,v):
  print(ab)
  for a in que[i]:
    if a in v:
      continue
    v.add(a)
    if ab[a] == -1 or dfs(ab[a], v):
      ab[a] = i
      return True
  return False
      
v = [set() for _ in range(n)]   
ab = [-1]*n

print(sum(dfs(i, set()) for i in range(n)))

Submission status: Wrong Answer

Solution code:

N = int(input())
ab = [list(map(int, input().split())) for _ in range(N)]
cd = [list(map(int, input().split())) for _ in range(N)]

ab_sorted = sorted(ab, key = lambda x:x[0], reverse = True)
cd_sorted = sorted(cd, key = lambda x:x[0], reverse = True)


for i in range(len(ab_sorted)):
    candidate = -10e+10
    nearest_size = -10e+10
    for j in range(len(cd_sorted)):
        if cd_sorted[j][0] > ab_sorted[i][0] and cd_sorted[j][1] > ab_sorted[i][1] and nearest_size < cd_sorted[j][1]:
            candidate = j
            nearest_size = cd_sorted[j][1]
    if candidate != -10e+10:
        del cd_sorted[candidate]

print(len(ab_sorted) - len(cd_sorted))

Submission status: Wrong Answer

Solution code:
N = int(input())
ab = [list(map(int, input().split())) for _ in range(N)]
cd = [list(map(int, input().split())) for _ in range(N)]

ab_sorted = sorted(ab, key = lambda x:x[0], reverse = True)
cd_sorted = sorted(cd, key = lambda x:x[0], reverse = True)


for i in range(len(ab_sorted)):
    candidate = -10e+10
    nearest_size = -10e+10
    for j in range(len(cd_sorted)):
        if cd_sorted[j][0] > ab_sorted[i][0] and cd_sorted[j][0] > ab_sorted[i][0] and nearest_size < cd_sorted[j][1]:
            candidate = j
            nearest_size = cd_sorted[j][1]
    if candidate != -10e+10:
        del cd_sorted[candidate]
print(len(ab_sorted) - len(cd_sorted))

Submission status: Wrong Answer

Solution code:

n = int(input())
from collections import defaultdict
AB = [list(map(int,input().split())) for _ in range(n)]
CD = [list(map(int,input().split())) for _ in range(n)]

f = [[True]*n for _ in range(2)]
ab = [[] for _ in range(n)]
for i in range(n):
  for j in range(n):
    if AB[i][0] < CD[j][0] and AB[i][1] < CD[j][1]:
      ab[i].append(j)

def dfs(i, v):
  for j in range(len(ab[i])):
    if j in v:
      continue
    v.add(j)
    if (f[0][i] or f[1][j]) or dfs(j, v):
      f[0][i] = False
      f[1][j] = False
      return True
  return False

print(sum(dfs(i, set()) for i in range(n)))

Submission status: Wrong Answer

Solution code:

n = int(input())
from collections import defaultdict
AB = [list(map(int,input().split())) for _ in range(n)]
CD = [list(map(int,input().split())) for _ in range(n)]
AB.sort(reverse= True)
CD.sort(reverse= True)
ab = defaultdict(list)
cd = defaultdict(list)

for i in range(n):
  ab[i].append(AB[i][0])
  ab[i].append(AB[i][1])
  cd[i].append(CD[i][0])
  cd[i].append(CD[i][1])

f = [[0]*n for _ in range(2)]

def dfs(i,pf):
  global ans
  
  if sum(pf[0]) > ans:
    ans = sum(pf[0])
  
  if i == n:
    return pf
  
  for j in range(n):
      if ab[j][0] < cd[i][0] and ab[j][1] < cd[i][1] and \
        pf[0][j] == 0 and pf[1][i] == 0:
          nf = pf.copy()
          nf[0][j] = 1
          nf[1][i] = 1
          ph = dfs(i+1, nf)
          ph = dfs(i+1, pf)

ans = 0
dfs(0,f)
print(ans)

Submission status: Wrong Answer

Solution code:

n = int(input())
from collections import defaultdict
AB = [list(map(int,input().split())) for _ in range(n)]
CD = [list(map(int,input().split())) for _ in range(n)]
AB.sort(reverse= True)
CD.sort(reverse= True)
ab = defaultdict(list)
cd = defaultdict(list)

for i in range(n):
  ab[i].append(AB[i][0])
  ab[i].append(AB[i][1])
  cd[i].append(CD[i][0])
  cd[i].append(CD[i][1])

f = [[0]*n for _ in range(2)]

def dfs(i,pf):
  global f
  
  if sum(pf[0]) > sum(f[0]):
    f = pf.copy()
    print(f)
  if i == n:
    return
  
  for j in range(n):
      if ab[j][0] < cd[i][0] and ab[j][1] < cd[i][1] and \
        pf[0][j] == 0 and pf[1][i] == 0:
          nf = pf.copy()
          nf[0][j] = 1
          nf[1][i] = 1
          dfs(i+1, nf)
          dfs(i+1, pf)

dfs(0,f)
print(sum(f[0]))

Submission status: Wrong Answer

Solution code:

n = int(input())
ab = [list(map(int,input().split())) for _ in range(n)]
cd = [list(map(int,input().split())) for _ in range(n)]

ab.sort()
cd.sort()

abf = [0]*n
cdf = [0]*n
que = [[] for _ in range(n)]
for i in range(n):
  for j in range(n):
    if cd[i][0] > ab[j][0] and cd[i][1] > ab[j][1] and abf[j] == 0:
        que[i].append(j)
  if len(que[i]) > 0:
    q = [0,ab[que[i][0]][1]]
    for j in range(len(que[i])):
      if ab[que[i][j]][1] > q[1]:
        q = [que[i][j], ab[que[i][j]][1]]
    abf[q[0]] = 1

print(abf)

Submission status: Wrong Answer

Solution code:

n = int(input())
ab = [list(map(int,input().split())) for _ in range(n)]
cd = [list(map(int,input().split())) for _ in range(n)]

ab.sort()
cd.sort()

abf = [0]*n
cdf = [0]*n
que = [[] for _ in range(n)]
for i in range(n):
  for j in range(n):
    if ab[j][0] < cd[i][0] and ab[j][1] < cd[i][1] and \
        abf[j] == 0 and cdf[i] == 0:
      que[i].append(j)

qn = []
for i in range(n):
  qn.append([len(que[i]), i])
qn.sort()

for i in range(len(qn)):
    for idx in que[qn[i][1]]:
      if abf[idx] == 0:
        abf[idx] = 1

  
print(sum(abf))

Submission status: Wrong Answer

Solution code:

n = int(input())
ab = [list(map(int,input().split())) for _ in range(n)]
cd = [list(map(int,input().split())) for _ in range(n)]

ab.sort()
cd.sort()

abf = [0]*n
cdf = [0]*n
que = [[] for _ in range(n)]
for i in range(n):
  for j in range(n):
    if ab[j][0] < cd[i][0] and ab[j][1] < cd[i][1] and \
        abf[j] == 0 and cdf[i] == 0:
      que[i].append(j)

for i in range(n)[::-1]:
  for j in que[i][::-1]:
    if abf[j] == 0:
      abf[j] = 1
      break
      
print(sum(abf))

Submission status: Wrong Answer

Solution code:

n = int(input())
ab = [list(map(int,input().split())) for _ in range(n)]
cd = [list(map(int,input().split())) for _ in range(n)]

ab.sort()
cd.sort()

abf = [0]*n
cdf = [0]*n
for i in range(n):
  idx = -1
  for j in range(n):
    if ab[j][0] < cd[i][0] and ab[j][1] < cd[i][1] and \
        abf[j] == 0 and cdf[i] == 0:
      if idx == -1:idx = j
      if  max(ab[j][0],ab[j][1]) > max(ab[idx][0],ab[idx][1]):
          idx = j
      elif max(ab[j][0],ab[j][1]) == max(ab[idx][0],ab[idx][1]) and \
           min(ab[j][0],ab[j][1]) > min(ab[idx][0],ab[idx][1]):
          idx = j
  if idx >= 0:      
    abf[idx] = 1
    cdf[i] = 1

print(sum(abf))

Submission status: Wrong Answer

Solution code:

n = int(input())
ab = [list(map(int,input().split())) for _ in range(n)]
cd = [list(map(int,input().split())) for _ in range(n)]

ab.sort()
cd.sort()

abf = [0]*n
cdf = [0]*n
for i in range(n):
  idx = -1
  for j in range(n):
    if ab[j][0] < cd[i][0] and ab[j][1] < cd[i][1] and \
        abf[j] == 0 and cdf[i] == 0:
      if idx == -1:idx = j
      if  max(ab[j][0],ab[j][1]) > max(ab[idx][0],ab[idx][1]):
        idx = j
  if idx >= 0:      
    abf[idx] = 1
    cdf[i] = 1

print(sum(abf))

Submission status: Wrong Answer

Solution code:
N = int(input())
R = []
B = []
flag = [1 for i in range(N)]
for _ in range(N):
    R.append(list(map(int,input().split())))
for _ in range(N):
    B.append(list(map(int,input().split())))
R.sort()
B.sort()
ans = 0
for c, d in B:
    for i in range(N):
        a, b = R[i]
        if flag[i] and a < c and b < d:
            flag[i] = 0
            ans += 1
            break
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())

red_list=[]
for i in range(N):
  a,b=map(int,input().split())
  red_list.append((a,b))
blue_list=[]
for i in range(N):
  c,d=map(int,input().split())
  blue_list.append((c,d))

max_answer=0
for k in range(101):
  k1=k
  k2=100-k

  red_list_w=[]
  for a,b in red_list:    
    red_list_w.append((k1*a+k2*b,a,b))
  red_list_w.sort()

  blue_list_w=[]
  for c,d in blue_list:    
    blue_list_w.append((k1*c+k2*d,c,d))
  blue_list_w.sort()

  answer=0
  selected_set=set()
  for i in range(N):
    rs,rx,ry=red_list_w[i]
    for j in range(N):
      if j in selected_set:
        continue
      bs,bx,by=blue_list_w[j]
      if rx<bx and ry<by:
        #print((rx,ry),(bx,by))
        selected_set.add(j)
        answer+=1
        break
      
  max_answer=max(max_answer,answer)
  
print(max_answer)

Submission status: Wrong Answer

Solution code:
N=int(input())

xlist=[0]*(2*N)
ylist=[0]*(2*N)

red_list=[]
for i in range(N):
  a,b=map(int,input().split())
  red_list.append((a,b))
  xlist[a]="r"
  ylist[b]="r"
red_list.sort()

blue_list=[]
for i in range(N):
  c,d=map(int,input().split())
  blue_list.append((c,d))
  xlist[c]="b"
  ylist[d]="b"
blue_list.sort()
  
#print(xlist)
#print(ylist)

x,y=0,0
min_x,min_y=0,0
for i in range(2*N):
  if xlist[i]=="r":
    x+=1
  else:
    x-=1
  min_x=min(x,min_x)
  
  if ylist[i]=="r":
    y+=1
  else:
    y-=1
  min_y=min(y,min_y)
  
print(min(N+min_x,N+min_y))

Submission status: Wrong Answer

Solution code:
N=int(input())

xlist=[0]*(2*N)
ylist=[0]*(2*N)

red_list=[]
for i in range(N):
  a,b=map(int,input().split())
  red_list.append((a,b))
  xlist[a]="r"
  ylist[b]="r"
red_list.sort()

blue_list=[]
for i in range(N):
  c,d=map(int,input().split())
  blue_list.append((c,d))
  xlist[c]="b"
  ylist[d]="b"
blue_list.sort()
  
#print(xlist)
#print(ylist)

x,y=0,0
min_x,min_y=0,0
for i in range(N):
  if xlist[i]=="r":
    x+=1
  else:
    x-=1
  min_x=min(x,min_x)
  
  if ylist[i]=="r":
    y+=1
  else:
    y-=1
  min_y=min(y,min_y)
  
print(min(N+min_x,N+min_y))

Submission status: Wrong Answer

Solution code:
N=int(input())

red_list=[]
for i in range(N):
  a,b=map(int,input().split())
  red_list.append((a+b,a,b))
red_list.sort()

blue_list=[]
for i in range(N):
  c,d=map(int,input().split())
  blue_list.append((c+d,c,d))
blue_list.sort()
  
#print(red_list)
#print(blue_list)

answer1=0
selected_set=set()
for i in reversed(range(N)):
  rs,rx,ry=red_list[i]
  for j in reversed(range(N)):
    if j in selected_set:
      continue
    bs,bx,by=blue_list[j]
    if rx<bx and ry<by:
      #print((rx,ry),(bx,by))
      selected_set.add(j)
      answer1+=1
      break
      
#rotate
for i in range(N):
  rs,rx,ry=red_list[i]  
  bs,bx,by=blue_list[i]
  red_list[i]=(rx,ry,rs)
  blue_list[i]=(bx,by,bs)
red_list.sort()
blue_list.sort()

answer2=0
selected_set=set()
for i in reversed(range(N)):
  rx,ry,rs=red_list[i]
  for j in reversed(range(N)):
    if j in selected_set:
      continue
    bx,by,bs=blue_list[j]
    if rx<bx and ry<by:
      #print((rx,ry),(bx,by))
      selected_set.add(j)
      answer2+=1
      break

#rotate
for i in range(N):
  rx,ry,rs=red_list[i]  
  bx,by,bs=blue_list[i]
  red_list[i]=(ry,rx,rs)
  blue_list[i]=(by,bx,bs)
red_list.sort()
blue_list.sort()

answer3=0
selected_set=set()
for i in reversed(range(N)):
  ry,rx,rs=red_list[i]
  for j in reversed(range(N)):
    if j in selected_set:
      continue
    by,bx,bs=blue_list[j]
    if rx<bx and ry<by:
      #print((rx,ry),(bx,by))
      selected_set.add(j)
      answer3+=1
      break

#print(answer1,answer2,answer3)
print(max(answer1,answer2,answer3))

Submission status: Wrong Answer

Solution code:
N=int(input())

red_list=[]
for i in range(N):
  a,b=map(int,input().split())
  red_list.append((a+b,a,b))
red_list.sort()

blue_list=[]
for i in range(N):
  c,d=map(int,input().split())
  blue_list.append((c+d,c,d))
blue_list.sort()
  
#print(red_list)
#print(blue_list)

answer1=0
selected_set=set()
for i in range(N):
  rs,rx,ry=red_list[i]
  for j in range(N):
    if j in selected_set:
      continue
    bs,bx,by=blue_list[j]
    if rx<bx and ry<by:
      #print((rx,ry),(bx,by))
      selected_set.add(j)
      answer1+=1
      break
      
#rotate
for i in range(N):
  rs,rx,ry=red_list[i]  
  bs,bx,by=blue_list[i]
  red_list[i]=(rx,ry,rs)
  blue_list[i]=(bx,by,bs)
red_list.sort()
blue_list.sort()

answer2=0
selected_set=set()
for i in range(N):
  rx,ry,rs=red_list[i]
  for j in range(N):
    if j in selected_set:
      continue
    bx,by,bs=blue_list[j]
    if rx<bx and ry<by:
      #print((rx,ry),(bx,by))
      selected_set.add(j)
      answer2+=1
      break

#rotate
for i in range(N):
  rx,ry,rs=red_list[i]  
  bx,by,bs=blue_list[i]
  red_list[i]=(ry,rx,rs)
  blue_list[i]=(by,bx,bs)
red_list.sort()
blue_list.sort()

answer3=0
selected_set=set()
for i in range(N):
  ry,rx,rs=red_list[i]
  for j in range(N):
    if j in selected_set:
      continue
    by,bx,bs=blue_list[j]
    if rx<bx and ry<by:
      #print((rx,ry),(bx,by))
      selected_set.add(j)
      answer3+=1
      break

#print(answer1,answer2,answer3)
print(max(answer1,answer2,answer3))

Submission status: Wrong Answer

Solution code:
n=int(input())
ab=[[int(i) for i in input().split()] for _ in range(n)]
cd=[[int(i) for i in input().split()] for _ in range(n)]
inab=[sum(map(lambda x:x[0]>a and x[1]>b,cd)) for a,b in ab]
incd=[sum(map(lambda x:x[0]<c and x[1]<d,ab)) for c,d in cd]
ans=0
while 1:
  f=1
  mab=1000
  for i in range(n):
    if inab[i] > 0 and mab > inab[i]:
      f=0
      mab=inab[i]
  if f:
    break
  mcd=1000
  tmp=(-1,-1)
  ans+=1
  for i in range(n):
    if mab==inab[i]:
      a,b=ab[i]
      for j in range(n):
        if incd[j]==0:continue
        c,d=cd[j]
        if a<c and b<d and mcd>incd[j]:
          mcd=incd[j]
          tmp=(i,j)
  ta,tb=ab[tmp[0]]
  tc,td=cd[tmp[1]]
  for i in range(n):
    a,b=ab[i]
    c,d=cd[i]    
    if inab[i]:
      if a<tc and b<td:
        inab[i]-=1
    if incd[i]:
      if c<ta and d<tb:
        incd[i]-=1  
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
ab=[[int(i) for i in input().split()] for _ in range(n)]
cd=[[int(i) for i in input().split()] for _ in range(n)]
ab.sort()
cd.sort()
check=[0]*n
ans=0
for a,b in ab:
  for i in range(n):
    if check[i]:
      continue
    c,d=cd[i]
    if c>a and d>b:
      ans+=1
      check[i]=1
      break
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

R = []
for i in range(N):
    a, b = map(int, input().split())
    R.append([a, b])

B = []
for i in range(N):
    c, d = map(int, input().split())
    B.append([c, d])

R = sorted(R,key=lambda x:-x[0])
B = sorted(B, key=lambda x:x[0])

ans1 = 0

RC = [0]*(N+1)
BC = [0]*(N+1)

for i in range(N):
    for j in range(N):
        if R[i][0] < B[j][0] and R[i][1] < B[j][1] and BC[j] == 0 and RC[i] == 0:
            ans1 += 1
            BC[j] = 1 
            RC[i] = 1

R = sorted(R,key=lambda x:-x[1])
B = sorted(B, key=lambda x:x[1])

ans2 = 0

RC = [0]*(N+1)
BC = [0]*(N+1)

for i in range(N):
    for j in range(N):
        if R[i][0] < B[j][0] and R[i][1] < B[j][1] and BC[j] == 0 and RC[i] == 0:
            ans2 += 1
            BC[j] = 1 
            RC[i] = 1

print(max(ans1, ans2))

Submission status: Wrong Answer

Solution code:
N = int(input())

R = []
for i in range(N):
    a, b = map(int, input().split())
    R.append([a, b])

B = []
for i in range(N):
    c, d = map(int, input().split())
    B.append([c, d])

R = sorted(R,key=lambda x:x[0])
B = sorted(B, key=lambda x:x[0])

ans1 = 0

RC = [0]*(N+1)
BC = [0]*(N+1)

for i in range(N):
    for j in range(N):
        if R[i][0] < B[j][0] and R[i][1] < B[j][1] and BC[j] == 0 and RC[i] == 0:
            ans1 += 1
            BC[j] = 1 
            RC[i] = 1

R = sorted(R,key=lambda x:x[1])
B = sorted(B, key=lambda x:x[1])

ans2 = 0

RC = [0]*(N+1)
BC = [0]*(N+1)

for i in range(N):
    for j in range(N):
        if R[i][0] < B[j][0] and R[i][1] < B[j][1] and BC[j] == 0 and RC[i] == 0:
            ans2 += 1
            BC[j] = 1 
            RC[i] = 1

print(max(ans1, ans2))

Submission status: Wrong Answer

Solution code:
import sys
from io import StringIO
import unittest

# 二部グラフのマッチングに関する参考ページ
# https://ikatakos.com/pot/programming_algorithm/graph_theory/bipartite_matching

graphs = []


def dfs(now, visited, matches):

    # 辺を網羅していく
    for next in graphs[now]:

        # 到達済みの点の場合、何もせず終了
        if str(next) in visited:
            continue

        # 到達フラグを立てる
        visited.append(str(next))

        dfs(next, visited, matches)

        # 自点と次点が繋がっている場合
        if matches[now] == next:
            # 次点の先にどこにも繋がっていない点が存在する場合
            work = [False, False]
            for next2 in graphs[next]:
                if matches[next2] == -1:
                    work[0] = True
                    break
            # 自点の前にどこにも繋がっていない点が存在する場合
            for before in graphs[now]:
                if matches[before] == -1:
                    work[1] = True
                    break

            # 増幅路を発見
            if all(work):
                # 自点と次点のペアを解消する
                matches[next] = -1
                matches[now] = -1
                # 次点と次の点を繋げる
                matches[next] = next2
                matches[next2] = next
                # 自点と前の点を繋げる
                matches[before] = now
                matches[now] = before

        # 自点と次点がどこにもつながっていない場合
        if matches[now] == matches[next] == -1:
            # 次点と自点をマッチングする
            matches[now] = next
            matches[next] = now
            return

    return False


def resolve():
    global graphs
    # ★get input
    n = int(input())

    reds = [[int(i) for i in input().split()] for j in range(n)]
    blues = [[int(i) for i in input().split()] for j in range(n)]

    # 2部グラフ作成(各点が、どの点とマッチングできるか、という組み合わせを格納したリストを作成する。
    # この形に直さずに再帰処理を作ると、実装が非常に大変になるため。
    graphs = [[] for i in range(n * 2)]
    # 赤と青がマッチングする組み合わせを検索
    for i, red in enumerate(reds):
        for j, blue in enumerate(blues):
            # マッチングする場合、情報をグラフに追加。
            if red[0] < blue[0] and red[1] < blue[1]:
                graphs[i].append(n + j)  # 赤点の情報
                graphs[n + j].append(i)  # 青点の情報

    # どの点をペアにしたか保持する変数
    matches = [-1 for i in range(n*2)]
    # どの赤点->青点の組み合わせを調査済みか保持する変数
    visited = []

    for now in range(n*2):
        dfs(now, visited, matches)

    ans = [not i == -1 for i in matches].count(True) / 2
    print(int(ans))


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """3
2 0
3 1
1 3
4 2
0 4
5 5"""
        output = """2"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """3
0 0
1 1
5 2
2 3
3 4
4 5"""
        output = """2"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """2
2 2
3 3
0 0
1 1"""
        output = """0"""
        self.assertIO(input, output)

    def test_入力例_4(self):
        input = """5
0 0
7 3
2 2
4 8
1 6
8 5
6 9
5 4
9 1
3 7"""
        output = """5"""
        self.assertIO(input, output)

    def test_入力例_5(self):
        input = """5
0 0
1 1
5 5
6 6
7 7
2 2
3 3
4 4
8 8
9 9"""
        output = """4"""
        self.assertIO(input, output)


if __name__ == "__main__":
    # unittest.main()
    resolve()

Submission status: Wrong Answer

Solution code:
import sys
from io import StringIO
import unittest

# 二部グラフのマッチングに関する参考ページ
# https://ikatakos.com/pot/programming_algorithm/graph_theory/bipartite_matching

graphs = []


def dfs(now, visited, matches):

    # 辺を網羅していく
    for next in graphs[now]:

        # 到達済みの点の場合、何もせず終了
        if str(next) in visited:
            continue

        # 到達フラグを立てる
        visited.append(str(next))

        dfs(next, visited, matches)

        # 自点と次点が繋がっている場合
        if matches[now] == next:
            # 次点の先にどこにも繋がっていない点が存在する場合
            work = [False, False]
            for next2 in graphs[next]:
                if matches[next2] == -1:
                    work[1] = True
                    break
            # 自点の前にどこにも繋がっていない点が存在する場合
            for before in graphs[now]:
                if matches[before] == -1:
                    work[2] = True
                    break

            # 増幅路を発見
            if all(work):
                # 自点と次点のペアを解消する
                matches[matches[now]] = -1
                matches[now] = -1
                # 次点と次の点を繋げる
                matches[next] = next2
                matches[next2] = next
                # 自点と前の点を繋げる
                matches[before] = now
                matches[now] = before

        # 自点と次点がどこにもつながっていない場合
        if matches[now] == matches[next] == -1:
            # 次点と自点をマッチングする
            matches[now] = next
            matches[next] = now
            return

    return False


def resolve():
    global graphs
    # ★get input
    n = int(input())

    reds = [[int(i) for i in input().split()] for j in range(n)]
    blues = [[int(i) for i in input().split()] for j in range(n)]

    # 2部グラフ作成(各点が、どの点とマッチングできるか、という組み合わせを格納したリストを作成する。
    # この形に直さずに再帰処理を作ると、実装が非常に大変になるため。
    graphs = [[] for i in range(n * 2)]
    # 赤と青がマッチングする組み合わせを検索
    for i, red in enumerate(reds):
        for j, blue in enumerate(blues):
            # マッチングする場合、情報をグラフに追加。
            if red[0] < blue[0] and red[1] < blue[1]:
                graphs[i].append(n + j)  # 赤点の情報
                graphs[n + j].append(i)  # 青点の情報

    # どの点をペアにしたか保持する変数
    matches = [-1 for i in range(n*2)]
    # どの赤点->青点の組み合わせを調査済みか保持する変数
    visited = []

    for now in range(n*2):
        dfs(now, visited, matches)

    ans = [not i == -1 for i in matches].count(True) / 2
    print(int(ans))


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """3
2 0
3 1
1 3
4 2
0 4
5 5"""
        output = """2"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """3
0 0
1 1
5 2
2 3
3 4
4 5"""
        output = """2"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """2
2 2
3 3
0 0
1 1"""
        output = """0"""
        self.assertIO(input, output)

    def test_入力例_4(self):
        input = """5
0 0
7 3
2 2
4 8
1 6
8 5
6 9
5 4
9 1
3 7"""
        output = """5"""
        self.assertIO(input, output)

    def test_入力例_5(self):
        input = """5
0 0
1 1
5 5
6 6
7 7
2 2
3 3
4 4
8 8
9 9"""
        output = """4"""
        self.assertIO(input, output)


if __name__ == "__main__":
    # unittest.main()
    resolve()

Submission status: Wrong Answer

Solution code:
import sys
from io import StringIO
import unittest

# 二部グラフのマッチングに関する参考ページ
# https://ikatakos.com/pot/programming_algorithm/graph_theory/bipartite_matching

graphs = []


def dfs(now, visited, matches):

    # 辺を網羅していく
    for next in graphs[now]:

        # 到達済みの点の場合、何もせず終了
        if str(next) in visited:
            continue

        # 到達フラグを立てる
        visited.append(str(next))

        dfs(next, visited, matches)

        # 次点がどこにもつながっていない場合
        if matches[next] == -1:
            # 自分が繋がっているペアは解消する
            if not matches[now] == -1:
                matches[matches[now]] = -1
                matches[now] = -1
            # 次点と自点をマッチングする
            matches[now] = next
            matches[next] = now
            return

    return


def resolve():
    global graphs
    # ★get input
    n = int(input())

    reds = [[int(i) for i in input().split()] for j in range(n)]
    blues = [[int(i) for i in input().split()] for j in range(n)]

    # 2部グラフ作成(各点が、どの点とマッチングできるか、という組み合わせを格納したリストを作成する。
    # この形に直さずに再帰処理を作ると、実装が非常に大変になるため。
    graphs = [[] for i in range(n * 2)]
    # 赤と青がマッチングする組み合わせを検索
    for i, red in enumerate(reds):
        for j, blue in enumerate(blues):
            # マッチングする場合、情報をグラフに追加。
            if red[0] < blue[0] and red[1] < blue[1]:
                graphs[i].append(n + j)  # 赤点の情報
                graphs[n + j].append(i)  # 青点の情報

    # どの点をペアにしたか保持する変数
    matches = [-1 for i in range(n*2)]
    # どの赤点->青点の組み合わせを調査済みか保持する変数
    visited = []

    for now in range(n*2):
        dfs(now, visited, matches)

    ans = [not i == -1 for i in matches].count(True) / 2
    print(int(ans))


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """3
2 0
3 1
1 3
4 2
0 4
5 5"""
        output = """2"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """3
0 0
1 1
5 2
2 3
3 4
4 5"""
        output = """2"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """2
2 2
3 3
0 0
1 1"""
        output = """0"""
        self.assertIO(input, output)

    def test_入力例_4(self):
        input = """5
0 0
7 3
2 2
4 8
1 6
8 5
6 9
5 4
9 1
3 7"""
        output = """5"""
        self.assertIO(input, output)

    def test_入力例_5(self):
        input = """5
0 0
1 1
5 5
6 6
7 7
2 2
3 3
4 4
8 8
9 9"""
        output = """4"""
        self.assertIO(input, output)


if __name__ == "__main__":
    # unittest.main()
    resolve()