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)]

cand = []
for b in B:
    temp = []
    for i, r in enumerate(R):
        if r[0] < b[0] and r[1] < b[1]:
            temp.append(i)
    cand.append(temp)

# cand = sorted(cand, key=lambda x: len(x))

result = 0
d = [False for _ in range(N)]
while True:
    flag = False
    for c in cand:
        if len(c) == 1:
            flag = True
    cnt = d.count(True)

    if flag:
        for c in cand:
            if 0 < len(c):
                num = c[0]
                if len(c) == 1 and not d[num]:
                    result += 1
                    d[num] = True
                    for i in cand:
                        if num in i:
                            i.remove(num)
            c = []
    else:
        cnt = d.count(True)
        for j, c in enumerate(cand):
            if 0 < len(c):
                num = c[0]

                result += 1
                d[num] = True
                for i in cand:
                    if num in i:
                        i.remove(num)
                cand[j] = []
                break

    if cnt == d.count(True):
        break

print(result)

Submission status: Wrong Answer

Solution code:
import itertools
n=int(input())
red=[]
blue=[]
for i in range(n):
    red.append(list(map(int,input().split())))
    blue.append(list(map(int,input().split())))
perm=list(itertools.permutations(blue))
pair=0
ans=0
for k in perm:
    for m in range(n):
        if int(red[m][0])<int(k[m][0]) and int(red[m][1])<int(k[m][1]):
            pair+=1
    if pair>ans:
        ans=pair
    pair=0
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

# AtCoder Beginner Contest
# Problem C

if __name__ == '__main__':
    number = int(input())

    a_b = [list(map(int, input().split())) for _ in range(number)]
    c_d = [list(map(int, input().split())) for _ in range(number)]

    sorted_a_b = sorted(a_b, key=lambda x: (x[1], x[0]))
    sorted_c_d = sorted(c_d, key=lambda y: (y[1], y[0]))

    count = 0

    for i, (a, b) in enumerate(sorted_a_b):
        print(i, a, b)
        for j, (c, d) in enumerate(sorted_c_d):
            print(j, c, d)
            if (a < c) and (b < d):
                sorted_a_b.pop()
                # print(sorted_a_b)
                sorted_c_d.pop()
                # print(sorted_c_d)
                count += 1

    print(count)

Submission status: Wrong Answer

Solution code:
def abc091_c():
    from operator import itemgetter
    _reds = []
    _blues = []
    _count = 0

    _n = int(input())

    for i in range(_n):
        _instr = str(input()).split()
        _reds.append(list(map(int, _instr)))

    for i in range(_n):
        _instr = str(input()).split()
        _blues.append(list(map(int, _instr)))

    _reds.sort()
    _blues.sort(key=itemgetter(1))
    # print(_reds)
    # print(_blues)
    for i in range(len(_reds)):
        for j in range(len(_blues)):
            if _reds[i][0] >= _blues[j][0]:
                continue
            elif _reds[i][1] < _blues[j][1]:
                _count += 1
                del _blues[j]
                break
            else:
                continue
    print(_count)


abc091_c()

Submission status: Wrong Answer

Solution code:
# http://nobuta05.hatenablog.com/entry/2015/11/12/013938

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)
            if (ui1,v) in M:
                M.remove((ui1,v))

            ui = get_edge(E, v, U=Si)
            if ui:
                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())
AB = [[int(_) for _ in input().split()] for i in range(N)]
CD = [[int(_) for _ in input().split()] for i in range(N)]

"""
from random import randint
N = 100
AB = [(randint(0, N*2), randint(0, N*2)) for i in range(N)]
CD = [(randint(0, N*2), randint(0, N*2)) for i in range(N)]
print(AB)
print(CD)
"""

E = []

for i in range(N):
    for j in range(N):
        if AB[i][0] < CD[j][0] and AB[i][1] < CD[j][1]:
            E.append((i, j))

M = Hungary(list(range(N)), list(range(N)), E)
print(len(M))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

