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:
N = int(input())
R = [list(map(int, input().split())) for _ in range(N)]
B = [list(map(int, input().split())) for _ in range(N)]

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

res = 0
for bx, by in B:
    tmp_ry = -1
    for i, (rx, ry) in enumerate(R):
        if rx < bx and ry < by:
            if ry > tmp_ry:
                tmp_i = i
                tmp_ry = ry
    if tmp_ry > -1:
        res += 1
        R.pop(tmp_i)

print(res)

Submission status: Wrong Answer

Solution code:
import sys
import itertools
sys.setrecursionlimit(10000)
def resolve():
    N = int(input())
    Reds = sorted([list(map(int, input().split(" "))) for i in range(N)], key=lambda x: x[1], reverse=True)
    Blues = sorted([list(map(int, input().split(" "))) for i in range(N)], key=lambda x: x[1])
    used = []
    for red in Reds:
        for blue in Blues:
            if blue not in used and able_to_be_pair(red, blue):
                used.append(blue)
                break
    print(len(used))

def able_to_be_pair(red, blue):
    return True if (blue[0] - red[0]) > 0 and (blue[1] - red[1]) > 0 else False

if '__main__' == __name__:
    resolve()

Submission status: Wrong Answer

Solution code:
from collections import deque
from copy import copy,deepcopy
from itertools import permutations,combinations
from pprint import pprint

def myinput():
    return map(int,input().split())

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col):
    data.sort(key=lambda x:x[col],reverse=False)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

n = int(input())
ab = [ list(myinput()) for _ in range(n) ]
cd = [ list(myinput()) for _ in range(n) ]

count = 0
for i in range(n):
    cd_sorted = mysort(cd,0)
    bx = cd[0][0]
    by = cd[0][1]
    cd.remove([bx,by])
    ab.sort(key=lambda x:x[1],reverse=True)
    print(cd)
    print(ab)
    for j in range(len(ab)):
        rx = ab[j][0]
        ry = ab[j][1]
        if rx<bx and ry<by:
            count += 1
            ab.remove([rx,ry])
            break
        else:
            pass
print(count)

Submission status: Wrong Answer

Solution code:
from collections import deque
from copy import copy,deepcopy
from itertools import permutations,combinations
from pprint import pprint

def myinput():
    return map(int,input().split())

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col):
    data.sort(key=lambda x:x[col],reverse=False)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

n = int(input())
ab = [ list(myinput()) for _ in range(n) ]
cd = [ list(myinput()) for _ in range(n) ]

count = 0
for i in range(n):
    cd_sorted = mysort(cd,0)
    bx = cd[0][0]
    by = cd[0][1]
    cd.remove([bx,by])
    ab.sort(key=lambda x:x[1],reverse=True)
    for j in range(len(ab)):
        rx = ab[j][0]
        ry = ab[j][1]
        if rx<bx and ry<by:
            count += 1
            break
        else:
            pass
    ab.remove([rx,ry])
print(count)

Submission status: Wrong Answer

Solution code:
from collections import deque
from copy import copy,deepcopy
from itertools import permutations,combinations
from pprint import pprint

def myinput():
    return map(int,input().split())

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col):
    data.sort(key=lambda x:x[col],reverse=False)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

n = int(input())
ab = [ list(myinput()) for _ in range(n) ]
cd = [ list(myinput()) for _ in range(n) ]

ab.sort(key=lambda x:x[1],reverse=True)

count = 0
for i in range(n):
    cd_sorted = mysort(cd,0)
    bx = cd[0][0]
    by = cd[0][1]
    cd.remove([bx,by])
    for j in range(len(ab)):
        rx = ab[j][0]
        ry = ab[j][1]
        if rx<bx and ry<by:
            count += 1
            break
        else:
            pass
    ab.remove([rx,ry])
print(count)

Submission status: Wrong Answer

Solution code:
from heapq import heapify, heappop, heappush
n = int(input())
ab = [list(map(int, input().split())) for _ in range(n)]
cd = [list(map(int, input().split())) for _ in range(n)]
A = [[x, y, 0] for x, y in ab]
B = [[x, y, 1] for x, y in cd]
abcd = A+B
abcd.sort()

