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: Accepted

Solution code:
n = int(input())
reds = list()
blues = list()
counter = 0

for i in range(n):
    reds.append(list(map(int,input().split())))
    
for i in range(n):
    blues.append(list(map(int,input().split())))
    
blues = sorted(blues,key=lambda x:x[0])
reds = sorted(reds,key=lambda x:x[1],reverse=True)

for blue in blues:
    for red in reds:
        if red[0] < blue[0] and red[1] < blue[1]:
            red[1] = 201
            counter += 1
            break
print(counter)

Submission status: Accepted

Solution code:
n = int(input())

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

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

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

count = 0
for blue in blues:
    lefts = sorted([red for red in reds if red[0] < blue[0]
                    and red[1] < blue[1]], key=lambda r: r[1])
    if len(lefts) == 0:
        continue

    reds.remove(lefts[-1])
    count += 1

print(count)

Submission status: Accepted

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[1],reverse=1)
b.sort(key=lambda x:x[0])
ans=0
for i in a:
  for j in b:
    if i[0]<j[0] and i[1]<j[1]:
      b.remove(j)
      ans+=1
      break
print(ans)

Submission status: Accepted

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

blue_Point.sort()

ans = 0
# x 座標に小さい順に blue point を見ていく
for i in range(N):
    index = -1
    diff  = 200
    for j in range(len(red_Point)):
        if red_Point[j][0] < blue_Point[i][0] and red_Point[j][1] < blue_Point[i][1]:
            if blue_Point[i][1] - red_Point[j][1] < diff:
                diff = blue_Point[i][1] - red_Point[j][1] 
                index = j
    if index != -1:
        del red_Point[index]
        ans += 1

print( ans )

Submission status: Accepted

Solution code:
INF = 1000000007

class Edge:
    def __init__(self, to, cap, rev):
        self.to = to
        self.cap = cap
        self.rev = rev

class FF:
    def __init__(self, n):
        self.n = n
        self.adj = []
        for i in range(n):
            self.adj.append([])
        self.used = [False] * n

    def add_edge(self, _from, _to, _cap):
        self.adj[_from].append(Edge(_to, _cap, len(self.adj[_to])))
        self.adj[_to].append(Edge(_from, 0, len(self.adj[_from]) - 1))

    def dfs(self, v, t, f):
        if v == t:
            return f
        self.used[v] = True
        for e in self.adj[v]:
            if self.used[e.to] == False and e.cap > 0:
                d = self.dfs(e.to, t, min(f, e.cap))
                if d > 0:
                 e.cap -= d
                 self.adj[e.to][e.rev].cap += d
                 return d
        return 0

    def max_flow(self, s, t):
        flow = 0
        while True:
            del self.used
            self.used = [False] * self.n
            f = self.dfs(s, t, INF)
            if f == 0:
                return flow
            flow += f


def main():
    n = int(input())
    reds = [tuple(int(s) for s in input().split()) for _ in range(n)]
    blues = [tuple(int(s) for s in input().split()) for _ in range(n)]
    ff = FF(2 * n + 2)
    for i in range(n):
        ff.add_edge(2 * n, i, 1)
        ff.add_edge(i + n, 2 * n + 1, 1)
    for i, (rx, ry) in enumerate(reds):
        for j, (bx, by) in enumerate(blues):
            if rx < bx and ry < by:
                ff.add_edge(i, j + n, 1)
    print(ff.max_flow(2 * n, 2 * n + 1))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def MI(): return map(int, input().split())
def II(): return int(input())
def IS(): return input()
def LI(): return list(map(int, input().split()))


n = II()
reds = [LI() for i in range(n)]
blues = [LI() for i in range(n)]
count = 0

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

for blue in blues:
    tmps = []
    for red in reds:
        if blue[0] > red[0]:
            tmps.append(red)
    tmps.sort(key=lambda x: x[1], reverse=True)
    for tmp in tmps:
        if blue[1] > tmp[1]:
            count += 1
            reds.pop(reds.index(tmp))
            break
print(count)

Submission status: Accepted

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

Submission status: Accepted

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