# AtCoder Beginner Contest
# Problem C

if __name__ == '__main__':
    number = int(input())

    a_b = [list(map(int, input().split())) for _ in range(number)]
    c_d = [list(map(int, input().split())) for _ in range(number)]

    sorted_a_b = sorted(a_b, key=lambda x: (x[1], x[0]))
    sorted_c_d = sorted(c_d, key=lambda y: (y[1], y[0]))

    count = 0

    print(sorted_a_b)
    print(sorted_c_d)

    for i, (a, b) in enumerate(sorted_a_b):
        print(i, a, b)
        for j, (c, d) in enumerate(sorted_c_d):
            print(j, c, d)
            if (a < c) and (b < d):
                sorted_a_b.pop()
                # print(sorted_a_b)
                sorted_c_d.pop()
                # print(sorted_c_d)
                count += 1

    print(count)

Submission status: Wrong Answer

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


def solve(AB, CD):
    AB_set = []
    CD_set = []
    for index_ab, ab in enumerate(AB):
        i, j = -1, -1
        if index_ab in AB_set:
            continue
        distance = float('inf')
        for index_cd, cd in enumerate(CD):
            if index_cd in CD_set:
                continue
            if (cd[0] - ab[0] > 0) & (cd[1] - ab[1] > 0) & ((cd[0]-ab[0]) + (cd[1] - ab[1]) < distance):
                distance = (cd[0] - ab[0]) + (cd[1] - ab[1])
                i, j = index_ab, index_cd
        if (i != -1) & (j != -1):
            AB_set.append(i)
            CD_set.append(j)
    return len(AB_set)

AB.sort()
CD.sort()
ans1 = solve(AB, CD)
AB.sort(reverse=True)
CD.sort(reverse=True)
ans2 = solve(AB, CD)
AB.sort(key=lambda x:x[1])
CD.sort(key=lambda x:x[1])
ans3 = solve(AB, CD)
AB.sort(key=lambda x:x[1], reverse=True)
CD.sort(key=lambda x:x[1], reverse=True)
ans4 = solve(AB, CD)
AB.sort()
CD.sort(key=lambda x:x[1])
ans5 = solve(AB, CD)
AB.sort(reverse=True)
CD.sort(key=lambda x:x[1], reverse=True)
ans6 = solve(AB, CD)
AB.sort(key=lambda x:x[1])
CD.sort()
ans7 = solve(AB, CD)
AB.sort(key=lambda x:x[1], reverse=True)
CD.sort(reverse=True)
ans8 = solve(AB, CD)
AB.sort(reverse=True)
CD.sort()
ans9 = solve(AB, CD)
AB.sort()
CD.sort(reverse=True)
ans10 = solve(AB, CD)
AB.sort(key=lambda x:x[1])
CD.sort(reverse=True)
ans11 = solve(AB, CD)
AB.sort(key=lambda x:x[1], reverse=True)
CD.sort()
ans12 = solve(AB, CD)
AB.sort(reverse=True)
CD.sort(key = lambda x:x[1])
ans13 = solve(AB, CD)
AB.sort()
CD.sort(key=lambda x:x[1], reverse=True)
ans14 = solve(AB, CD)
print(max(ans1, ans2, ans3, ans4, ans5, ans6, ans7, ans8, ans9, ans10, ans11, ans12, ans13, ans14))

Submission status: Wrong Answer

Solution code:
N = int(input())
ab = []
a_ap = ab.append
cd = []
c_ap = cd.append

for i in range(N):
    foo = input().split()
    a_ap((int(foo[0]), int(foo[1])))
for i in range(N):
    foo = input().split()
    c_ap((int(foo[0]), int(foo[1])))

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


p1 = []
p2 = []
ap1 = p1.append
ap2 = p2.append
counter = 0
for aa in ab:
    for cc in cd:
        if aa in p1:
            continue
        if cc in p2:
            continue
        if aa[0] < cc[0] and aa[1] < cc[1]:
            counter += 1
            ap1(aa)
            ap2(cc)
            continue

