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:
from operator import itemgetter
n=int(input())
A=[tuple(map(int,input().split())) for i in range(n)]
B=[tuple(map(int,input().split())) for j in range(n)]
A.sort()
B.sort()
count=0
for i in range(n):
    box=[A[i] for i in range(len(A)) if (A[i][0]<B[i][0]) and (A[i][1]<B[i][1])]
    if any(box):
        box=sorted(box, key=itemgetter(1))
        A.remove(box[-1])
        count +=1
print(count)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
n=int(input())
A=[tuple(map(int,input().split())) for i in range(n)]
B=[tuple(map(int,input().split())) for j in range(n)]
count=0
for i in range(n):
    box=[A[i] for i in range(len(A)) if (A[i][0]<B[i][0]) and (A[i][1]<B[i][1])]
    if any(box):
        box=sorted(box, key=itemgetter(1))
        A.remove(box[-1])
        count +=1
print(count)

Submission status: Wrong Answer

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

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

ab.sort(key=lambda x:x[1])
ab.sort(key=lambda x:x[0])
cd.sort(key=lambda x:x[1])
cd.sort(key=lambda x:x[0])

ans = 0

i = 0
j = 0
while j < n and i < n:
    while i < n and j < n and ab[i][1] > cd[j][1]:
        i += 1; j += 1
    if j >= n or i >= n:
        break
    if ab[i][0] < cd[j][0] and ab[i][1] < cd[j][1]:
        ans += 1
        # ペアを組めた
    i += 1
    j += 1
ab.sort(key=lambda x:x[0])
ab.sort(key=lambda x:x[1])
cd.sort(key=lambda x:x[0])
cd.sort(key=lambda x:x[1])

tmp = 0
i = 0
j = 0
while j < n and i < n:
    while i < n and j < n and ab[i][0] > cd[j][0]:
        i += 1; j += 1
    if j >= n or i >= n:
        break
    if ab[i][0] < cd[j][0] and ab[i][1] < cd[j][1]:
        tmp += 1
        # ペアを組めた
    i += 1
    j += 1


print(max(ans, tmp))

Submission status: Wrong Answer

Solution code:
import sys
from functools import reduce
import copy
import math
from pprint import pprint


sys.setrecursionlimit(4100000)


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def int_inputs(num_of_input):
    ins = [int(input()) for i in range(num_of_input)]
    return ins


def solve(inputs):
    int_inputs = list(map(string_to_int, inputs))
    N = len(inputs) // 2
    reds = int_inputs[:N]
    blues = int_inputs[N:]

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

    count = 0
    for i in range(N):
        candidates = []
        for j in range(len(blues)):
            if blues[j][0] > reds[i][0] and blues[j][1] > reds[i][1]:
                candidates.append([j, blues[j][0], blues[j][1]])
        if len(candidates) > 0:
            candidates.sort(key=lambda x: x[2])
            blues.pop(candidates[0][0])
            count += 1

    return count


def string_to_int(string):
    return list(map(int, string.split()))


if __name__ == "__main__":
    N = int(input())
    ret = solve(inputs(N*2))
    print(ret)

Submission status: Wrong Answer

Solution code:
n = int(input())
inf = -10**5
red = [ [ int(v) for v in input().split() ] for i in range(n) ]
blue = [ [ int(v) for v in input().split() ] for i in range(n) ]
red.sort()
red.reverse()
blue.sort()
blue.reverse()


ans = 0
for i, u in enumerate(red):
    for j, v in enumerate(blue):
        if u[0] < v[0] and u[1] < v[1]:
            ans += 1
            blue[j] = [inf, inf]
            break
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

import queue

class Dinic:
    def __init__(self, v, inf=sys.maxsize):
        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)

n = int(input())
data1 = [list(map(int,input().split())) for _ in range(n)]
data2 = [list(map(int,input().split())) for _ in range(n)]
v = 2*n + 2

D = Dinic(v)
for i in range(n):
    D.add_edge(0,i+1,1)
    D.add_edge(n+i+1,2*n+1,1)