ans = 0
for x,y, in blue:
    i = bisect_left([a[0] for a in red], x)
    tmp = sorted(red[:i], key=lambda x:x[1], reverse=True)
    for xx, yy in tmp:
        if y > yy:
            ans += 1
            red.remove([xx,yy])
            break
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
L = []
for i in range(N):
  L.append(list(map(int,input().split())))
M = []
for i in range(N):
  M.append(list(map(int,input().split())))
L = sorted(L, key = lambda x:x[1])
L.reverse()
M.sort()
LT = [True]*N
MT = [True]*N
ans = 0
for i in range(N):
  curx = M[i][0]
  cury = M[i][1]
  for j in range(N):
    if LT[j] == True:
      if MT[i] == True:
        if curx >= L[j][0] and cury >= L[j][1]:
          LT[j] = False
          ans += 1
          MT[i] = False
print(ans)

Submission status: Accepted

Solution code:
# Dinic's algorithm
from collections import deque
class Dinic:
    def __init__(self, N):
        self.N = N
        self.G = [[] for i in range(N)]

    def add_edge(self, fr, to, cap):
        forward = [to, cap, None]
        forward[2] = backward = [fr, 0, forward]
        self.G[fr].append(forward)
        self.G[to].append(backward)

    def add_multi_edge(self, v1, v2, cap1, cap2):
        edge1 = [v2, cap1, None]
        edge1[2] = edge2 = [v1, cap2, edge1]
        self.G[v1].append(edge1)
        self.G[v2].append(edge2)

    def bfs(self, s, t):
        self.level = level = [None]*self.N
        deq = deque([s])
        level[s] = 0
        G = self.G
        while deq:
            v = deq.popleft()
            lv = level[v] + 1
            for w, cap, _ in G[v]:
                if cap and level[w] is None:
                    level[w] = lv
                    deq.append(w)
        return level[t] is not None

    def dfs(self, v, t, f):
        if v == t:
            return f
        level = self.level
        for e in self.it[v]:
            w, cap, rev = e
            if cap and level[v] < level[w]:
                d = self.dfs(w, t, min(f, cap))
                if d:
                    e[1] -= d
                    rev[1] += d
                    return d
        return 0

    def flow(self, s, t):
        flow = 0
        INF = 10**9 + 7
        G = self.G
        while self.bfs(s, t):
            *self.it, = map(iter, self.G)
            f = INF
            while f:
                f = self.dfs(s, t, INF)
                flow += f
        return flow

n = int(input())
ab = [list(map(int,input().split())) for i in range(n)]
dinic = Dinic(n*2+2)
for i in range(n):
    c,d = map(int,input().split())
    for j in range(n):
        if ab[j][0] < c and ab[j][1] < d:
            dinic.add_edge(i+1,n+j+1,1)
    dinic.add_edge(0,i+1,1)
    dinic.add_edge(n+i+1,2*n+1,1)
ans = dinic.flow(0,2*n+1)
print(ans)

Submission status: Accepted

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

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

answer=0
for Bluei in range(N):
  popwant=101
  count=0
  while(True):
    if count==len(Red) or Blue[Bluei][1]<=Red[count][1]:
      break
    if Red[count][0]<Blue[Bluei][0]:
      popwant=count
    count+=1
  if popwant<100:
    Red.pop(popwant)
    answer+=1
print(answer)

Submission status: Accepted

Solution code:
import sys
from collections import deque
import copy
import math
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N] = [long(input_raw[0])]
    R = []
    R_ = []
    for i in range(N):
        input_raw = read_func().strip().split()
        [a, b] = [long(input_raw[0]), long(input_raw[1])]
        R.append((a, b))

    B = []
    for i in range(N):
        input_raw = read_func().strip().split()
        [a, b] = [long(input_raw[0]), long(input_raw[1])]
        B.append((a, b))
    B.sort()
    count = 0
    already_set = set([])
    for i in range(len(B)):
        max_y = -1
        max_y_idx = -1
        for j in range(len(R)):
            if j not in already_set and B[i][0] > R[j][0] and B[i][1] > R[j][1]:
                if R[j][1] > max_y:
                    max_y = R[j][1]
                    max_y_idx = j
        if max_y_idx != -1:
            already_set.add(max_y_idx)
            count += 1


    print count