print(counter)

Submission status: Wrong Answer

Solution code:
import copy
n = int(input())
x = [[int(i) for i in input().split()] for  i in range(n)]
y = [[int(i) for i in input().split()] for  i in range(n)]
x.sort()
y.sort()
x2 = copy.deepcopy(x)
y2 = copy.deepcopy(y)
answer1,answer2,answer3,answer4 = 0,0,0,0
for i in x:
	for j in range(len(y)):
		if i[0]<y[j][0] and i[1]<y[j][1]:
			answer1 += 1
			y = y[j+1:]
			break
for i in y2:
	for j in range(len(x)):
		if i[0]>x[j][0] and i[1]>x[j][1]:
			answer2 += 1
			x = x[j+1:]
			break
for i in range(n):
	x2[i][0],x2[i][1],y2[i][0],y2[i][1] = x2[i][1],x2[i][0],y2[i][1],y2[i][0]
x2.sort()
y2.sort()
y3 = copy.deepcopy(y2)
for i in x2:
	for j in range(len(y2)):
		if i[0]<y2[j][0] and i[1]<y2[j][1]:
			answer3 += 1
			y2 = y2[j+1:]
			break
for i in y3:
	for j in range(len(x2)):
		if i[0]>x2[j][0] and i[1]>x2[j][1]:
			answer4 += 1
			x2 = x2[j+1:]
			break
print(max(answer1,answer2,answer3,answer4))

Submission status: Wrong Answer

Solution code:
if __name__ == "__main__":
    N = int(input())
    A = []
    B = []
    C = []
    D = []
    for i in range(N):
        buf1, buf2 = list(map(int, (input().split(' '))))
        A.append(buf1)
        B.append(buf2)
    for i in range(N):
        buf1, buf2 = list(map(int, (input().split(' '))))
        C.append(buf1)
        D.append(buf2)

    def calc_dist(a, b, c, d):
        return pow((pow((c - a), 2) + pow((d - b), 2)), 0.5)

    A_dist_buf = {}
    B_dist_buf = {}
    for i in range(N):
        a_key = str(A[i]) + '_' + str(B[i])
        b_key = str(C[i]) + '_' + str(D[i])
        A_dist_buf[a_key] = calc_dist(0, 0, A[i], B[i])
        B_dist_buf[b_key] = calc_dist(0, 0, C[i], D[i])
    A_dist = sorted(A_dist_buf.items(), key=lambda x: x[1], reverse=True)
    B_dist = sorted(B_dist_buf.items(), key=lambda x: x[1], reverse=True)
#    print(A_dist)
#    print(B_dist)
    A = []
    B = []
    C = []
    D = []
    for key,ele in A_dist:
        A.append(key.split('_')[0])
        B.append(key.split('_')[1])
    for key,ele in B_dist:
        C.append(key.split('_')[0])
        D.append(key.split('_')[1])
    ans1 = 0
    for i in range(N):
        for j in range(N):
            if len(A) <= i or len(C) <= j:
                break
            if (A[i] <= C[j]) and (B[i] <= D[j]):
#                print(A[i], B[i], C[j], D[j])
                ans1 += 1
                del C[j], D[j]
                break

    A_dist = sorted(A_dist_buf.items(), key=lambda x: x[1])
    B_dist = sorted(B_dist_buf.items(), key=lambda x: x[1])
#    print(A_dist)
#    print(B_dist)
    A = []
    B = []
    C = []
    D = []
    for key,ele in A_dist:
        A.append(key.split('_')[0])
        B.append(key.split('_')[1])
    for key,ele in B_dist:
        C.append(key.split('_')[0])
        D.append(key.split('_')[1])
    ans2 = 0
    for i in range(N):
        for j in range(N):
            if len(A) <= i or len(C) <= j:
                break
            if (A[i] <= C[j]) and (B[i] <= D[j]):
#                print(A[i], B[i], C[j], D[j])
                ans2 += 1
                del C[j], D[j]
                break
    if ans1 > ans2:
        print(ans1)
    else:
        print(ans2)