for i,ab in enumerate(data1):
    for j,cd in enumerate(data2):
        if ab[0]<cd[0] and ab[1]<cd[1]:
            D.add_edge(i+1,n+i+1,1)

ans = D.max_flow(0,2*n+1)
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
Red = [list(map(int,input().split())) for i in range(N)]
Blue = [list(map(int,input().split())) for i in range(N)]
Red.sort()
Blue.sort(key=lambda x: x[1])
count = 0
for red in Red:
    for blue in Blue:
        if red[0]<blue[0] and red[1]<blue[1]:
            count += 1
            Blue.pop(Blue.index(blue))
            break
print(count)

Submission status: Wrong Answer

Solution code:
def slove():
    import sys
    import collections
    input = sys.stdin.readline
    n = int(input().rstrip('\n'))
    ab = [list(map(int, input().rstrip('\n').split())) for _ in range(n)]
    cd = [list(map(int, input().rstrip('\n').split())) for _ in range(n)]
    ab.sort(reverse=True)
    cd.sort(reverse=True)
    dic = collections.defaultdict(list)
    for i, abx in enumerate(ab):
        a, b = abx
        for j, cdx in enumerate(cd):
            c, d = cdx
            if a < c and b < d and "i" + str(i) not in dic and "j" + str(j) not in dic:
                dic["i" + str(i)] += [ab[i]]
                dic["j" + str(j)] += [cd[j]]
    print(len(dic) // 2)


if __name__ == '__main__':
    slove()

Submission status: Wrong Answer

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

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

cands = [[] for _ in range(n)]
for i in range(n):
    a = ab[i][0]
    b = ab[i][1]
    for c, d in cd:
        if a < c and b < d:
            cands[i].append((c, d))

cands.sort(key=lambda x: len(x))
used = set()
for cand in cands:
    for point in cand:
        if point not in used:
            used.add(point)
            break

ans = len(used)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque as dq
N = int(input())
R = [list(map(int, input().split())) + [0] for _ in range(N)]
B = [list(map(int, input().split())) + [1] for _ in range(N)]
P = sorted(R + B, key = lambda x: min(x[0], x[1]))
res = 0
inf = 10 ** 3
LIS = [inf] * N
Q = dq([])
for i in range(N * 2):
  if P[i][2] == 0:
    Q.append(P[i][1])
  elif len(Q):
    Q.popleft()
    res += 1
print(res)

Submission status: Wrong Answer

Solution code:
from collections import deque as dq
N = int(input())
R = [list(map(int, input().split())) + [0] for _ in range(N)]
B = [list(map(int, input().split())) + [1] for _ in range(N)]
P = sorted(R + B, key = lambda x: (x[0], -x[1]))
res = 0
inf = 10 ** 3
LIS = [inf] * N
Q = dq([])
for i in range(N * 2):
  if P[i][2] == 0:
    Q.append(P[i][1])
  elif len(Q):
    Q.popleft()
    res += 1
print(res)

Submission status: Wrong Answer

Solution code:
import bisect
n=int(input())
ab=[[int(i) for i in input().split()] for j in range(n)]
cd=[[int(i) for i in input().split()] for j in range(n)]
ab.sort()
cd.sort()

ans=0

for c,d in cd:
    now_y=-1
    check=False
    for a,b in ab:
        if a>=c:
            break
        if b<d and b>now_y:
            now_id=bisect.bisect_left(ab,[a,b])
            check=True

    if check:
        ans+=1
        ab.pop(now_id)
print(ans)

Submission status: Wrong Answer

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

candidates = [[] for _ in range(n)]
for i, (a, b) in enumerate(red):
    for c, d in blue:
        if a < c and b < d:
            candidates[i].append((c, d))

candidates.sort(key=len)

selection = []
for candidate in candidates:
    for point in candidate:
        if point not in selection:
            selection.append(point)
            break

print(len(selection))

Submission status: Wrong Answer

Solution code:
import sys
from bisect import *
from collections import *
from copy import deepcopy
from heapq import *
from itertools import *
from math import *
from operator import *
from pprint import *

sys.setrecursionlimit(10**8)

input = sys.stdin.readline


def main():
    """ main """
    N = int(input())
    REDS = [tuple(map(int, input().split())) for _ in range(N)]
    BLUES = [tuple(map(int, input().split())) for _ in range(N)]
    REDS.sort(reverse=True)
    BLUES.sort()

    ans = 0
    for ax,ay in REDS:
        bs = [(bx,by) for bx,by in BLUES if ax < bx]
        bs.sort(key=itemgetter(1))
        if 0<len(bs):
            BLUES.remove(bs[0])
            ans += 1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
rs = [[0, 0] for _ in range(n)]
bs = [[0, 0] for _ in range(n)]

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

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


#rs.sort(key=lambda x: x[0]+x[1])
#bs.sort(key=lambda x: x[0]+x[1])

#print(rs)
#print(bs)

rb = [[] for _ in range(n)]
for i in range(n):
  for j in range(n):
    if rs[i][0]<bs[j][0] and rs[i][1]<bs[j][1]:
      rb[i].append(j)
#print(rb)

br = [[] for _ in range(n)]
for i in range(n):
  for j in range(n):
    if rs[j][0]<bs[i][0] and rs[j][1]<bs[i][1]:
      br[i].append(j)
#print(br)

use = [False]*n
ans = 0
for i in range(n):
  min_br = n+1
  min_b = n+1
  for j in rb[i]:
    if use[j]:
      continue
    if len(br[j]) <= min_br:
      min_br = len(br[j])
      min_b = j
  if min_b != n+1:
    use[min_b] = True
    ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
rs = [[0, 0] for _ in range(n)]
bs = [[0, 0] for _ in range(n)]

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

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


rs.sort(key=lambda x: x[0]+x[1])
bs.sort(key=lambda x: x[0]+x[1])

#print(rs)
#print(bs)

rb = [[] for _ in range(n)]
for i in range(n):
  for j in range(n):
    if rs[i][0]<bs[j][0] and rs[i][1]<bs[j][1]:
      rb[i].append(j)
#print(rb)

rb.sort(key=lambda x: len(x))
#print(rb)
use = [False]*n
ans = 0
for i in range(n):
  for j in rb[i]:
    if not use[j]:
      ans += 1
      use[j] = True
      break
print(ans)

Submission status: Wrong Answer

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

p[0] = sorted(p[0], key = lambda x: x[0]*x[1], reverse=True)
p[1] = sorted(p[1], key = lambda x: x[0]*x[1])
ans = 0

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

print(ans)

Submission status: Wrong Answer

Solution code:

def main():
    N = int(input())
    small = [tuple(map(int, input().split())) for _ in [0]*N]
    large = [tuple(map(int, input().split())) for _ in [0]*N]
    small.sort(key=lambda x: (x[0], x[1]), reverse=True)
    large.sort(key=lambda x: (x[0], x[1]), reverse=True)
    ans = 0
    used = [0]*N
    for l in large:
        for i, s in enumerate(small):
            if (not used[i]) and s[0] < l[0] and s[1] < l[1]:
                used[i] = 1
                ans += 1
                break
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n=int(input())
ab=[[int(i) for i in input().split()] for j in range(n)]
cd=[[int(i) for i in input().split()] for j in range(n)]
ab=sorted(ab,key=lambda x:x[0]+x[1], reverse=True)
cd=sorted(cd,key=lambda x:x[0]+x[1])
    
dic={}
for i in range(n):
    for j in range(n):
        if ab[i][0]<cd[j][0] and ab[i][1]<cd[j][1] and j not in dic.values():
            dic[i]=j
            break
        
print(len(dic))

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline

def main():
    N=int(input())
    R=[]
    for _ in range(N):
        R.append(list(map(int, input().split())))
    B=[]
    for _ in range(N):
        B.append(list(map(int, input().split())))
    R.sort(reverse=True)
    B.sort(reverse=True)
    ans = 0
    while R:
        rx = max(R, key=lambda x:x[0])
        ry = max(R, key=lambda x:x[1])
        r = rx if rx[0] >= ry[1] else ry
        for b in B:
            if r[0]<=b[0] and r[1]<=b[1]:
                B.remove(b)
                ans += 1
                break
        R.remove(r)

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline

def main():
    N=int(input())
    R=[]
    for _ in range(N):
        R.append(list(map(int, input().split())))
    B=[]
    for _ in range(N):
        B.append(list(map(int, input().split())))
    ans = 0
    while R:
        rx = max(R, key=lambda x:x[0])
        ry = max(R, key=lambda x:x[1])
        r = rx if rx[0] >= ry[1] else ry
        for b in B:
            if r[0]<=b[0] and r[1]<=b[1]:
                B.remove(b)
                ans += 1
                break
        R.remove(r)

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
ab = [list(map(int,input().split())) for _ in range(N)]
cd = [list(map(int,input().split())) for _ in range(N)]
ab = sorted(ab, key=lambda x:x[1], reverse=True)
cnt = 0
for a, b in ab:
  for c, d in cd:
    if a<c and b<d:
      cd.remove([c,d])
      cnt+=1
      break

print(cnt)

Submission status: Wrong Answer

Solution code:
N = int(input())
ab = [list(map(int,input().split())) for _ in range(N)]
cd = [list(map(int,input().split())) for _ in range(N)]
cnt = 0
for a, b in ab:
  for c, d in cd:
    if a<c and b<d:
      cd.remove([c,d])
      cnt+=1
      break

print(cnt)

Submission status: Wrong Answer

Solution code:
n = int(input())
ls0 = [list(map(int, input().split())) for _ in range(n)]
ls1 = [list(map(int, input().split())) for _ in range(n)]
ls0.sort(key=lambda x: x[0], reverse=True)
count = 0
for x0, y0 in ls0:
    val = float('inf')
    index = -1
    for i, (x1, y1) in enumerate(ls1):
        if x0 <= x1:
            if y1 < val:
                index = i
                val = y1
    if index >= 0:
        count += 1
        ls1.remove(ls1[index])
print(count)

Submission status: Wrong Answer

Solution code:
n = int(input())
ls0 = [list(map(int, input().split())) for _ in range(n)]
ls1 = [list(map(int, input().split())) for _ in range(n)]
table = [[0 for _ in range(n)] for _ in range(n)]
for i, (x0, y0) in enumerate(ls0):
    for j, (x1, y1) in enumerate(ls1):
        if x0 <= x1 and y0 <= y1:
            table[i][j] = 1

count = 0
while True:
    if sum([sum(l) for l in table]) == 0:
        break
    minval = n + 1
    rindex = -1
    cindex = -1
    for i in range(n):
        s = sum(table[i])
        if 0 < s < minval:
            rindex = i
            cindex = -1
            minval = s
        s = sum([table[j][i] for j in range(n)])
        if 0 < s < minval:
            rindex = -1
            cindex = i
            minval = s
    if rindex >= 0:
        for i in range(n):
            if table[rindex][i] == 1:
                count += 1
                for j in range(n):
                    table[j][i] = 0
                    table[rindex][j] = 0
                break
    elif cindex >= 0:
        for i in range(n):
            if table[i][cindex] == 1:
                count += 1
                for j in range(n):
                    table[i][j] = 0
                    table[j][cindex] = 0
                break
print(count)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from heapq import heappush, heappop

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

red_flag = [0] * n
ans = 0
for i in range(n):
    idx = -1
    for j in range(n):
        if red[j][0] >= blue[i][0] or red_flag[j] == 1:
            continue
        if idx == -1 or red[idx][1] < red[j][1]:
            idx = j

    if idx >= 0:
        red_flag[idx] = 1
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter

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

Red.sort(key=itemgetter(0), reverse=True)
checked = [False for _ in range(N)]

c = 0
for rx, ry in Red:
    P = []
    for i, (bx, by) in enumerate(Blue):
        if bx > rx and not checked[i]:
            P.append((i, by))
    if P:
        P.sort(key=itemgetter(1))
        ip, _ = P[0]
        checked[ip] = True
        c += 1

print(c)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter

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

Red.sort(key=itemgetter(0), reverse=True)
checked = [False for _ in range(N)]

c = 0
for rx, ry in Red:
    P = []
    for i, (bx, by) in enumerate(Blue):
        if bx > rx and not checked[i]:
            P.append((i, ry))
    if P:
        P.sort(key=itemgetter(1))
        ip, _ = P[0]
        checked[ip] = True
        c += 1

print(c)

Submission status: Wrong Answer

Solution code:
n = int(input())
aka = []
ao = []
for _ in range(n):
    ab = list(map(int, input().split()))
    aka.append(ab)
for _ in range(n):
    cd = list(map(int, input().split()))
    ao.append(cd)
count = 0
for i in range(2*n):
    for j in range(2*n):
        if [2*n-1-i,2*n-1-j] in ao:
            for k in range(i+1,2*n):
                for l in range(j+1, 2*n):
                    if [2*n-1-k, 2*n-1-l] in aka:
                        aka.remove([2*n-1-k, 2*n-1-l])
                        count += 1
                        break
                else:
                    continue
                break
print(count)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

N = int(input().split()[0])
r_list = []
b_list = []

for _ in range(N):
    a, b = list(map(int, input().split()))
    r_list.append((a, b))

blue_dict = {}

for _ in range(N):
    c, d = list(map(int, input().split()))
    b_list.append((c, d))
    blue_dict[(c, d)] = []
    for ab in r_list:
        a, b = ab
        if a < c and b < d:
            blue_dict[(c, d)] += [(a, b)]

b_list = sorted(b_list, key=lambda x: x[1])
pair_list = []

for b in b_list:
    # xが小さいものから見ていく
    kouho_r_list = blue_dict[b]
    if kouho_r_list:
        kouho_r_list = sorted(kouho_r_list, key=lambda x: x[1], reverse=True)
        r = kouho_r_list[0]
        pair_list.append((r, a))

        for k, v in blue_dict.items():
            if r in v:
                v.remove(r)

ans = len(pair_list)
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

N = int(input().split()[0])
r_list = []
b_list = []

for _ in range(N):
    a, b = list(map(int, input().split()))
    r_list.append((a, b))

red_dict = {(a, b): [] for a, b in r_list}
blue_counter = {}

for _ in range(N):
    c, d = list(map(int, input().split()))
    b_list.append((c, d))
    blue_counter[(c, d)] = 0
    for ab in red_dict.keys():
        a, b = ab
        if a < c and b < d:
            red_dict[(a, b)] += [(c, d)]
            blue_counter[(c, d)] += 1

# 選択肢が少ないものから片付けていく
red_sorted_list = sorted(red_dict.items(), key=lambda x: x[1])
pair_list = []
for i in range(N):
    red = red_sorted_list[i]
    red_node = red[0]
    blue_list = red[1]

    if blue_list:
        # 対が少ない青い点から片付けていく
        blue_list = sorted(blue_list, key=lambda x: blue_counter[x])
        blue_node = blue_list[0]
        pair_list.append((red_node, blue_node))

        for r in red_sorted_list:
            # 他の赤ノードの候補から、当該青ノードを除去する
            if blue_node in r[1]:
                r[1].remove(blue_node)

ans = len(pair_list)
print(ans)

Submission status: Wrong Answer

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

found=[0]*n
for bx, by in blue:
    y=-1
    pair=-1

    for i,r in enumerate(red):
        rx, ry=r
        if found[i]:
            continue
        if bx>rx and by>ry:
            if ry>y:
                pair=i
                y=ry

    if pair!=-1:
        found[pair]=1

print(sum(found))

Submission status: Wrong Answer

Solution code:
#PDF解説
N = int(input())
Red, Blue = [], []
for n in range(N):
  Red.append([int(ab) for ab in input().split()])
Red.sort(key=lambda x: x[1], reverse=True)
for n in range(N):
  Blue.append([int(cd) for cd in input().split()])
Blue.sort(key=lambda x: x[0])

pairs = 0
for B in Blue:
  c, d = B
  for R in Red:
    a, b = R
    inclination = (d-b) / abs(c-a)
    if inclination > 0:
      pairs += 1
      Red.remove(R)
      break

print(pairs)

Submission status: Wrong Answer

Solution code:
#PDF解説
N = int(input())
Red, Blue = [], []
for n in range(N):
  Red.append([int(ab) for ab in input().split()])
Red.sort(key=lambda x: x[1], reverse=True)
for n in range(N):
  Blue.append([int(cd) for cd in input().split()])
Blue.sort(key=lambda x: x[0])

pairs = 0
for B in Blue:
  c, d = B
  for R in Red:
    a, b = R
    inclination = (d-b) / abs(c-a)
    if inclination > 0:
      pairs += 1
      print([R, B])
      Red.remove(R)
      break

print(pairs)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

def main():
    N = int(input())
    ab = sorted([list(map(int, input().split())) for i in range(N)], reverse=True)
    cd = sorted([list(map(int, input().split())) for i in range(N)])

    check = [False] * N
    ans = 0
    for i in range(N):
        a, b = ab[i]
        min_ = int(1e5)
        ind = -1
        for i in range(N):
            if not check[i]:
                c, d = cd[i]
                if c > a and d > b:
                    tmp = abs(a - c) + abs(b - d)
                    if min_ > tmp:
                        min_ = tmp
                        ind = i
        if ind != -1:
            check[ind] = True
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

red_coordinate.sort(reverse = True)
blue_coordinate.sort(reverse = True) #それぞれの座標はx座標が大きい順，同じ場合はy座標が大きい順に並ぶ
ans = 0

for i in range(n): #赤い点について回す
    for j in range(n): #青い点について回す
        find = False
        if red_coordinate[i][0] < blue_coordinate[j][0] \
            and red_coordinate[i][1] < blue_coordinate[j][1]:
            ans = ans + 1
            blue_coordinate[j][0] = 0
            blue_coordinate[j][1] = 0
            find = True
        
        if find:
            break

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
from fractions import gcd
# import queue
# from collections import Counter
# from itertools import accumulate
# from functools import reduce

def lcm(a, b):
    return a * b // gcd(a, b)

def combination_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)