a = [float('inf')]
heapify(a)
result = 0
for i in range(2*n):
    x, y, h = abcd[i]
    if h==0:
        heappush(a, -y)
    else:
        a_y = heappop(a)
        h = []
        while y-a_y < 0:
            h.append(a_y)
            if len(a) > 0:
                a_y = heappop(a)
            else:
                break
        if y-a_y>0:
            result += 1
        for j in h:
            heappush(a, j)
        
print(result)

Submission status: Wrong Answer

Solution code:
# XとYの二部グラフの最大マッチング X={0,1,2,...|X|-1} Y={0,1,2,...,|Y|-1}
#   edges[x]: xとつながるYの頂点のset
#   matched[y]: yとマッチングされたXの頂点(暫定)
 
def dfs(v, visited):
    """
    :param v: X側の未マッチングの頂点の1つ
    :param visited: 空のsetを渡す（外部からの呼び出し時）
    :return: 増大路が見つかればTrue
    """
    for u in edges[v]:
        if u in visited:
            continue
        visited.add(u)
        if matched[u] == -1 or dfs(matched[u], visited):
            matched[u] = v
            return True
    return False
 
 
# 標準入力からのグラフ読み取り
n = int(input())

r = [[0,0] for i in range(n)]
for i in range(n) :
  x,y = map(int,input().split())
  r[i][0],r[i][1] = x,y
  
b = [[0,0] for i in range(n)]
for i in range(n) :
  x,y = map(int,input().split())
  b[i][0],b[i][1] = x,y

xn,yn = n,n,
edges = [set() for _ in range(xn)]
matched = [-1] * yn
  
for i in range(n) :
  for j in range(n) :
    if r[i] < b[j] :
      edges[i].add(j)
 
# 増大路発見に成功したらTrue(=1)。合計することでマッチング数となる
print(sum(dfs(s, set()) for s in range(xn)))

Submission status: Wrong Answer

Solution code:
import sys
from io import StringIO
import unittest

def resolve():
    # ★get input
    n = int(input())
    red = [[int(i) for i in input().split()] for j in range(n)]
    blue = [[int(i) for i in input().split()] for j in range(n)]

    # # redに次元を追加。(以下の処理で、redの内容が更新される。
    # for i in red:
    #     i.append(0)

    for i in red:

        matching_count = 0

        for j in blue:
            if i[0] < j[0] and i[1] < j[1]:
                matching_count += 1

        i.append(matching_count)

    # redをマッチング数の昇順でソートする
    red.sort(key=lambda xx: xx[2])

    ans = 0
    for i in red:
        for j in blue:
            if i[0] < j[0] and i[1] < j[1]:
                blue.remove(j)
                ans += 1
                break

    print(ans)
    # ★exec
    # 各点が作れるペア数を確認。



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:
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(ab,reverse=True)
cd=sorted(cd,reverse=True)

cnt=0
for i in range(n):#ab
    for j in range(len(cd)):#cd
        if ab[i][0]<cd[j][0] and ab[i][1]<cd[j][1]:
            cnt+=1
            cd.pop(j)
            break
print(cnt)

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(ab,reverse=True)
cd=sorted(cd)

cnt=0
for i in range(n):#ab
    for j in range(len(cd)):#cd
        if ab[i][0]<cd[j][0] and ab[i][1]<cd[j][1]:
            cnt+=1
            cd.pop(j)
            break
print(cnt)

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(ab)
cd.sort(key=lambda x: x[0],reverse=True)
cd.sort(key=lambda x: x[1])

cnt=0
for i in range(n):#ab
    for j in range(len(cd)):#cd
        if ab[i][0]<cd[j][0] and ab[i][1]<cd[j][1]:
            cnt+=1
            cd.pop(j)
            break
print(cnt)

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(key=lambda x: x[0])
ab.sort(key=lambda x: x[1])
cd.sort(key=lambda x: x[0])
cd.sort(key=lambda x: x[1])
cnt=0
for i in range(n):#ab
    for j in range(len(cd)):#cd
        if ab[i][0]<cd[j][0] and ab[i][1]<cd[j][1]:
            cnt+=1
            cd.pop(j)
            break
print(cnt)

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(key=lambda x: x[1])
cd.sort(key=lambda x: x[1])
cnt=0
for i in range(n):#ab
    for j in range(len(cd)):#cd
        if ab[i][0]<cd[j][0] and ab[i][1]<cd[j][1]:
            cnt+=1
            cd.pop(j)
            break