Submission status: Wrong Answer

Solution code:
n = int(input())
ired = []
iblue = []

for i in range(n):
    a,b = map(int,input().split())
    ired.append([a,b])
    
for i in range(n):
    c,d = map(int,input().split())
    iblue.append([c,d])

red = sorted(ired)
blue = sorted(iblue)

flag = False
if [0,0] in red:
    red.remove([0,0])
    flag = True
    
x_ans = 0

for i in range(len(red)):
    for j in range(n):
        if (blue[j][0] > red[i][0]) and (blue[j][1] > red[i][1]):
            blue[j] = [-1,-1]
            x_ans += 1
            break
        
red = sorted(ired,key = lambda x:x[1])
blue = sorted(iblue,key = lambda x:x[1])


if [0,0] in red:
    red.remove([0,0])
    flag = True
    
y_ans = 0        
for i in range(len(red)):
    for j in range(n):
        if (blue[j][0] > red[i][0]) and (blue[j][1] > red[i][1]):
            blue[j] = [-1,-1]
            y_ans += 1
            break        

 
if flag and len(iblue) > x_ans:
    x_ans += 1
    
if flag and len(iblue) > y_ans:
    y_ans += 1
   

print(max(x_ans,y_ans))

Submission status: Wrong Answer

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


def solve(AB, CD):
    AB_set = []
    CD_set = []
    for index_ab, ab in enumerate(AB):
        i, j = -1, -1
        if index_ab in AB_set:
            continue
        distance = float('inf')
        for index_cd, cd in enumerate(CD):
            if index_cd in CD_set:
                continue
            if (cd[0] - ab[0] >= 0) & (cd[1] - ab[1] >= 0) & ((cd[0]-ab[0]) + (cd[1] - ab[1]) < distance):
                distance = (cd[0] - ab[0]) + (cd[1] - ab[1])
                i, j = index_ab, index_cd
        if (i != -1) & (j != -1):
            AB_set.append(i)
            CD_set.append(j)
    return len(AB_set)

AB.sort()
CD.sort()
ans1 = solve(AB, CD)
AB.sort(reverse=True)
CD.sort(reverse=True)
ans2 = solve(AB, CD)
AB.sort(key=lambda x:x[1])
CD.sort(key=lambda x:x[1])
ans3 = solve(AB, CD)
AB.sort(key=lambda x:x[1], reverse=True)
CD.sort(key=lambda x:x[1], reverse=True)
ans4 = solve(AB, CD)
AB.sort()
CD.sort(key=lambda x:x[1])
ans5 = solve(AB, CD)
AB.sort(reverse=True)
CD.sort(key=lambda x:x[1], reverse=True)
ans6 = solve(AB, CD)
AB.sort(key=lambda x:x[1])
CD.sort()
ans7 = solve(AB, CD)
AB.sort(key=lambda x:x[1], reverse=True)
CD.sort(reverse=True)
ans8 = solve(AB, CD)
AB.sort(reverse=True)
CD.sort()
ans9 = solve(AB, CD)
AB.sort()
CD.sort(reverse=True)
ans10 = solve(AB, CD)
AB.sort(key=lambda x:x[1])
CD.sort(reverse=True)
ans11 = solve(AB, CD)
AB.sort(key=lambda x:x[1], reverse=True)
CD.sort()
ans12 = solve(AB, CD)
AB.sort(reverse=True)
CD.sort(key = lambda x:x[1])
ans13 = solve(AB, CD)
AB.sort()
CD.sort(key=lambda x:x[1], reverse=True)
ans14 = solve(AB, CD)
print(max(ans1, ans2, ans3, ans4, ans5, ans6, ans7, ans8, ans9, ans10, ans11, ans12, ans13, ans14))

Submission status: Wrong Answer

Solution code:
n = int(raw_input())
red = []
blue = []
for i in range(n):
	x,y = map(int,raw_input().split())
	red.append((x,y));