big_prime = 1000000007

"""
# 標準入力取得
## 文字列
 =  sys.stdin.readline().rstrip()
 =  list(sys.stdin.readline().rstrip())

## 数値
 =  int(sys.stdin.readline())
 =  map(int, sys.stdin.readline().split())
 =  list(map(int, sys.stdin.readline().split()))
 =  [list(map(int,list(sys.stdin.readline().split()))) for i in range(N)]
"""
# def ds(L):
#     R = []
#     curr = L[0][0]
#     tmp = [L[0]]
#     for l in L[1::]:
#         if curr == l[0]:
#             tmp.append(l)
#         else:
#             tmp.sort(key=lambda x : x[1])
#             R + tmp
#             curr = l[0]
#             tmp = [l]
#     return R

N =  int(sys.stdin.readline())
A =  [list(map(int,list(sys.stdin.readline().split()))) for i in range(N)]
B =  [list(map(int,list(sys.stdin.readline().split()))) for i in range(N)]

A.sort()
B.sort()

cnt = 0
for a in A[::-1]:
    for b in B[::-1]:
        if a[0] < b[0] and a[1] < b[1]:
            b[0] = -1
            b[1] = -1
            cnt += 1
            break
print(cnt)

Submission status: Wrong Answer

Solution code:
N = int(input())
X = [0 for _ in range(2*N)]
Y = [0 for _ in range(2*N)]
for _ in range(N):
    a, b = map(int, input().split())
    X[a] = 1
    Y[b] = 1