print(cnt)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    n = int(input())
    red, blue = [-1]*2*n, [-1]*2*n

    for _ in range(n):
        a,b = map(int, input().split())
        red[a] = b
    for _ in range(n):
        a,b = map(int, input().split())
        blue[a] = b

    kouho = []
    res = 0
    for i in range(2*n-1, -1, -1):
        if blue[i] >= 0:
            kouho.append(blue[i])
        else:
            kouho.sort()
            for i in range(len(kouho)):
                if red[i] < kouho[i]:
                    kouho.pop(i)
                    res += 1
                    break
    print(res)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math
from fractions import gcd

NN = 202020
MOD = 10**9+7
INF = float("inf")

n = int(input())
A = [list(map(int, input().split())) for i in range(n)]
B = [list(map(int, input().split())) for i in range(n)]

used = [False]*n
A.sort()
B.sort()
count = 0
for i in range(len(B)):
    cand = [-1, -1]
    cand_idx = -1
    for j in range(len(A)):
        if A[j][0] < B[i][0]:
            # print(used[j], cand[1], A[j][1])
            if (not used[j]) and (cand[1] < A[j][1]):
                cand = A[j]
                cand_idx = j
        else:
            break

    if cand_idx != -1:
        count += 1
        used[cand_idx] = True

print(count)

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()))+[1] for _ in range(N)]

AB=sorted(ab, key=lambda x:x[1], reverse=True)
CD=sorted(cd, key=lambda x:x[0], reverse=True)
cnt=0

for i in range(N):
  for j in range(N):
    if AB[i][0]<CD[j][0] and AB[i][1]<CD[j][1] and CD[j][2] ==1:
      cnt+=1
      CD[j][2]-=1
      break
      
print(cnt)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = [list(map(int, input().split())) for _ in range(n)]
t = [list(map(int, input().split()))+[1] for _ in range(n)]

ss = sorted(s, key=lambda x:(x[0], x[1]), reverse=True)
tt = sorted(t, key=lambda x:(x[0], x[1]))
cnt = 0

for i in range(n):
  for j in range(n):
    if ss[i][0] < tt[j][0] and ss[i][1] < tt[j][1] and tt[j][2] == 1:
      cnt += 1
      tt[j][2] -= 1
      break
    
print(cnt)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = [list(map(int, input().split())) for _ in range(n)]
t = [list(map(int, input().split()))+[1] for _ in range(n)]

ss = sorted(s, key=lambda x:(x[0], x[1]), reverse=True)
tt = sorted(t, key=lambda x:(x[0], x[1]), reverse=True)
cnt = 0
bmin = n*3
for i in range(n):
  for j in range(n):
    if ss[i][0] < tt[j][0] and ss[i][1] < tt[j][1] and tt[j][2] == 1 and bmin > tt[j][1]:
      cnt += 1
      tt[j][2] -= 1
      break
    
print(cnt)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = [list(map(int, input().split())) for _ in range(n)]
t = [list(map(int, input().split()))+[1] for _ in range(n)]

ss = sorted(s, key=lambda x:(x[0], x[1]), reverse=True)
tt = sorted(t, key=lambda x:(x[0], x[1]), reverse=True)
cnt = 0

for i in range(n):
  for j in range(n):
    if ss[i][0] < tt[j][0] and ss[i][1] < tt[j][1] and tt[j][2] == 1:
      cnt += 1
      tt[j][2] -= 1
      break
    
print(cnt)

Submission status: Wrong Answer

Solution code:
import math
import collections
from operator import mul
from functools import reduce
import bisect
import string
import copy

n=int(input())
r=[(0,0)]*n
b=[(0,0)]*n
for i in range(n):
    r[i]=tuple(map(int,input().split()))
for i in range(n):
    b[i]=tuple(map(int,input().split()))
r=sorted(r)
b=sorted(b)
y=0

for i in range(0,n)[::-1]:
    ind=bisect.bisect(b,r[i])
    if len(b)>ind:
         y+=1
         b.pop(ind)



print(y)

Submission status: Wrong Answer

Solution code:
import math
import collections
from operator import mul
from functools import reduce
import bisect
import string
import copy

n=int(input())
r=[(0,0)]*n
b=[(0,0)]*n
for i in range(n):
    r[i]=tuple(map(int,input().split()))
for i in range(n):
    b[i]=tuple(map(int,input().split()))