for i in range(n):
	x,y = map(int,raw_input().split())
	blue.append((x,y));

d = {}
for i in red:
	d[i] = 0;
ans = 0;

for pr in blue:
	flag = 0;
	for x in range(pr[0],-1,-1):

		for y in range(pr[1],-1,-1):
			if d.get((x,y)) != None and d[(x,y)] != 1:
				ans+=1;
				d[(x,y)] = 1;
				flag = 1;
				break;
		if flag == 1:
			break;

print ans;

Submission status: Wrong Answer

Solution code:
n = int(input())
red_list = []
x_min = 200
for i in range(n):
    x, y = map(int, input().split())
    x_min = min(x_min, x)
    red_list.append((x, y))
red_list = sorted(red_list, reverse=True, key=lambda x: max(x[0], x[1]))
blue_list = []
for i in range(n):
    x, y = map(int, input().split())
    if x_min < x:
        blue_list.append((x, y))
blue_list = sorted(blue_list, key=lambda x: x[1])

max_pair = min(len(red_list), len(blue_list))
pair = 0
for blue in blue_list:
    flag = 0
    for red in red_list:
        if blue[0] > red[0] and blue[1] > red[1]:
            pair += 1
            red_list.remove(red)
    if pair >= max_pair:
        break

print(pair)

Submission status: Wrong Answer

Solution code:
n = int(input())
red = []
blue = []

for i in range(n):
    x, y = map(int, input().split())
    red.append((x, y))
for i in range(n):
    x, y = map(int, input().split())
    blue.append((x, y))

sr = list(reversed(sorted(red)))
sb = list(reversed(sorted(blue)))
sry = list(reversed(sorted(red, key=lambda tup: tup[1])))
sby = list(reversed(sorted(blue, key=lambda tup: tup[1])))
ans = 0
ans2 = 0
for i in range(n):
    for j in range(n):
        if(sr[i][0] < sb[j][0] and sr[i][1] < sb[j][1]):
            sr[i] = (2 * n + 1, 2 * n + 1)
            sb[j] = (-1, -1)
            ans += 1
        if(sry[i][0] < sby[j][0] and sry[i][1] < sby[j][1]):
            sry[i] = (2 * n + 1, 2 * n + 1)
            sby[j] = (-1, -1)
            ans2 += 1

if(ans > ans2):
    print(ans)
else:
    print(ans2)

Submission status: Wrong Answer

Solution code:
import math
import sys
from pprint import pprint

def distance(a,b):
    return math.sqrt((a[0]-b[0])**2 + (a[1]-b[1])**2)

def solve(reds, blues):
    ans = []
    # for blue in blues:
    #     pprint(reds)
    #     pprint(blues)
    #     print("------")
    #     red_ans = reds[0]
    #     min_d = sys.maxsize
    #     for red in reds:
    #         print("now checking {} and {}".format(red, blue))
    #         if blue[0] > red[0] and blue[1] > red[1] and (red, blue) not in ans:
    #             min_d = 1
    #             break
    #             # d = distance(red, blue)
    #             # if min_d > d:
    #             #     red_ans = red
    #             #     min_d = d
    #     if min_d != sys.maxsize:
    #         ans.append((red_ans, blue))
    #         blues.remove(blue)
    #         reds.remove(red_ans)
    while len(blues) != 0:
        blue = blues.pop()
        # print("-----")
        # pprint(reds)
        # pprint(blues)
        red_ans = reds[0]
        min_d = sys.maxsize
        for red in reds:
            if blue[0] > red[0] and blue[1] > red[1] and (red, blue) not in ans:
                d = distance(red, blue)
                if min_d > d:
                    red_ans = red
                    min_d = d
        if min_d != sys.maxsize:
            # print("{} <-> {}".format(red_ans, blue))
            ans.append((red_ans, blue))
            reds.remove(red_ans)
    # pprint(reds)
    # pprint(blues)
    # while len(reds) != 0:
    #     red = reds.pop()
    #     # print("-----")
    #     # pprint(reds)
    #     # pprint(blues)
    #     blue_ans = blues[0]
    #     min_d = sys.maxsize
    #     for blue in blues:
    #         if blue[0] > red[0] and blue[1] > red[1] and (red, blue) not in ans:
    #             d = distance(red, blue)
    #             if min_d > d:
    #                 blue_ans = blue
    #                 min_d = d
    #     if min_d != sys.maxsize:
    #         # print("{} <-> {}".format(red, blue_ans))
    #         ans.append((red, blue_ans))
    #         blues.remove(blue_ans)
    # pprint(ans)
    return len(ans)

