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: Runtime Error

Solution code:
 N = int(input())
 ab = sorted([ tuple(map(int, input().split())) for x in range(N)], key=lambda x:x[1], reverse=True)
 cd = sorted([ tuple(map(int, input().split())) for x in range(N)])
 resultx = []
 resulty = []
 for xb, yb in list(cd):
     for xr, yr in list(ab):
         if (xr, yr) in resultx:
             continue
         if xr < xb and yr < yb:
             resultx.append((xr,yr))
             resulty.append((xb,yb))
             break

 print(len(resultx))

Submission status: Runtime Error

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)]
 result = []
 for i in range(N):
     xr , yr = ab[i]
     xb, yb = cd[i]
     if xr < xb or yr < yb:
         print(xr, yr, xb, yb)
         result.append('BINGO!!!')
 print(len(result))

Submission status: Runtime Error

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)]
 result = []
 for i in range(N):
     xr , yr = ab[i]
     xb, yb = cd[i]
     if xr < xb or yr < yb:
        print(xr, yr, xb, yb)
        result.append('BINGO!!!')
 print(len(result))

Submission status: Runtime Error

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)]
 result = []
 for i in range(N):
     xr , yr = ab[i]
     xb, yb = cd[i]
     if xr < xb and yr < yb:
         result.append('BINGO!!!')
 print(len(result))

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().split()))

sum_even = sum(map(lambda i: A[i] if A[i] > 0 else 0, range(1, N, 2)))
sum_odd  = sum(map(lambda i: A[i] if A[i] > 0 else 0, range(0, N, 2)))

if sum_even == 0 and sum_odd == 0:
    max_ = max(A)
    print(max_)
    index = A.index(max_)
    print(len(A)-1)
    for _ in range(index):
        print(1)
    for j in range(N-index-1):
        print(N - index - j)
    exit()

print(max(sum_even, sum_odd))
EVEN = sum_even >= sum_odd
ans = []

if EVEN:
    A = A[1:]
    ans.append(1)
if len(A)%2 == 0:
    ans.append(len(A))
    A = A[:-1]

while len(A) > 1:
    if A[0] <= 0:
        ans.append(1)
        ans.append(1)
        A = A[2:]
    else:
        if A[2] <= 0:
            ans.append(3)
            A.pop(2)
            if len(A) == 2:
                ans.append(2)
                A.pop(1)
            else:
                ans.append(3)
                A.pop(2)
        else:
            ans.append(2)
            A.pop(1)
            A[0] += A.pop(1)
print(len(ans))
for a in ans:
    print(a)

Submission status: Runtime Error

Solution code:
    def Contest092C(self):
        number = int(input())
        list = []
        num = 0
        for i in range(number):
            list.append(input())

        for j in range(number):
            temp = input()
            if temp[0] > list[j][0] and temp[2] > list[j][2]:
                num += 1
        return num
if __name__ == '__main__':
    atcoder = Atcoder()
    print(atcoder.Contest092C())

Submission status: Runtime Error

Solution code:
   def Contest092C(self):
        number = int(input())
        print(type(number))
        list = []
        num = 0
        for i in range(number):
            list.append(input())

        for j in range(number):
            temp = input()
            if temp[0] > list[j][0] and temp[2] > list[j][2]:
                num += 1
        return num
if __name__ == '__main__':
    atcoder = Atcoder()
    print(atcoder.Contest092C())

Submission status: Runtime Error

Solution code:
# C
N = int(input())

red_list = []
blue_list = []

for _ in range(N):
    x, y = map(int, input().split())
    red_list.append([x, y])

for _ in range(N):
    x, y = map(int, input().split())
    blue_list.append([x, y])
    
GR = dict()
GB = dict()

for i in range(N):
    GR[i+1] = [0, [], 0]
    GB[i+1] = [0, [], 0]

for i in range(N):
    for j in range(N):
        if red_list[i][0] < blue_list[j][0] and red_list[i][1] < blue_list[j][1]:
            GR[i+1][1].append(j+1)
            GB[j+1][1].append(i+1)
            
def find_path(GR_, GB_, N):
    GR = GR_.copy()
    GB = GB_.copy()

    done_red = [0]*(N+1)
    can_red = [0]*(N+1)
    done_blue = [0]*(N+1)

    # start from RED
    for i in range(1, N+1): 
        if GR[i][0] == 0:
            can_red[i] = 1
        GR[i][2] = -1
        GB[i][2] = -1

    while True:

        go_flg = 0
        for i in range(1, N+1):
            if can_red[i] == 1 and done_red[i] == 0:
                go_flg = 1

        if go_flg == 0:
            return []

        for i in range(1, N+1): 
            if can_red[i] == 1 and done_red[i] == 0:
                done_red[i] = 1
                for j in GR[i][1]:
                    if done_blue[j] == 0:
                        GB[j][2] = i
                        done_blue[j] = 1
                        if GB[j][0] != 0:
                            can_red[GB[i][0]] = 1
                            GR[GB[j][0]][2] = j
                        else:
                            # found
                            res_list = [j, i]
                            while res_list[-1] > 0:
                                j = GR[res_list[-1]][2]
                                i = GB[j][2]
                                res_list.append(j)
                                res_list.append(i)
                            return res_list
                        
# set initial path
res = 0
for i in range(1, N+1):
    for j in GR[i][1]:
        if GB[j][0] == 0:
            GR[i][0] = j
            GB[j][0] = i
            res += 1
            break