r=sorted(r)
b=sorted(b)
y=0
for ri in r:
     ind=bisect.bisect(b,ri)
     if len(b)>ind:
         y+=1
         b.pop(ind)



print(y)

Submission status: Wrong Answer

Solution code:
import math
import collections
from operator import mul
from functools import reduce
import bisect
import string
import copy

n=int(input())
r=[(0,0)]*n
b=[(0,0)]*n
for i in range(n):
    r[i]=tuple(map(int,input().split()))
for i in range(n):
    b[i]=tuple(map(int,input().split()))
r=sorted(r)
b=sorted(b)
y=0
indr=n-1
indb=n-1
while indr>=0 and indb>=0:
    if r[indr][0]<b[indb][0] and r[indr][1]<b[indb][1]:
        y+=1
        indr-=1 
        indb-=1
    else:
        indr-=1


print(y)

Submission status: Wrong Answer

Solution code:
n=int(input())
ab=[tuple(map(int,input().split())) for i in range(n)]
cd=[tuple(map(int,input().split())) for i in range(n)]
ab.sort(key=lambda x: x[0]*x[1],reverse=True)
ab.sort(key=lambda x: x[0]+x[1],reverse=True)
cd.sort(key=lambda x: x[0]*x[1])
cd.sort(key=lambda x: x[0]+x[1])
check=[False]*n
def isOK(i,j):
    global ab,cd,check
    return ab[i][0]<cd[j][0] and ab[i][1]<cd[j][1]
for i in range(n):
    for j in range(n):
        if not check[j] and isOK(i,j):
            check[j]=True
            break
print(sum(check))

Submission status: Wrong Answer

Solution code:
n=int(input())
ab=[tuple(map(int,input().split())) for i in range(n)]
cd=[tuple(map(int,input().split())) for i in range(n)]
ab.sort(key=lambda x: x[0],reverse=True)
cd.sort(key=lambda x: x[0])
check1=[False]*n
check2=[False]*n
def isOK(i,j):
    global ab,cd,check1,check2
    return ab[i][0]<cd[j][0] and ab[i][1]<cd[j][1]
for i in range(n):
    for j in range(n):
        if not check1[j] and isOK(i,j):
            check1[j]=True
            break
ab.sort(key=lambda x: x[1],reverse=True)
cd.sort(key=lambda x: x[1])
for i in range(n):
    for j in range(n):
        if not check2[j] and isOK(i,j):
            check2[j]=True
            break
print(max(sum(check1),sum(check2)))

Submission status: Wrong Answer

Solution code:
n=int(input())
ab=[tuple(map(int,input().split())) for i in range(n)]
cd=[tuple(map(int,input().split())) for i in range(n)]
ab.sort(key=lambda x: x[0]*x[1],reverse=True)
cd.sort(key=lambda x: x[0]*x[1])
check=[False]*n
def isOK(i,j):
    global ab,cd,check
    return ab[i][0]<cd[j][0] and ab[i][1]<cd[j][1]
for i in range(n):
    for j in range(n):
        if not check[j] and isOK(i,j):
            check[j]=True
            break
print(sum(check))

Submission status: Wrong Answer

Solution code:
n=int(input())
ab=[tuple(map(int,input().split())) for i in range(n)]
cd=[tuple(map(int,input().split())) for i in range(n)]
ab.sort(key=lambda x: x[0]+x[1],reverse=True)
cd.sort(key=lambda x: x[0]+x[1])
check=[False]*n
def isOK(i,j):
    global ab,cd,check
    return ab[i][0]<cd[j][0] and ab[i][1]<cd[j][1]
for i in range(n):
    for j in range(n):
        if not check[j] and isOK(j,i):
            check[j]=True
            break
print(sum(check))

Submission status: Wrong Answer

Solution code:
n=int(input())
ab=[tuple(map(int,input().split())) for i in range(n)]
ab.sort(key=lambda x: x[0]+x[1],reverse=True)
cd=[tuple(map(int,input().split())) for i in range(n)]
cd.sort(key=lambda x: x[0]+x[1])
check=[False]*n
def isOK(i,j):
    global ab,cd,check
    return ab[i][0]<cd[j][0] and ab[i][1]<cd[j][1]
for i in range(n):
    for j in range(n):
        if not check[j] and isOK(i,j):
            check[j]=True
            break