if __name__ == '__main__':
    N = int(input())
    reds = []
    for i in range(N):
        a,b = list(map(lambda x: int(x), input().split(" ")))
        reds.append((a,b))
    blues = []
    for i in range(N):
        c,d = list(map(lambda x: int(x), input().split(" ")))
        blues.append((c,d))
    ans = []
    reds.sort()
    blues.sort()
    blues.reverse()
    ans = solve(reds, blues)
    print(ans)
    # while len(blues) == 0:
    #     blue = blues.pop()

Submission status: Wrong Answer

Solution code:
# http://nobuta05.hatenablog.com/entry/2015/11/12/013938

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)
            if (ui1,v) in M:
                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())
AB = [[int(_) for _ in input().split()] for i in range(N)]
CD = [[int(_) for _ in input().split()] for i in range(N)]

"""
from random import randint
N = 100
AB = [(randint(0, N*2), randint(0, N*2)) for i in range(N)]
CD = [(randint(0, N*2), randint(0, N*2)) for i in range(N)]
print(AB)
print(CD)
"""

E = []

for i in range(N):
    for j in range(N):
        if AB[i][0] < CD[j][0] and AB[i][1] < CD[j][1]:
            E.append((i, j))

M = Hungary(list(range(N)), list(range(N)), E)
print(len(M))

Submission status: Wrong Answer

Solution code:
n=int(input())
x=[tuple(map(int,input().split()))for i in range(n)]#red point
y=[tuple(map(int,input().split()))for i in range(n)]#blue point
red=[]
blue=[]
for i in range(n):
    for j in range(n):
        if x[i][0]<y[j][0] and x[i][1]<y[j][1]:
            red.append(x[i])
            blue.append(y[j])
set_red=set(red)
set_blue=set(blue)
print(min(len(set_red),len(set_blue)))

Submission status: Wrong Answer

Solution code:
n = int(input())
red_list = []
x_min = 200
y_max = 0
for i in range(n):
    x, y = map(int, input().split())
    x_min = min(x_min, x)
    y_max = max(y_max, y)
    red_list.append((x, y))
red_list = sorted(red_list, reverse=True, key=lambda x: max(x[0], x[1]))
blue_list = []
for i in range(n):
    x, y = map(int, input().split())
    if x_min < x:
        blue_list.append((x, y))
blue_list = sorted(blue_list, key=lambda x: x[1])

max_pair = min(len(red_list), len(blue_list))
pair = 0
for blue in blue_list:
    flag = 0
    p_x, p_y = 200, 200
    for red in red_list:
        if blue[0] > red[0] and blue[1] > red[1]:
            if p_x + p_y > (blue[0]-red[0]) + (blue[1]-red[1]):
                p_x = red[0]
                p_y = red[1]
                flag = 1
    if flag == 1:
        pair += 1
        red_list.remove((p_x, p_y))
    if pair >= max_pair:
        break

print(pair)

Submission status: Wrong Answer

Solution code:
n = int(input())
red = []
blue = []

for i in range(n):
    x, y = map(int, input().split())
    red.append((x, y))
for i in range(n):
    x, y = map(int, input().split())
    blue.append((x, y))

sr = list(reversed(sorted(red)))
sb = list(reversed(sorted(blue)))
ans = 0
for i in range(n):
    for j in range(n):
        if(sr[i][0] < sb[j][0] and sr[i][1] < sb[j][1]):
            sr[i] = (2 * n + 1, 2 * n + 1)
            sb[j] = (-1, -1)
            ans += 1


