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:
def main():
    n = int(input())
    aa = []
    for i in range(n):
        x, y = map(int, input().split())
        aa.append([x, y])
    bb = []
    for i in range(n):
        x, y = map(int, input().split())
        bb.append([x, y])
    cc = {i: set() for i in range(n)}
    dd = {i: set() for i in range(n)}
    for i, a in enumerate(aa):
        for j, b in enumerate(bb):
            if a < b:
                cc[i].add(j)
                dd[j].add(i)
    count = 0
    while cc:
        for i in range(n):
            if i in cc and not cc[i]:
                del cc[i]
            if i in dd and not dd[i]:
                del dd[i]
        best_key = None
        min_null = n
        for i, c in cc.items():
            for j in c:
                null = 0
                for ii in dd[j]:
                    if i != ii and len(cc[ii]) == 1:
                            null += 1
                if min_null > null:
                    min_null = null
                    best_key = (i, j)
                if min_null == 0:
                    break
        if best_key is None:
            break
        count += 1
        ii, jj = best_key
        cc[ii] = []
        dd[jj] = []
        for c in cc.values():
            if jj in c:
                c.remove(jj)
        for d in dd.values():
            if ii in d:
                d.remove(ii)
    print(count)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
R = [list(map(int, input().split(' '))) + [0] for i in range(N)]
B = [list(map(int, input().split(' '))) + [list()] for i in range(N)]
R = sorted(R)
B = sorted(B)
for b in B:
    for r in R:
        if b[0] > r[0] and b[1] > r[1]:
            b[2].append(r)
B = sorted(B, key=lambda x:len(x[2]))
ans = 0
for b in B:
    rs = [r for r in b[2] if r[2] == 0]
    if len(rs) > 0:
        for r in rs:
            if b[0] > r[0] and b[1] > r[1]:
                r[2] += 1
                ans += 1
                break
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=[]
B=[]
for i in range(N):
  x,y=map(int,input().split())
  A.append([x,y])
for i in range(N):
  x,y=map(int,input().split())
  B.append([x,y])
res=[0 for j in range(N)]
for i in range(N):
  for j in range(N):
    if A[i][0]<B[j][0] and A[i][1]<B[j][1]:
      res[i]+=1
ans=0
for i in range(N):
  if res[i]>0:
    ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import math
import itertools
from heapq import heapify, heappop, heappush
from sys import stdin, stdout, setrecursionlimit
from bisect import bisect, bisect_left, bisect_right
from collections import defaultdict, deque


# d = defaultdict(lambda: 0)
# setrecursionlimit(10**7)
# inf = float("inf")


##### stdin ####
def LM(t, r): return list(map(t, r))
def R(): return stdin.readline()
def RS(): return R().split()
def I(): return int(R())
def F(): return float(R())
def LI(): return LM(int,RS())
def LF(): return LM(float,RS())
def ONE_SL(): return list(input())
def ONE_IL(): return LM(int, ONE_SL())
def ALL_IL(): return LM(int,stdin)

##### tools #####
def ap(f): return f.append
def pll(li): print('\n'.join(LM(str,li)))
def pljoin(li, s): print(s.join(li))



##### main #####
def main():
	ans = 0
	N =I()
	red = {}

	for i in range(N):
		a,b = LI()
		red[a] = b
	A = list(red.keys())

	comb = defaultdict(lambda: [])
	for i in range(N):
		c,d = LI()
		cand = [x for x in A if x<=c]
		if cand:
			for x in cand:
				y = red[x]
				if y <= d:
					comb[i].append(x)
					
	used = []
	for v in sorted(comb.values(), key=lambda x:len(x)):
		for i in range(len(v))[::-1]:
			if v[i] not in used:
				ans += 1
				used.append(v[i])
				break
	print(ans)




if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
from operator import itemgetter

if __name__ == '__main__':
    N = int(input())
    red = [list(map(int, input().split())) for _ in range(N)]
    blue = [list(map(int, input().split())) for _ in range(N)]

    for i in range(N):
        ap = 0
        for j in range(N):
            b_x, b_y = blue[i]
            r_x, r_y = red[j]

            if b_x > r_x and b_y > r_y:
                ap += 1

        blue[i].append(ap)

    blue = sorted(blue, key=itemgetter(2))

    red = sorted(red, reverse=True, key=itemgetter(0))

    ans = 0

    for b2_x, b2_y, t in blue:
        del_flg = False
        for r_x, r_y in red:
            if r_x > b2_x:
                continue
            if r_y > b2_y:
                continue

            del_flg = True
            del_x = r_x
            del_y = r_y
            ans += 1
            break
        if del_flg:
            red.remove([del_x, del_y])

    print(ans)