print(sum(check))

Submission status: Wrong Answer

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

from operator import itemgetter

red=sorted(red)
blue=sorted(blue,key=itemgetter(1))
seen=[0]*n
ans=0
for i in range(n):
    for j in range(n):
        if seen[j]==0 and red[i][0]<blue[j][0] and red[i][1]<blue[j][1]:
            seen[j]=1
            ans+=1
            break

print(ans)

Submission status: Wrong Answer

Solution code:
#91c
N = int(input()) #N<=100

red_points = list()
for i in range(N):
    a,b = map(int, input().split())
    red_points.append((a,b))
    
blue_points = list()
for i in range(N):
    c,d = map(int, input().split())
    blue_points.append((c,d))
    
#赤い点と青い点は，
# 赤い点の x 座標が青い点の x 座標より小さく， また
# 赤い点の y 座標も青い点の y座標より小さい    とき，
#仲良しペアになれます。
#あなたは最大で何個の仲良しペアを作ることができますか？ ただし，1つの点が複数のペアに所属することはできません。

#100*100 = 10**4ループを回して、ペアになれる点同士を算出
pairable_dict = dict() #key:red_point , value:pairable blue point
for red_point in red_points:
    pairable_dict[red_point] = set()
    red_point_x = red_point[0]
    red_point_y = red_point[1]
    for blue_point in blue_points:
        blue_point_x = blue_point[0]
        blue_point_y = blue_point[1]
        if red_point_x < blue_point_x and red_point_y < blue_point_y: 
            pairable_dict[red_point].add(blue_point)
            
#print(pairable_dict)


pair_dict = dict() #key:red_point , value:paired blue point
used_blue_points = set()

#ペアになれる相手が単独なら確定していく
def make_unique_pair():
    for pair in pairable_dict.items():
        red_point = pair[0]
        blue_points = pair[1]
        blue_points = blue_points - (blue_points&used_blue_points)
        
        #print(red_point,blue_points)
        
        if len(blue_points) == 1:
            #print("paired")
            blue_point = blue_points.pop()
            pair_dict[red_point] = blue_point
            used_blue_points.add(blue_point)
            pairable_dict[red_point] = set()
            make_unique_pair()

#単独ペア確定後は、近い点からやっていく
def make_pair():
    for pair in pairable_dict.items():
        red_point = pair[0]
        blue_points = pair[1]
        blue_points = blue_points - (blue_points&used_blue_points)
        
        if len(blue_points) != 0:
            #最も近い点を使う
            min_d_point = blue_points.pop()
            min_distance = min_d_point[0]**2 + min_d_point[1]**2
            
            for blue_point in blue_points:
                if blue_point[0]**2 + blue_point[1]**2 < min_distance:
                    min_distance = blue_point[0]**2 + blue_point[1]**2
                    min_d_point = blue_point
                    
            pair_dict[red_point] = min_d_point
            used_blue_points.add(min_d_point)
            pairable_dict[red_point] = set()
            make_pair()            
            
make_unique_pair()
make_pair()

print(len(pair_dict))
#print(pair_dict)

Submission status: Wrong Answer

Solution code:
n = int(input())
A = []
B = []
for i in range(n):
    a,b = map(int,input().split())
    A.append((a+b,a,b))
for i in range(n):
    a,b = map(int,input().split())
    B.append((a+b,a,b))
A.sort(reverse=True)
B.sort(reverse=True)
A1 = A
B1 = B[::-1]
ans = 0
ans2 = 0
for i in B:
    dis = 1000000
    check = -1
    for j in range(len(A)):
        if i[1] > A[j][1] and i[2] > A[j][2]:
            
            if dis > i[0]-A[j][0]:
                check = j
                dis = i[0]-A[j][0]
    if check > -1:
        ans += 1
        A.pop(check)
for i in B1:
    dis = 1000000
    check = -1
    for j in range(len(A1)):
        if i[1] > A1[j][1] and i[2] > A1[j][2]:
            
            if dis > i[0]-A1[j][0]:
                check = j
                dis = i[0]-A1[j][0]
    if check > -1:
        ans2 += 1
        A1.pop(check)
print(max(ans,ans2))

Submission status: Wrong Answer

Solution code:
n = int(input())
A = []
B = []
for i in range(n):
    a,b = map(int,input().split())
    A.append((a+b,a,b))