print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
red = [0]*n
blue = [0]*n
for i in range(n):
    red[i] = list(map(int,input().split()))
for i in range(n):
    blue[i] = list(map(int,input().split()))
red.sort()
blue.sort()
p = [[] for j in range(n)]
q = []
for i in range(n):
    for j in range(n):
        if(red[i][0]<blue[j][0] and red[i][1]<blue[j][1]):
            p[i].append(j)
            q.append(j)
q = list(set(q))
o = 0
qq = []
for i in q:
    c = 0
    for j in p:
        c+=j.count(i)
    qq.append([c,i])
qq.sort(key=lambda x:x[0])
for i in qq:
    for j in range(n):
        if i[1] in p[j]:
            p[j] = [-1]
            o += 1
            break
print(o)

Submission status: Wrong Answer

Solution code:
if __name__ == "__main__":
    N = int(input())
    A = []
    B = []
    C = []
    D = []
    for i in range(N):
        buf1, buf2 = list(map(int, (input().split(' '))))
        A.append(buf1)
        B.append(buf2)
    for i in range(N):
        buf1, buf2 = list(map(int, (input().split(' '))))
        C.append(buf1)
        D.append(buf2)

    def calc_dist(a, b, c, d):
        return pow((pow((c - a), 2) + pow((d - b), 2)), 0.5)

    A_dist = {}
    B_dist = {}
    for i in range(N):
        a_key = str(A[i]) + '_' + str(B[i])
        b_key = str(C[i]) + '_' + str(D[i])
        A_dist[a_key] = calc_dist(0, 0, A[i], B[i])
        B_dist[b_key] = calc_dist(0, 0, C[i], D[i])
    A_dist = sorted(A_dist.items(), key=lambda x: x[1], reverse=True)
    B_dist = sorted(B_dist.items(), key=lambda x: x[1], reverse=True)
#    print(A_dist)
#    print(B_dist)
    A = []
    B = []
    C = []
    D = []
    for key,ele in A_dist:
        A.append(key.split('_')[0])
        B.append(key.split('_')[1])
    for key,ele in B_dist:
        C.append(key.split('_')[0])
        D.append(key.split('_')[1])
    ans = 0
    for i in range(N):
        for j in range(N):
            if len(A) <= i or len(C) <= j:
                break
            if (A[i] <= C[j]) and (B[i] <= D[j]):
#                print(A[i], B[i], C[j], D[j])
                ans += 1
                del C[j], D[j]
                break
    print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
listRed = [[i for i in map(int,input().split())]for j in range(N)]
listBlue = [[i for i in map(int,input().split())]for j in range(N)]
ans = 0
sortRed = sorted(listRed,key = lambda x: x[0] + x[1],reverse=True)
sortBlue = sorted(listBlue,key = lambda x: x[0] + x[1])

for i in range(N):
    for j in range(len(sortBlue)):
        if sortRed[i][0] < sortBlue[j][0] and sortRed[i][1] < sortBlue[j][1]:
            ans += 1
            sortBlue.pop(j)
            break

print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    red = []
    for i in range(N):
        x,y = [int(i) for i in input().split()]
        red.append([x,y])
    blue = []
    for i in range(N):
        x,y = [int(i) for i in input().split()]
        blue.append([x,y])
    red.sort(reverse=True)
    blue.sort(reverse=True)
    #print(red)
    #print(blue)
    pair = 0
    for a in range(N):
        flag = False
        for i in range(N):
            for j in range(N):
                if(red[i][0] <= blue[j][0] and red[i][1] <= blue[j][1]):
                    pair = pair + 1
                    flag = True
                    #print(f'{red[i]} {blue[j]}')
                    blue[j][0] = -float('inf')
                    blue[j][1] = -float('inf')
                    break
                
        if flag:
            break
    print(pair)
if __name__ == '__main__':
    main()