Submission status: Wrong Answer

Solution code:
import math
import itertools
from heapq import heapify, heappop, heappush
from sys import stdin, stdout, setrecursionlimit
from bisect import bisect, bisect_left, bisect_right
from collections import defaultdict, deque


# d = defaultdict(lambda: 0)
# setrecursionlimit(10**7)
# inf = float("inf")


##### stdin ####
def LM(t, r): return list(map(t, r))
def R(): return stdin.readline()
def RS(): return R().split()
def I(): return int(R())
def F(): return float(R())
def LI(): return LM(int,RS())
def LF(): return LM(float,RS())
def ONE_SL(): return list(input())
def ONE_IL(): return LM(int, ONE_SL())
def ALL_IL(): return LM(int,stdin)

##### tools #####
def ap(f): return f.append
def pll(li): print('\n'.join(LM(str,li)))
def pljoin(li, s): print(s.join(li))



##### main #####
def main():
	ans = 0
	N =I()
	red = {}

	for i in range(N):
		a,b = LI()
		red[a] = b
	A = list(red.keys())

	comb = defaultdict(lambda: [])
	for i in range(N):
		c,d = LI()
		cand = [x for x in A if x<c]
		if cand:
			for x in cand:
				y = red[x]
				if y < d:
					comb[i].append(x)
					
	used = []
	for v in sorted(comb.values(), key=lambda x:len(x)):
		for i in range(len(v))[::-1]:
			if v[i] not in used:
				ans += 1
				used.append(v[i])
				break
	print(ans)




if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
import math
import itertools
from heapq import heapify, heappop, heappush
from sys import stdin, stdout, setrecursionlimit
from bisect import bisect, bisect_left, bisect_right
from collections import defaultdict, deque


# d = defaultdict(lambda: 0)
# setrecursionlimit(10**7)
# inf = float("inf")


##### stdin ####
def LM(t, r): return list(map(t, r))
def R(): return stdin.readline()
def RS(): return R().split()
def I(): return int(R())
def F(): return float(R())
def LI(): return LM(int,RS())
def LF(): return LM(float,RS())
def ONE_SL(): return list(input())
def ONE_IL(): return LM(int, ONE_SL())
def ALL_IL(): return LM(int,stdin)

##### tools #####
def ap(f): return f.append
def pll(li): print('\n'.join(LM(str,li)))
def pljoin(li, s): print(s.join(li))



##### main #####
def main():
	ans = 0
	N =I()
	red = {}

	for i in range(N):
		a,b = LI()
		red[a] = b
	A = list(red.keys())

	comb = defaultdict(lambda: [])
	for i in range(N):
		c,d = LI()
		cand = [x for x in A if x<c]
		if cand:
			for x in cand:
				y = red[x]
				if y < d:
					comb[i].append(x)
					
	used = []
	for v in sorted(comb.values(), key=lambda x:len(x)):
		for i in range(len(v)):
			if v[i] not in used:
				ans += 1
				used.append(v[i])
				break
	print(ans)

if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
N = int(input())

Red = []
Blue = []

for i in range(N):
    r_geo = list(map(int, input().split(' ')))
    Red.append(r_geo)

for i in range(N):
    b_geo = list(map(int, input().split(' ')))
    Blue.append(b_geo)

Red.sort(key=lambda x:(x[0],x[1]))
Blue.sort(key=lambda x:(x[0],x[1]))

count = 0

for i in range(N):
    red = Red[i]

    for j in range(len(Blue)):
        blue = Blue[j]

        if red < blue:
            Blue.remove(blue)
            count += 1
            break

print(count)

Submission status: Wrong Answer

Solution code:
#/usr/bin/env python
import numpy as np
N = int(input())
red = sorted([tuple(map(int, input().split())) for _ in range(N)], reverse=True)
blue = sorted([tuple(map(int, input().split())) for _ in range(N)], reverse=True) 
ref = np.zeros((N, N))
for r in range(N):
    for b in range(N):
        if red[r][0] < blue[b][0] and red[r][1] < blue[b][1]:
            ref[r, b] = 1