while True:
    new_path = find_path(GR, GB, N)
    if len(new_path) == 0:
        break
    else:
        for l in len(new_path) // 2:
            j, i = 2*l, 2*l+1
            GB[j][0] = i
            GB[i][0] = j
        res += 1

print(res)

Submission status: Runtime Error

Solution code:
# C
N = int(input())

red_list = []
blue_list = []

for _ in range(N):
    x, y = map(int, input().split())
    red_list.append([x, y])

for _ in range(N):
    x, y = map(int, input().split())
    blue_list.append([x, y])
    
GR = dict()
GB = dict()

for i in range(N):
    GR[i+1] = [0, [], 0]
    GB[i+1] = [0, [], 0]

for i in range(N):
    for j in range(N):
        if red_list[i][0] < blue_list[j][0] and red_list[i][1] < blue_list[j][1]:
            GR[i+1][1].append(j+1)
            GB[j+1][1].append(i+1)
            
def find_path(GR_, GB_, N):
    GR = GR_.copy()
    GB = GB_.copy()

    done_red = [0]*(N+1)
    can_red = [0]*(N+1)
    done_blue = [0]*(N+1)

    # start from RED
    for i in range(1, N+1): 
        if GR[i][0] == 0:
            can_red[i] = 1
        GR[i][2] = -1
        GB[i][2] = -1

    while True:

        go_flg = 0
        for i in range(1, N+1):
            if can_red[i] == 1 and done_red[i] == 0:
                go_flg = 1

        if go_flg == 0:
            return []

        for i in range(1, N+1): 
            if can_red[i] == 1 and done_red[i] == 0:
                done_red[i] = 1
                for j in GR[i][1]:
                    if done_blue[j] == 0:
                        GB[j][2] = i
                        done_blue[j] = 1
                        if GB[j][0] != 0:
                            can_red[GB[i][0]] = 1
                        else:
                            # found
                            res_list = [j, i]
                            while res_list[-1] > 0:
                                j = GR[res_list[-1]][2]
                                i = GB[j][2]
                                res_list.append(j)
                                res_list.append(i)
                            return res_list
                        
# set initial path
res = 0
for i in range(1, N+1):
    for j in GR[i][1]:
        if GB[j][0] == 0:
            GR[i][0] = j
            GB[j][0] = i
            res += 1
            break

while True:
    new_path = find_path(GR, GB, N)
    if len(new_path) == 0:
        break
    else:
        for l in len(new_path) // 2:
            j, i = 2*l, 2*l+1
            GB[j][0] = i
            GB[i][0] = j
        res += 1

print(res)

Submission status: Runtime Error

Solution code:
def get_edge(M, u, U=None):
    if U == None:
        for x in M[:]:
            if x[0] == u:
                return x[1]
            elif x[1] == u:
                return x[0]

    else:
        for x in M[:]:
            if x[0] == u and x[1] in U:
                return x[1]
            elif x[1] == u and x[0] in U:
                return x[0]
    return None


def get_nodes(M):
    U = set()
    V = set()
    for x in M:
        U.add(x[0])
        V.add(x[1])
    return (U, V)


def augpath(Si, Ti, M, E):
    (U, V) = get_nodes(M)
    Ti1 = set(x[1] for x in E if x[0] in Si and not x[1] in Ti)

    if Ti1 == set():
        return (M, None)

    elif Ti1.difference(V) == set():
        Si1 = set(x[0] for x in M if x[1] in Ti1)
        (M, ui1) = augpath(Si1, Ti.union(Ti1), M, E)

        if ui1 == None:
            return (M, None)

        else:
            v = get_edge(M, ui1)
            M.remove((ui1, v))

            ui = get_edge(E, v, U=Si)
            M.append((ui, v))

            return (M, ui)

    else:
        v = Ti1.difference(V).pop()
        u = get_edge(E, v, U=Si)
        M.append((u, v))

        return (M, u)


def Hungary(U0, V0, E):
    U_bef = set()
    M = []
    cnt = 0
    length = len(U0)

    # CALC
    while True:

        # INIT
        (U, V) = get_nodes(M)
        u = U0[cnt % length]
        cnt = cnt + 1
        S0 = set()
        S0.add(u)
        T0 = set()

        # 終了条件(すべての頂点から始まる増大道を調べて、マッチング数が変わっていなければ、それ以上増えることはない)
        if cnt % length == 0:
            if U.difference(U_bef) == set():
                break
            U_bef = U.copy()

        # 枝刈り(すでにマッチングしている頂点から始まる道は増大道ではない)
        if u in U:
            continue

        # CALC
        (M, u) = augpath(S0, T0, M, E)

    return M


N = int(input())
red = [list(map(int,input().split())) for _ in range(N)]
blue = [list(map(int,input().split())) for _ in range(N)]
match = []
redg = [i for i in range(N)]
blueg = [i for i in range(N)]

for i in range(N):
    for j in range(N):
        if red[i][0] < blue[j][0] and red[i][1] < blue[j][1]:
            match.append((i, j))

edges = Hungary(redg, blueg, match)
print(len(edges))

Submission status: Runtime Error

Solution code:
N = int(input())
a,b,c,d = [0]*N,[0]*N,[0]*N,[0]*N
for i in range(N):
    a[i],b[i] = map(int,input().split())
for i in range(N):
    c[i],d[i] = map(int,input().split())

ans=0
for k in range(N):
    for i in range(N):
        if a[i] == k or b[i] == k:
            ans += 1
            a.pop(i)
            b.pop(i)
            break
        elif c[i] == k or d[i] == k:
            c.pop(i)
            d.pop(i)

print(ans)