##    for i in range(N):
##        input_raw = read_func().strip().split()
##        [a, b] = [long(input_raw[0]), long(input_raw[1])]
##        R.append((a, b, i))
##        R_.append((b, a, i))
##    sortedR = sorted(R)
##    R_.sort()
##    Rx_order=[0]*N
##    Ry_order=[0]*N
##    for i in range(N):
##        Rx_order[sortedR[i][2]]=i
##        Ry_order[R_[i][2]]=i
##
##    B = []
##    B_ = []
##    for i in range(N):
##        input_raw = read_func().strip().split()
##        [a, b] = [long(input_raw[0]), long(input_raw[1])]
##        B.append((a, b, i))
##        B_.append((b, a, i))
##    sortedB = sorted(B)
##    B_.sort()
##    Bx_order=[0]*N
##    By_order=[0]*N
##    for i in range(N):
##        Bx_order[sortedB[i][2]]=i
##        By_order[B_[i][2]]=i

##
##    count = 0
##    already_set = set([])
##    for i in range(len(B)):
##        min_dist = sys.maxint
##        min_dist_idx = -1
##        for j in range(len(R)):
##            if j not in already_set and B[i][0] > R[j][0] and B[i][1] > R[j][1]:
##                dist = min(abs(Bx_order[i] - Rx_order[j]), abs(By_order[i] - Ry_order[j]))
##                if dist < min_dist:
##                    min_dist = dist
##                    min_dist_idx = j
##        if min_dist_idx != -1:
##            already_set.add(min_dist_idx)
##            count += 1
##        print i, min_dist_idx, min_dist, Bx_order[i], Rx_order[min_dist_idx],By_order[i], Ry_order[min_dist_idx]

    #print count




if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from operator import itemgetter

n = int(input())
red = []
blue = []
for i in range(n):
    a, b = map(int, input().split())
    red.append([a, b, min(a, b)])
for i in range(n):
    c, d = map(int, input().split())
    blue.append([c, d, min(c, d)])
red = sorted(red, key=itemgetter(2))
blue = sorted(blue, key=itemgetter(2))
red_x = set()
red_y = set()
blue_x = set()
blue_y = set()
for i in red:
    red_x.add(i[0])
    red_y.add(i[1])
for i in blue:
    blue_x.add(i[0])
    blue_y.add(i[1])
red_kouho = []
blue_kouho = []
for i in red:
    rx = i[0]
    ry = i[1]
    kouho = []
    for j in blue:
        bx = j[0]
        by = j[1]
        if rx < bx and ry < by:
            kouho.append((bx, by))
    red_kouho.append([kouho, len(kouho)])
red_kouho = sorted(red_kouho, key=itemgetter(1))
count = 0
for i in red_kouho:
    for j in i[0]:
        if j[0] in blue_x and j[1] in blue_y:
            blue_x.discard(j[0])
            blue_y.discard(j[1])
            count += 1
            break
print(count)

Submission status: Accepted

Solution code:
N = int(input())
red_points = [tuple(map(int, input().split())) for i in range(N)]
blue_points = [tuple(map(int, input().split())) for i in range(N)]

red_points.sort(key=lambda x: -x[1])
blue_points.sort(key=lambda x: x[0])

count = 0

points_used = [False for i in range(N)]

for blue in blue_points:
    for i, red in enumerate(red_points):
        if not points_used[i] and red[0] < blue[0] and red[1] < blue[1]:
            count += 1
            points_used[i] = True
            break
            
print(count)

Submission status: Accepted

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
N = int(input())
in_red = [tuple(map(int, input().split())) for _ in range(N)]
in_blu = [tuple(map(int, input().split())) for _ in range(N)]
in_red = sorted(in_red, key=lambda x: x[1], reverse=True)
in_blu = sorted(in_blu)

# print(in_red)
# print(in_blu)

ans = 0
for ei,x in enumerate(in_blu):
    x,y = x
    # print("x: {}, x,y: {}, {}".format(x,x,y))

    idx = 0
    found = False
    for e,p in enumerate(in_red):
        # print("\tp: {}, {}".format(p[0], p[1]))
        if p[0] < x and p[1] < y:
            idx = e
            found = True
            break
    if found:
        ans += 1
        in_red.pop(idx)