unsearched_red = list(range(N))
unsearched_blue = list(range(N))
cnt = 0
for b in range(N):
    for r in range(N):
        if ref[r, b] and (r in unsearched_red) and (b in unsearched_blue):
            cnt += 1
            unsearched_red.remove(r)
            unsearched_blue.remove(b) 
print(cnt)

Submission status: Wrong Answer

Solution code:
# coding=utf-8
from pprint import pprint
n = int(input())
red = []
blue = []

for _ in range(n):
    line = input().split(" ")
    red.append((int(line[0]), int(line[1]), 0))
red.sort()

for _ in range(n):
    line = input().split(" ")
    blue.append((int(line[0]), int(line[1]), False))
blue.sort()

for (ri,r) in enumerate(red):
    cnt = 0
    for (bi,b) in enumerate(blue):
        if r[0]<b[0] and r[1]<b[1]:
            cnt += 1
    red[ri] = (r[0],r[1],cnt)

# pprint(red)
red.sort(key=lambda c:c[2])
# pprint(red)


cnt = 0
for r in red:
    for (bi,b) in enumerate(blue):
        if not b[2] and r[0]<b[0] and r[1]<b[1]:
            cnt += 1
            blue[bi] = (b[0], b[1], True)
            break
print(cnt)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter


def ret(red, blue):
    ans = 0
    for b_x, b_y in blue:
        del_flg = False
        for r_x, r_y in red:
            if r_x > b_x:
                continue
            if r_y > b_y:
                continue

            del_flg = True
            del_x = r_x
            del_y = r_y
            ans += 1
            break
        if del_flg:
            red.remove([del_x, del_y])

    return ans


if __name__ == '__main__':
    N = int(input())
    red = [list(map(int, input().split())) for _ in range(N)]
    blue = [list(map(int, input().split())) for _ in range(N)]

    red1 = sorted(red, reverse=True, key=itemgetter(0))
    blue1 = sorted(blue, key=itemgetter(0))

    ans_1 = ret(red1, blue1)

    red2 = sorted(red, reverse=True, key=itemgetter(1))
    blue2 = sorted(blue, key=itemgetter(1))

    ans_2 = ret(red2, blue2)

    print(max(ans_1, ans_2))

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    aa = []
    for i in range(n):
        x, y = map(int, input().split())
        aa.append([x, y])
    bb = []
    for i in range(n):
        x, y = map(int, input().split())
        bb.append([x, y])
    aa.sort(key=lambda l: max(l), reverse=True)
    c = 0
    for a in aa:
        lis = [i for i in range(n) if a < bb[i]]
        if lis:
            i = min(lis, key=lambda i: bb[i][0] + bb[i][1] - aa[i][0] - aa[i][1])
            c += 1
            bb[i] = [0, 0]
    print(c)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    aa = []
    for i in range(n):
        x, y = map(int, input().split())
        aa.append([x, y])
    bb = []
    for i in range(n):
        x, y = map(int, input().split())
        bb.append([x, y])
    aa.sort(key=lambda l: max(l), reverse=True)
    c = 0
    for a in aa:
        lis = [i for i in range(n) if aa[i] < bb[i]]
        if lis:
            i = min(lis, key=lambda i: bb[i][0] + bb[i][1] - aa[i][0] - aa[i][1])
            c += 1
            bb[i] = [0, 0]
    print(c)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
ab = [[-1, -1] for i in range(n)]
cd = [[-1, -1] for i in range(n)]
ans = 0
for i in range(n):
    ab[i][0], ab[i][1] = map(int, input().split())

for i in range(n):
    cd[i][0], cd[i][1] = map(int, input().split())

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

ans = 0
ab = list(reversed(sorted(ab)))
cd = list(sorted(cd))
used = [False for _ in range(n)]
for (ai, bi) in ab:
    for j in range(n):
        if used[j]:
            continue
        (cj, dj) = cd[j]
        if ai < cj and bi < dj:
            ans += 1
            used[j] = True
            break
print(ans)

Submission status: Wrong Answer