for _ in range(N):
    c, d = map(int, input().split())
    X[c] = -1
    Y[d] = -1

l = 0
a = 0
for x in X:
    l += x
    if x < 0 and l >= 0:
        a += 1
    l = max(l, 0)
r = 0
b = 0
for y in Y:
    r += y
    if y < 0 and r >= 0:
        b += 1
    r = max(r, 0)

print(min(a, b))

Submission status: Wrong Answer

Solution code:
N = int(input())
X = [0 for _ in range(2*N)]
Y = [0 for _ in range(2*N)]
for _ in range(N):
    a, b = map(int, input().split())
    X[a] = 1
    Y[b] = 1
for _ in range(N):
    c, d = map(int, input().split())
    X[c] = -1
    Y[d] = -1

l = 0
a = 0
for x in X:
    l += x
    if x < 0 and l >= 0:
        a += 1

r = 0
b = 0
for y in Y:
    r += y
    if y < 0 and r >= 0:
        b += 1

print(min(a, b))

Submission status: Wrong Answer

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)]
used = [False] * n
a.sort(key = lambda x: x[0], reverse=True)
b.sort(key = lambda x: x[0], reverse=True)
result = 0
for i in range(n):
  for j in range(n):
    if used[j]:
      continue
    if a[i][0] < b[j][0] and a[i][1] < b[j][1]:
      print(a[i], b[j])
      used[j] = True
      result += 1
      break