print(ans)

Submission status: Accepted

Solution code:
N = input()

ab = []
for _ in range(N):
    a, b = map(int, raw_input().split())
    ab.append([a, b])
ab.sort(key=lambda p:p[1], reverse=True)

cd = []
for _ in range(N):
    c, d = map(int, raw_input().split())
    cd.append([c, d])
cd.sort(key=lambda p:p[0])

res = 0
used = {}
for (c, d) in cd:
    for (a, b) in ab:
        if a < c and b < d and (a, b) not in used:
            used[(a, b)] = True
            res += 1
            break
print res

Submission status: Accepted

Solution code:
N=int(input())

red=[]
blue=[]

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

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

red=sorted(red,key=lambda x:-x[1])
blue=sorted(blue,key=lambda x:x[0])

answer=0
for i,b in enumerate(blue):
    for j,r in enumerate(red):
        if r[0]<b[0] and r[1]<b[1]:
            answer+=1
            red.pop(j)
            break

print(answer)

Submission status: Accepted

Solution code:
iipt=lambda:int(input())
miipt=lambda:list(map(int,input().split(" ")))
n=iipt()
r=[]
b=[]
for i in range(n):
    r.append(miipt())
for i in range(n):
    b.append(miipt())
r.sort(key=lambda x:x[1], reverse=True)
b.sort()
c=0
for xb, yb in b:
    for i, (xr, yr) in enumerate(r):
        if xr<xb and yr<yb:
            r[i]=(212, 212)
            c+=1
            break
    else:
        continue
print(c)

Submission status: Accepted

Solution code:
N=int(input())
R=[[int(i) for i in input().split()] for i in range(N)]
B=[[int(i) for i in input().split()] for i in range(N)]
List=[[] for i in range(N)]
count=[0]*N
unpaired=[True]*N

for i,r in enumerate(R):
  for j,b in enumerate(B):
    if b[0]>r[0] and b[1]>r[1]:
      List[i].append(j)
      count[j]+=1    
List.sort(key=lambda x:len(x))

ans=0
for l in List:
  k=float("inf")
  p=-1
  for j in l:
    if unpaired[j]:
      if k>count[j]:
        k=count[j]
        p=j
      count[j]-=1
  if p>=0:
    ans+=1
    unpaired[p]=False
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
red =[]
blue =[]
for i in range(n):
    x, y = map(int, input().split(' '))
    red.append(x + y*1000)
for i in range(n):
    x, y = map(int, input().split(' '))
    blue.append(x*1000 + y)