Solution code:
import math
import itertools
from heapq import heapify, heappop, heappush
from sys import stdin, stdout, setrecursionlimit
from bisect import bisect, bisect_left, bisect_right
from collections import defaultdict, deque


# d = defaultdict(lambda: 0)
# setrecursionlimit(10**7)
# inf = float("inf")


##### stdin ####
def LM(t, r): return list(map(t, r))
def R(): return stdin.readline()
def RS(): return R().split()
def I(): return int(R())
def F(): return float(R())
def LI(): return LM(int,RS())
def LF(): return LM(float,RS())
def ONE_SL(): return list(input())
def ONE_IL(): return LM(int, ONE_SL())
def ALL_IL(): return LM(int,stdin)

##### tools #####
def ap(f): return f.append
def pll(li): print('\n'.join(LM(str,li)))
def pljoin(li, s): print(s.join(li))



##### main #####
def main():
	ans = 0
	N =I()
	red = {}

	for i in range(N):
		a,b = LI()
		red[a] = b
	A = list(red.keys())

	for i in range(N):
		c,d = LI()
		cand = [x for x in A if x<c]
		if cand:
			x = max(cand)
			y = red[x]
			if y < d:
				del red[x]
				A = list(red.keys())
				ans += 1


	print(ans)


if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:

def main():
    n = int(input())
    aa = []
    for i in range(n):
        x, y = map(int, input().split())
        aa.append([x, y])
    bb = []
    for i in range(n):
        x, y = map(int, input().split())
        bb.append([x, y])
    cc = {i: set() for i in range(n)}
    dd = {i: [] for i in range(n)}
    for i, a in enumerate(aa):
        for j, b in enumerate(bb):
            if a < b:
                cc[i].add(j)
                dd[j].append(i)
    for i in range(n):
        if not cc[i]:
            del cc[i]
    count = 0
    while cc:
        k = min(cc, key=lambda key: len(cc[key]))
        c = cc[k]
        if c:
            count += 1
            for j in c:
                for i in dd[j]:
                    if i in cc and j in cc[i]:
                        cc[i].remove(j)
                break
            del cc[k]
        else:
            break
    print(count)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def c(t1, t2):
    if t1[0] == t2[0]:
        return cmp(t1[1], t2[1])
    return cmp(t1[0], t2[0])


n = input()
r = sorted([map(int, raw_input().split()) + [1] for _ in xrange(n)], cmp = c, reverse = True)
b = sorted([map(int, raw_input().split()) + [1] for _ in xrange(n)], cmp = c, reverse = True)
cnt = 0
for i in xrange(n):
    for j in xrange(n):
        if b[j][0] > r[i][0] and b[j][1] > r[i][1] and b[j][2] and r[i][2]:
            cnt += 1
            b[j][2], r[i][2] = 0, 0
            break
print cnt

Submission status: Wrong Answer

Solution code:
N=int(input())
a=[0 for i in range(N)]
b=[0 for i in range(N)]
c=[0 for i in range(N)]
d=[0 for i in range(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())
m=[[0 for i in range(N)] for i in range(N)]
s=[set() for i in range(N)]
for i in range(N):
    for j in range(N):
        if a[i]<c[j] and b[i]<d[j]:
            m[i][j]+=1
            s[i].add(j)
t=[set() for i in range(N)]
#import numpy as np
#u=list(np.argsort(np.array([len(s[i]) for i in range(N)])))
ans=0
used=[False for i in range(N)]
k=[set() for i in range(N+1)]
for i in range(N):
    k[len(s[i])].add(i)
for n in range(N+1):
    for i in k[n]:
        for j in s[i]:
            if not(used[j]):
                used[j]=True
                t[i].add(j)
                break
        if len(t[i])!=0:
            ans+=1
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)]

ans = 0
ab = list(reversed(sorted(ab)))
used = [False for _ in range(n)]
for (ai, bi) in ab:
    for j in range(n):
        if used[j]:
            continue
        (cj, dj) = cd[j]
        if ai < cj and bi < dj:
            ans += 1
            used[j] = True
            break
print(ans)

Submission status: Wrong Answer