print(result)

Submission status: Wrong Answer

Solution code:
inf = float('inf')
N = int(input())
A = []
B = []
for _ in range(N):
    A.append(tuple(map(int, input().split())))
for _ in range(N):
    B.append(tuple(map(int, input().split())))
A.sort(key=lambda t: t[0]+t[1], reverse=True)

count = 0
for i in range(N):
    x, y = A[i]
    min_dist = inf
    idx = -1
    for j in range(len(B)):
        tx, ty = B[j]
        if x < tx and y < ty:
            dist = tx-x+ty-y
            if min_dist > dist:
                min_dist = dist
                idx = j
    if idx >= 0:
        B.pop(idx)
        count += 1
print(count)

Submission status: Wrong Answer

Solution code:
from collections import deque

class Dinic:
    def __init__(self, v, inf=10**9+7):
        self.V = v
        self.inf = inf
        self.G = [list() for _ in range(v)]
        self.level = [-1 for _ in range(v)]
        self.iter = [0]*v

    def addedge(self,fr,to,cap):
        """
        G[fr] = [to, cap, rev]
        """
        go = [to, cap, None]
        go[2] = back = [fr, 0, go]
        self.G[fr].append(go)
        self.G[to].append(back)

    def bfs(self,st,en):
        q = deque([st])
        self.level = [-1 for _ in range(self.V)]
        self.level[st] = 0
        while q:
            cur = q.popleft()
            for x,cap,_ in self.G[cur]:
                if cap and self.level[x]<0:
                    self.level[x] = self.level[cur] + 1
                    q.append(x)
        return self.level[en] > 0

    def dfs(self,v,t,f):
        if v == t:
            return f
        for e in self.iter[v]:
            w,cap,rev = e
            if cap and self.level[v]<self.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
        while self.bfs(s,t):
            self.iter = list(map(iter, self.G))
            f = self.dfs(s,t,self.inf)
            while f:
                flow += f
                f = self.dfs(s,t,self.inf)
        return flow
n = int(input())
dinic = Dinic(n*2+2)
red = [tuple(map(int, input().split())) for _ in range(n)]
blue = [tuple(map(int, input().split())) for _ in range(n)]
for i in range(n):
  dinic.addedge(0,1+i,1)
  dinic.addedge(n+1+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[i][1]:
      dinic.addedge(1+i,n+1+j,1)
print(dinic.flow(0,2*n+1))