red.sort()
blue.sort()
ans = 0
red = red[::-1]
for b in blue:
    flag = True
    for r in red:
        if (r%1000 < b//1000) and (r//1000 < b%1000) and flag:
            flag = False
            red[red.index(r)]=9999999999
            ans +=1
print(ans)

Submission status: Accepted

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

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

red =  sorted(red,  key=lambda x:x[0])
blue = sorted(blue, key=lambda x:x[0])

ans = 0

for i in range(N):
    c = blue[i][0]
    d = blue[i][1]

    ind = -1
    y_max = -1
    for j in range(N - ans):
#        print('red = ',red[j])
        a = red[j][0]
        b = red[j][1]

        if a < c and b < d and y_max < b:
            ind = j
            y_max = b
        elif a > c:
            break

    if ind > -1:
        ans += 1
#        print('pop',c,d,red[ind])
        red.pop(ind)
#        print('remove',red)
print(ans)

Submission status: Accepted

Solution code:
def inpl(): return [int(i) for i in input().split()]

N = int(input())
red = [inpl() for _ in range(N)]
blue = [inpl() for _ in range(N)]
red = sorted(red,key = lambda x: -x[0])
blue = sorted(blue,key = lambda x: x[1])
ans = 0

for a,b in red:
    for c,d in blue:
        if a<c and b<d:
            ans +=1
            blue.remove([c,d])
            break
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a,b = [],[]
for _ in [0]*n:
  a += [list(map(int,input().split()))]
a.sort()
for _ in [0]*n:
  b += [list(map(int,input().split()))]
b.sort(key=lambda s:s[1])
c = 0
for t in a[::-1]:
  for s in b:
    if t[0]<s[0] and t[1]<s[1]:
      c += 1
      b.remove(s)
      break
print(n-len(b))

Submission status: Accepted

Solution code:
n = int(input())
a = []
b = []
for _ in [0]*n:
  a += [list(map(int,input().split()))]
a.sort(key=lambda t:-t[0])
for _ in [0]*n:
  b += [list(map(int,input().split()))]
b.sort(key=lambda s:s[1])
c = 0
for t in a:
  for s in b:
    if t[0]<s[0] and t[1]<s[1]:
      c += 1
      b.remove(s)
      break
print(n-len(b))

Submission status: Accepted

Solution code:
N = int(input())
r = [[0, 0] for i in range(N)]
b = [[0, 0] for i in range(N)]
for i in range(N):
    r[i][0], r[i][1] = map(int, input().split())
for i in range(N):
    b[i][0], b[i][1] = map(int, input().split())

r.sort(key=lambda x: (x[1]), reverse=True)
b.sort(key=lambda x: (x[0]))
r_flag = [False] * N
b_flag = [False] * N
count = 0

for i in range(N):
    for j in range(N):
        if r[j][0] < b[i][0] and r[j][1] < b[i][1] and not r_flag[j]:
            r_flag[j] = True
            count += 1
            break

print(count)

Submission status: Accepted

Solution code:
import bisect
N = int(input())
rs = [list(map(int, input().split())) for i in range(N)]
bs = [list(map(int, input().split())) for i in range(N)]
points = []
for r in rs:
    points.append((r[0], r[1], 'red'))
for b in bs:
    points.append((b[0], b[1], 'blue'))
points.sort()

rys = []
cnt = 0
for p in points:
    if p[2]=='red':
        bisect.insort_left(rys, p[1])
    else:
        idx = bisect.bisect_left(rys, p[1]) - 1
        if idx == -1:
            continue
        else:
            rys.pop(idx)
            cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
n = int(input())
red = []
for i in range(n):
    a,b = map(int,input().split())
    red.append([a,b])
blue = []
for i in range(n):
    c,d = map(int,input().split())
    blue.append([c,d])

red.sort(key = lambda x:(x[1],x[0]))
blue.sort(key = lambda x:(x[0],x[1]))

ans = 0
for i in range(n):
    for k in range(n):
        if blue[i][0] > red[n-1-k][0] and blue[i][1] > red[n-1-k][1]:
            ans += 1
            red[n-1-k][0] = 2000
            red[n-1-k][1] = 2000
            break
print(ans)

Submission status: Accepted

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




V = N*2 # 頂点数
MAX_V = V

G = [0]*MAX_V # グラフの隣接リスト表現
for i in range(MAX_V):
    G[i] = []
match = [-1]*MAX_V # マッチングのペア
used = [False]*MAX_V # DFSで既に調べたかのフラグ

# uとvを結ぶ辺をグラフに追加する
def addEdge(u, v):
    G[u].append(v)
    G[v].append(u)


##
for a in range(N):
    (rx, ry) = s[a]
    for b in range(N):
        (bx, by) = l[b]
        if rx < bx and ry < by:
            addEdge(a, b+N)


# 増加パスをDFSで探す
def dfs(v):
    used[v] = True
    for i in range(len(G[v])):
        u = G[v][i]
        w = match[u]
        if w < 0 or not used[w] and dfs(w):
            match[v] = u
            match[u] = v
            return True
    return False

# 二部グラフの最大マッチングを求める
def bipartiteMatching():
    res = 0
    for v in range(V):
        if match[v] < 0:
            for i in range(len(used)):
                used[i] = False
            if dfs(v):
                res += 1
    return res

print(bipartiteMatching())

Submission status: Accepted

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




V = N*2 # 頂点数
MAX_V = V

G = [0]*MAX_V # グラフの隣接リスト表現
for i in range(MAX_V):
    G[i] = []
match = [0]*MAX_V # マッチングのペア
used = [False]*MAX_V # DFSで既に調べたかのフラグ

# uとvを結ぶ辺をグラフに追加する
def addEdge(u, v):
    G[u].append(v)
    G[v].append(u)


##
for a in range(N):
    (rx, ry) = s[a]
    for b in range(N):
        (bx, by) = l[b]
        if rx < bx and ry < by:
            addEdge(a, b+N)


# 増加パスをDFSで探す
def dfs(v):
    used[v] = True
    for i in range(len(G[v])):
        u = G[v][i]
        w = match[u]
        if w < 0 or not used[w] and dfs(w):
            match[v] = u
            match[u] = v
            return True
    return False

# 二部グラフの最大マッチングを求める
def bipartiteMatching():
    res = 0
    for i in range(len(match)):
        match[i] = -1
    for v in range(V):
        if match[v] < 0:
            for i in range(len(used)):
                used[i] = False
            if dfs(v):
                res += 1
    return res

print(bipartiteMatching())

Submission status: Accepted

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




V = N*2 # 頂点数
MAX_V = V
G = [0]*MAX_V # グラフの隣接リスト表現
for i in range(MAX_V):
    G[i] = []
match = [0]*MAX_V # マッチングのペア
used = [False]*MAX_V # DFSで既に調べたかのフラグ

# uとvを結ぶ辺をグラフに追加する
def addEdge(u, v):
    G[u].append(v)
    G[v].append(u)

##
for a in range(N):
    (rx, ry) = s[a]
    for b in range(N):
        (bx, by) = l[b]
        if rx < bx and ry < by:
            addEdge(a, b+N)


# 増加パスをDFSで探す
def dfs(v):
    used[v] = True
    for i in range(len(G[v])):
        u = G[v][i]
        w = match[u]
        if w < 0 or (not used[w]) and dfs(w):
            match[v] = u
            match[u] = v
            return True
    return False

# 二部グラフの最大マッチングを求める
def bipartiteMatching():
    res = 0
    for i in range(len(match)):
        match[i] = -1
    for v in range(V):
        if match[v] < 0:
            for i in range(len(used)):
                used[i] = False
            if dfs(v):
                res += 1
    return res


#print(G)
#print(match)
print(bipartiteMatching())

Submission status: Accepted

Solution code:
n = int(input())

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


node = n*2
    
for i in range(n):
    for j in range(n):
        if red[i][0]<blue[j][0] and red[i][1]<blue[j][1]:
            ed.append([i,j+n])
            
import random
import numpy as np


edge = ed

def tutte():
    tut = np.zeros((node,node))
    for e in edge:
        x = random.random()
        tut[e[0]][e[1]]=x
        tut[e[1]][e[0]]=-x
    return tut



times = 11
rank = []
for i in range(times):
    rank.append(np.linalg.matrix_rank(tutte()))
rank.sort()
ans = rank[times//2]//2

print(ans)

Submission status: Accepted

Solution code:

n = int(input())

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

inf = 10**30

node = n*2+2

for i in range(1,n+1):
    ed.append([0,i,1])
    ed.append([n+i,2*n+1,1])
    
for i in range(n):
    for j in range(n):
        if red[i][0]<blue[j][0] and red[i][1]<blue[j][1]:
            ed.append([i+1,j+n+1,1])
    


edge = len(ed)
start = 0
goal = 2*n+1

# coding: utf-8
import queue

class Dinic:
    """Implementation of Dinic's Alogorithm"""

    def __init__(self, v, inf = 10**20):
        self.V = v
        self.inf = inf
        self.G = [[] for _ in range(v)]
        self.level = [0 for _ in range(v)]
        self.iter = [0 for _ in range(v)]

    def add_edge(self, from_, to, cap):
        # to: 行き先, cap: 容量, rev: 反対側の辺
        self.G[from_].append({'to':to, 'cap':cap, 'rev':len(self.G[to])})
        self.G[to].append({'to':from_, 'cap':0, 'rev':len(self.G[from_])-1})

    # sからの最短距離をbfsで計算
    def bfs(self, s):
        self.level = [-1 for _ in range(self.V)]
        self.level[s] = 0;
        que = queue.Queue()
        que.put(s)
        while not que.empty():
            v = que.get()
            for i in range(len(self.G[v])):
                e = self.G[v][i]
                if e['cap'] > 0 and self.level[e['to']] < 0:
                    self.level[e['to']] = self.level[v] + 1
                    que.put(e['to'])

    # 増加バスをdfsで探す
    def dfs(self, v, t, f):
        if v == t: return f
        for i in range(self.iter[v], len(self.G[v])):
            self.iter[v] = i
            e = self.G[v][i]
            if e['cap'] > 0 and self.level[v] < self.level[e['to']]:
                d = self.dfs(e['to'], t, min(f, e['cap']))
                if d > 0:
                    e['cap'] -= d
                    self.G[e['to']][e['rev']]['cap'] += d
                    return d

        return 0

    def max_flow(self, s, t):
        flow = 0
        while True:
            self.bfs(s)
            # bfsで到達不可
            if self.level[t] < 0 : return flow
            self.iter = [0 for _ in range(self.V)]
            f = self.dfs(s, t, self.inf)
            while f > 0:
                flow += f
                f = self.dfs(s,t, self.inf)
                
dinic = Dinic(node)
for e in ed:
    dinic.add_edge(e[0],e[1],e[2])
print(dinic.max_flow(start,goal))

Submission status: Accepted

Solution code:
n = int(input())

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

inf = 10**30

node = n*2+2

for i in range(1,n+1):
    ed.append([0,i,1])
    ed.append([n+i,2*n+1,1])
    
for i in range(n):
    for j in range(n):
        if red[i][0]<blue[j][0] and red[i][1]<blue[j][1]:
            ed.append([i+1,j+n+1,1])
    


edge = len(ed)
start = 0
goal = 2*n+1

"""
limit = [[0 for i in range(node)] for j in range(node)]
for i in edge:
    limit[i[0]][i[1]] += i[2]
"""

limit = [[] for i in range(node)]
for i in ed:
    limit[i[0]].append([i[1],i[2]])
    limit[i[1]].append([i[0],0])

ans = 0
while True:
    used = [False for i in range(node)]
    used[start] = True
    stack = [start]
    pre = [False for i in range(node)] # posの前
    pcos = [inf for i in range(node)] # posまでのコスト
    flg = False
    while stack:
        # print(stack)
        pos = stack.pop()
        for e in limit[pos]:
            if e[1] != 0 and (not used[e[0]]):
                pre[e[0]]=pos
                pcos[e[0]]=e[1]
                stack.append(e[0])
                used[e[0]]=True
                if e[0]==goal:
                    stack = []
                    flg = True
    if flg==False:
        print(ans)
        break
    pos = goal
    root = []
    minicost = inf
    while pos != start:
        root.append(pos)
        minicost = min(minicost,pcos[pos])
        pos = pre[pos]
    root.append(start)
    root.reverse()
    ans += minicost
    for i in range(len(root)-1):
        for j in range(len(limit[root[i]])):
            if limit[root[i]][j][0]==root[i+1]:
                limit[root[i]][j] = [root[i+1],limit[root[i]][j][1]-minicost]
        for j in range(len(limit[root[i+1]])):
            if limit[root[i+1]][j][0] == root[i]:
                limit[root[i+1]][j] = [root[i],limit[root[i+1]][j][1]+minicost]

Submission status: Accepted

Solution code:

N = int(input())
s = [0]*N
l = [0]*N
for i in range(N):
    a, b = map(int, input().split())
    s[i] = (-a, -b)

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

l.sort()
s.sort()

ans = 0
dp = [True]*N
for e in l:
    c = e[0]
    d = e[1]

    ind = -1
    high = -1
    for i in range(N):
        if dp[i]:
            a = -s[i][0]
            b = -s[i][1]
            
            if a < c and b < d:
                hoge = b
                if hoge > high:
                    high = hoge
                    ind = i
    if ind != -1:
        dp[ind] = False
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
# ２部マッチング
N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
B = [list(map(int, input().split())) for _ in range(N)]

def dfs(v, visited):
    for u in edge[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

matched = [-1] * N
edge = [set() for _ in range(N)]
for i, a in enumerate(A):
    for j, b in enumerate(B):
        if a[0] < b[0] and a[1] < b[1]:
            edge[i].add(j)
print(sum(dfs(v, set()) for v in range(N)))