Solution code:
def dist(a, b):
    if a[0] >= b[0] or a[1] >= b[1]:
        return False

    return (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2


n = int(input())
r = []
b = []
for _ in range(n):
    r.append(list(map(int, input().split())))
for _ in range(n):
    b.append(list(map(int, input().split())))

pairs = []

for i in range(n):
    for j in range(n):
        ds = dist(r[i], b[j])
        if not ds:
            continue
        pairs.append((ds, '-'.join(map(str, r[i])), '-'.join(map(str, b[j]))))

pairs.sort(key=lambda x: x[0])

rv = set()
bv = set()

c = 0
for p in pairs:
    if p[1] not in rv and p[2] not in bv:
        rv.add(p[1])
        bv.add(p[2])
        c += 1

print(c)

Submission status: Wrong Answer

Solution code:
# coding=utf-8
from pprint import pprint
n = int(input())
red = []
blue = []

for _ in range(n):
    line = input().split(" ")
    red.append((int(line[0]), int(line[1]), False))
red.sort(reverse=True)

for _ in range(n):
    line = input().split(" ")
    blue.append((int(line[0]), int(line[1]), False))
blue.sort(reverse=True)

cnt = 0
p = []
for (ri,r) in enumerate(red):
    flag = False
    for (bi,b) in enumerate(blue):
        if not r[2] and not b[2] and r[0]<b[0] and r[1]<b[1]:
            p.append([r,b])
            cnt += 1
            red[ri] = (r[0], r[1], True)
            blue[bi] = (b[0],b[1],True)
            break

print(cnt)

Submission status: Wrong Answer

Solution code:
n = input()
r = sorted([map(int, raw_input().split()) + [1] for _ in xrange(n)], key = lambda x: x[1])
b = sorted([map(int, raw_input().split()) + [1] for _ in xrange(n)], key = lambda x: x[1])
cnt = 0
for i in xrange(n):
    for j in xrange(n):
        if b[j][0] > r[i][0] and b[j][1] > r[i][1] and b[j][2] and r[i][2]:
            cnt += 1
            b[j][2], r[i][2] = 0, 0
            break
print cnt

Submission status: Wrong Answer

Solution code:
from bisect import bisect

n = int(input())
ab = sorted((list(map(int, input().split())) for _ in range(n)))
cd = sorted((list(map(int, input().split())) for _ in range(n)))
ans = 0
for r in ab:
    i = bisect(cd, r)
    if i == n:
        continue
    dc = sorted([d, c] for c, d in cd[i:])
    j = bisect(dc, [r[1], r[0]])
    if j == len(dc):
        continue
    ans += 1
    d, c = dc[j]
    cd.remove([c, d])

print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
a=[0 for i in range(N)]
b=[0 for i in range(N)]
c=[0 for i in range(N)]
d=[0 for i in range(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())
m=[[0 for i in range(N)] for i in range(N)]
s=[set() for i in range(N)]
for i in range(N):
    for j in range(N):
        if a[i]<c[j] and b[i]<d[j]:
            m[i][j]+=1
            s[i].add(j)
t=[set() for i in range(N)]
import numpy as np
u=list(np.argsort(np.array([len(s[i]) for i in range(N)])))
ans=0
used=[False for i in range(N)]
'''
for i in range(N):
    print(u[i],s[u[i]])
print("##############")
'''
for i in range(N):
    #print(u[i],s[u[i]])
    for j in s[u[i]]:
        if not(used[j]):
            t[i].add(j)
            used[j]=True
            break
    if len(t[i])!=0:
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
# import sys
# from io import StringIO

import math

# sys.stdin = StringIO(open(__file__.replace('.py', '.in')).read())


def dist(a, b):
    if a[0] >= b[0] or a[1] >= b[1]:
        return False

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


n = int(input())
r = []
b = []
for _ in range(n):
    r.append(list(map(int, input().split())))
for _ in range(n):
    b.append(list(map(int, input().split())))

pairs = []

for i in range(n):
    for j in range(n):
        ds = dist(r[i], b[j])
        if not ds:
            continue
        pairs.append((ds, '-'.join(map(str, r[i])), '-'.join(map(str, b[j]))))

pairs.sort(key=lambda x: x[0])

rv = set()
bv = set()

res = []

for p in pairs:
    if p[1] not in rv and p[2] not in bv:
        res.append(p)
        rv.add(p[1])
        bv.add(p[2])

# print(res)
print(len(res))

Submission status: Wrong Answer

Solution code:
N=int(input())
a=[0 for i in range(N)]
b=[0 for i in range(N)]
c=[0 for i in range(N)]
d=[0 for i in range(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())
m=[[0 for i in range(N)] for i in range(N)]
s=[set() for i in range(N)]
for i in range(N):
    for j in range(N):
        if a[i]<c[j] and b[i]<d[j]:
            m[i][j]+=1
            s[i].add(j)
t=[set() for i in range(N)]
import numpy as np
u=list(np.argsort(np.array([len(s[i]) for i in range(N)])))
ans=0
used=[False for i in range(N)]
'''
for i in range(N):
    print(u[i],s[u[i]])
print("##############")
'''
for i in range(N):
    #print(u[i],s[u[i]])
    for j in s[u[i]]:
        if not(used[j]):
            t[i].add(j)
            used[j]=True
            ans+=1
            break
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())

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

sorted_a = sorted(sorted(a_lis, key=lambda x: x[0]), key=lambda y: y[1])
sorted_b = sorted(sorted(b_lis, key=lambda x: x[0]), key=lambda y: y[1])

arrive = []

for i in sorted_b:
    for index, j in enumerate(sorted_a):
        if j[0] < i[0] and j[1] < i[1] and index not in arrive:
            arrive.append(index)
            break

print(len(arrive))

Submission status: Wrong Answer

Solution code:

def main():
    n = int(input())
    aa = []
    for i in range(n):
        x, y = map(int, input().split())
        aa.append([x, y])
    bb = []
    for i in range(n):
        x, y = map(int, input().split())
        bb.append([x, y])
    aa.sort(key=lambda l: max(l), reverse=True)
    bb.sort(key=lambda l: max(l), reverse=False)
    c = 0
    for a in aa:
        for i, b in enumerate(bb):
            if a < b:
                c += 1
                bb[i] = [0, 0]
                break
    print(c)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:

def main():
    n = int(input())
    aa = []
    for i in range(n):
        x, y = map(int, input().split())
        aa.append([x, y])
    bb = []
    for i in range(n):
        x, y = map(int, input().split())
        bb.append([x, y])
    aa.sort(key=lambda l: max(l), reverse=True)
    c = 0
    for a in aa:
        for i, b in enumerate(bb):
            if a < b:
                c += 1
                bb[i] = [0, 0]
                break
    print(c)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
ab = sorted((list(map(int, input().split())) for _ in range(n)), reverse=True)
cd = sorted((list(map(int, input().split())) for _ in range(n)), reverse=True)

ans = 0
for a, b in ab:
    for i, (c, d) in enumerate(cd):
        if a > c:
            break
        if b < d:
            ans += 1
            del cd[i]
            break
print(ans)

Submission status: Wrong Answer

Solution code:
n = input()

r = sorted([map(int, raw_input().split()) for _ in xrange(n)])
b = sorted([map(int, raw_input().split()) for _ in xrange(n)])
r2 = sorted(r, key=lambda x:x[1])
b2 = sorted(b, key=lambda x:x[1])
a = len(([(i, j) for i, j in zip(r, b) if i[0] < j[0] and i[1] < j[1]]))
b = len(([(i, j) for i, j in zip(r2, b2) if i[0] < j[0] and i[1] < j[1]]))
print max(a,b)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations as prm
n = int(input())
red = [list(map(int,input().split())) for _ in range(n)]
blue = [list(map(int,input().split())) for _ in range(n)]
ans = 0
for l in prm(range(n)):
    c = 0
    for i in range(n):
        j = l[i]
        if red[i][0] < blue[j][0] and red[i][1] < blue[j][1]:
            c += 1
    ans = max(ans,c)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!python3

INF = 10 ** 15


# input
N = int(input())
a, b, c, d = [None] * N, [None] * N, [None] * N, [None] * N
for i in range(N):
    a[i], b[i] = list(map(int, input().split()))
for i in range(N):
    c[i], d[i] = list(map(int, input().split()))


class MaxFlow():

    def __init__(self, n):
        self.n = n
        self.c = [[0] * n for _ in range(n)]
        self.visit = [False] * n
        self.link = [set() for _ in range(n)]

    def add_link(self, x, y, capa):
        self.c[x][y] += capa
        self.link[x].add(y)
    
    def solve(self, t, v, f):
        if v == t:
            return f
        self.visit[v] = True
        
        w = 0
        
        for i in self.link[v]:
            if self.visit[i] or self.c[v][i] == 0:
                continue
            d = self.solve(t, i, min(f - w, self.c[v][i]))
            if d > 0:
                self.c[v][i] -= d
                self.c[i][v] += d
                self.link[i].add(v)
                w += d
                if w == f:
                    break
        
        self.visit[v] = False
        return w
        

def main():
    w = MaxFlow(2 * N + 2)
    for i in range(N):
        w.add_link(0, i + 1, 1)
        w.add_link(N + i + 1, 2 * N + 1, 1)
        for j in range(N):
            if a[i] < c[j] and b[i] < d[j]:
                w.add_link(i + 1, N + j + 1, 1)
    
    ans = w.solve(2 * N + 1, 0, INF)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!python3

INF = 10 ** 15


# input
N = int(input())
a, b, c, d = [None] * N, [None] * N, [None] * N, [None] * N
for i in range(N):
    a[i], b[i] = list(map(int, input().split()))
for i in range(N):
    c[i], d[i] = list(map(int, input().split()))


class MaxFlow():

    def __init__(self, n):
        self.n = n
        self.c = [[0] * n for _ in range(n)]
        self.visit = [False] * n

    def add_link(self, x, y, capa):
        self.c[x][y] += capa
    
    def solve(self, t, v, f):
        if v == t:
            return f
        self.visit[v] = True
        
        w = 0
        for i in range(self.n):
            if self.visit[i] or self.c[v][i] == 0:
                continue
            d = self.solve(t, i, min(f - w, self.c[v][i]))
            if d > 0:
                self.c[v][i] -= d
                self.c[i][v] += d
                w += d
                if w == f:
                    break
        
        self.visit[v] = False
        return w
        

def main():
    w = MaxFlow(2 * N + 2)
    for i in range(N):
        w.add_link(0, i + 1, 1)
        w.add_link(N + i + 1, 2 * N + 1, 1)
        for j in range(N):
            if a[i] < c[j] and b[i] < d[j]:
                w.add_link(i + 1, N + j + 1, 1)
    
    ans = w.solve(2 * N + 1, 0, INF)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
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)]
a.sort(key=lambda x:x[0])
b.sort(key=lambda x:x[1],reverse=1)
ans=0
i,j=0,0
while i<n and j<n:
  if a[i][0]>b[j][0]:
    j+=1
    continue
  elif a[i][1]>b[j][1]:
    i+=1
  else:
    ans+=1