for i in range(n):
    a,b = map(int,input().split())
    B.append((a+b,a,b))
A.sort(reverse=True)
B.sort(reverse=True)
ans = 0

for i in B:
    dis = 1000000
    check = -1
    for j in range(len(A)):
        if i[1] > A[j][1] and i[2] > A[j][2]:
            
            if dis > i[0]-A[j][0]:
                check = j
                dis = i[0]-A[j][0]
    if check > -1:
        ans += 1
        A.pop(check)
print(ans)

Submission status: Wrong Answer

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

from operator import itemgetter
ab.sort(key=itemgetter(1))
cd.sort(key=itemgetter(0))

C = [0] * N
cnt = 0
for i in range(N):
    for j in range(N):
        if C[i] == 0 and ab[- j - 1][0] < cd[i][0] and ab[ - j - 1][1] < cd[i][1]:
            C[i] = 1
            cnt += 1
            break
print(cnt)

Submission status: Wrong Answer

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

from operator import itemgetter
ab.sort(key=itemgetter(1))
cd.sort(key=itemgetter(0))

C = [0] * N
cnt = 0
for i in range(N):
    for j in range(N):
        if C[j] == 0 and ab[- j - 1][0] < cd[i][0] and ab[ - j - 1][1] < cd[i][1]:
            C[i] = 1
            cnt += 1
            break
print(cnt)

Submission status: Wrong Answer

Solution code:
from sys import stdin

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

ab.sort()
cd.sort()

used_cd = [0] * N
inf = 10 ** 9
tmp = 0
debug = []

for i in range(N):
    dist = inf
    a, b = ab[i]
    pair = False
    for j in range(N):
        if used_cd[j] == 1:
            continue
        c, d = cd[j]
        if a < c and b < d:
            if min(c - a, d - b) < dist:
                dist = min(c - a, d - b)
                tmp = j
                pair = True
    if pair:
        debug.append([ab[i], cd[tmp]])
        used_cd[tmp] = 1

# print(debug)
print(used_cd.count(1))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-


def main():
    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()
    red, blue = [], []

    for ab in AB:
        for cd in CD:
            if ab[0] < cd[0] and ab[1] < cd[1]:
                if ab not in red and cd not in blue:
                    red.append(ab)
                    blue.append(cd)
    print(len(red))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

#S = [[0 for i in range(2*N)] for j in range(2*N)]
DR, DB, DX, DY = {}, {}, {}, {}
'''for i in range(N):
  S[R[i][0]][R[i][1]] = 1
  S[B[i][0]][B[i][1]] = 2'''

for i in range(N):
  DR[R[i][0]] = R[i][1]
  DX[R[i][0]] = [0]
  DB[B[i][0]] = B[i][1]
P = 0

for i in DB:
  L = []
  for j in DR:
    if i > j and DB[i] > DR[j]:
      DX[j][0] += 1
      DX[j].append(i)
      L.append(j)
  DY[i] = L[:]

for i in DX:
  if DX[i][0] == N:
    P += 1
    for j in DY:
      if i in DY[j]:
        DY[j].remove(i)
    DX[i] = [0]
cnt = 0
for i in DY:
  if DY[i] != []:
    cnt += 1

while cnt != 0:
  cnt = 0
  for i in DX:
    if DX[i][0] == 1:
      s = DX[i][1]
      cnt += 1
      DY[DX[i][1]] = []
      P += 1
      for j in DX:
        if s in DX[j]:
          DX[j].remove(s)
          DX[j][0] -= 1
      DX[i] = [0]
DZ = {}
for i in DY:
  if DY[i] != []:
    DZ[i] = DY[i][:]
XX = int(1e+9)
for i in DX:
  if XX > DX[i][0] and DX[i][0] != 0:
    XX = DX[i][0]
P += min(len(DZ), XX)
print(P)

Submission status: Wrong Answer

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

#S = [[0 for i in range(2*N)] for j in range(2*N)]
DR, DB, DX, DY = {}, {}, {}, {}
'''for i in range(N):
  S[R[i][0]][R[i][1]] = 1
  S[B[i][0]][B[i][1]] = 2'''

for i in range(N):
  DR[R[i][0]] = R[i][1]
  DX[R[i][0]] = [0]
  DB[B[i][0]] = B[i][1]
P = 0