print(ans)

Submission status: Time Limit Exceeded

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

dp = {}


def check(v, p):
    return p & (1 << v)


def visit(v, p):
    return p ^ (1 << v)


def count(p):
    return bin(p).count('1')


def solve(i, p):
    if i == N:
        return count(p)

    k = (i, p)
    if k in dp:
        return dp[k]

    a, b = R[i]
    # ペアにならなかった
    m = solve(i+1, p)
    for j, (c, d) in enumerate(B):
        # すでにペアを持つ要素は無視
        if check(j, p):
            continue
        # ペアになった
        if a < c and b < d:
            m = max(m, solve(i+1, visit(j, p)))
    dp[k] = m
    return m


print(solve(0, 0))

Submission status: Time Limit Exceeded

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


def check(v, p):
    return p & (1 << v)


def visit(v, p):
    return p ^ (1 << v)


def count(p):
    return bin(p).count('1')


def solve(i, p):
    if i == N:
        return count(p)

    a, b = R[i]
    # ペアにならなかった
    m = solve(i+1, p)
    for j, (c, d) in enumerate(B):
        # すでにペアを持つ要素は無視
        if check(j, p):
            continue
        # ペアになった
        if a < c and b < d:
            m = max(m, solve(i+1, visit(j, p)))
    return m


print(solve(0, 0))

Submission status: Time Limit Exceeded

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


def solve(i, p):
    if i == N:
        return len(p)

    a, b = R[i]
    # ペアにならなかった
    s = [solve(i+1, p)]
    for c, d in B:
        # すでにペアを持つ要素は無視
        if (c, d) in p:
            continue
        # ペアになった
        if a < c and b < d:
            s.append(solve(i+1, p + [(c, d)]))
    return max(s)


print(solve(0, []))