for i in DB:
  L = []
  for j in DR:
    if i > j and DB[i] > DR[j]:
      DX[j][0] += 1
      DX[j].append(i)
      L.append(j)
  DY[i] = L[:]

for i in DX:
  if DX[i][0] == N:
    P += 1
    for j in DY:
      if i in DY[j]:
        DY[j].remove(i)
    DX[i] = [0]
cnt = 0
for i in DY:
  if DY[i] != []:
    cnt += 1

while cnt != 0:
  cnt = 0
  for i in DX:
    if DX[i][0] == 1:
      s = DX[i][1]
      cnt += 1
      DY[DX[i][1]] = []
      P += 1
      for j in DX:
        if s in DX[j]:
          DX[j].remove(s)
          DX[j][0] -= 1
      DX[i] = [0]
for i in DY:
  if DY[i] != []:
    P += 1
print(P)

Submission status: Wrong Answer

Solution code:
casen=0
if casen==0:
    a=[]
    c=[]
    n=int(input())
    for i in range(n):
        ai,bi=map(int,input().split())
        a.append([ai,bi])
    for i in range(n):
        ci,di=map(int,input().split())
        c.append([ci,di])
elif casen==1:
    n=3
    a=[[2,0],[3,1],[1,3]]
    c=[[4,2],[0,4],[5,5]]
elif casen==2:
    n=3
    a=[[0,0],[1,1],[5,2]]
    c=[[2,3],[3,4],[4,5]]
elif casen==3:
    n=2
    a=[[2,2],[3,3]]
    c=[[0,0],[1,1]]
elif casen==4:
    n=5
    a=[[0,0],[7,3],[2,2],[4,8],[1,6]]
    c=[[8,5],[6,9],[5,4],[9,1],[3,7]]
elif casen==5:
    n=5
    a=[[0,0],[1,1],[5,5],[6,6],[7,7]]
    c=[[2,2],[3,3],[4,4],[8,8],[9,9]]

a.sort()
c.sort(key=lambda x:x[1])

icnt=0
ic2=0
for ia in range(len(a)):
    for ic in range(len(c)):
        if a[ia][0]<c[ic][0] and a[ia][1]<c[ic][1]:
            icnt=icnt+1
            del c[ic]
            break
        else:
            continue
        break

print(icnt)

Submission status: Wrong Answer

Solution code:
casen=0
if casen==0:
    a=[]
    c=[]
    n=int(input())
    for i in range(n):
        ai,bi=map(int,input().split())
        a.append([ai,bi])
    for i in range(n):
        ci,di=map(int,input().split())
        c.append([ci,di])
elif casen==1:
    n=3
    a=[[2,0],[3,1],[1,3]]
    c=[[4,2],[0,4],[5,5]]
elif casen==2:
    n=3
    a=[[0,0],[1,1],[5,2]]
    c=[[2,3],[3,4],[4,5]]
elif casen==3:
    n=2
    a=[[2,2],[3,3]]
    c=[[0,0],[1,1]]
elif casen==4:
    n=5
    a=[[0,0],[7,3],[2,2],[4,8],[1,6]]
    c=[[8,5],[6,9],[5,4],[9,1],[3,7]]
elif casen==5:
    n=5
    a=[[0,0],[1,1],[5,5],[6,6],[7,7]]
    c=[[2,2],[3,3],[4,4],[8,8],[9,9]]

a.sort()
c.sort()

t=[]
for ia in range(n):
    s=[]
    for ic in range(n):
        if a[ia][0]<c[ic][0] and a[ia][1]<c[ic][1]:
            s.append(ic)
    t.append([len(s),s])
    
t.sort()

tyn=[0]*n

icnt=0
for ia in range(n):
#    print(ia,t[ia][1])
    for it in t[ia][1]:
#        print(ia,it,tyn[it])
        if tyn[it]==0 :
            icnt=icnt+1
            tyn[it]=1
            break

print(icnt)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter

n = int(input())
r = [tuple(map(int, input().split())) for i in range(n)]
b = [tuple(map(int, input().split())) for i in range(n)]

r = sorted(r, key=itemgetter(1), reverse=True)
b.sort()

ans = 0
pair = [False]*n

for i in range(n):
    for j in range(n):
        if b[i][0] > r[j][0] and b[i][1] > r[j][1] and pair[j] == False:
            pair[i] = True
            ans += 1
            break

print(ans)