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:
def dfs(v, visited):
    """
    :param v: X側の未マッチングの頂点の1つ
    :param visited: 空のsetを渡す（外部からの呼び出し時）
    :return: 増大路が見つかればTrue
    """
    for u in edges[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

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

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

edges = [set() for _ in range(N)]
matched = [-1] * N

for i in range(len(match)):
    x, y = match[i]
    edges[x].add(y)

# 増大路発見に成功したらTrue(=1)。合計することでマッチング数となる
print(sum(dfs(s, set()) for s in range(N)))



#
# def get_edge(M, u, U=None):
#     if U == None:
#         for x in M[:]:
#             if x[0] == u:
#                 return x[1]
#             elif x[1] == u:
#                 return x[0]
#
#     else:
#         for x in M[:]:
#             if x[0] == u and x[1] in U:
#                 return x[1]
#             elif x[1] == u and x[0] in U:
#                 return x[0]
#     return None
#
#
# def get_nodes(M):
#     U = set()
#     V = set()
#     for x in M:
#         U.add(x[0])
#         V.add(x[1])
#     return (U, V)
#
#
# def augpath(Si, Ti, M, E):
#     (U, V) = get_nodes(M)
#     Ti1 = set(x[1] for x in E if x[0] in Si and not x[1] in Ti)
#
#     if Ti1 == set():
#         return (M, None)
#
#     elif Ti1.difference(V) == set():
#         Si1 = set(x[0] for x in M if x[1] in Ti1)
#         (M, ui1) = augpath(Si1, Ti.union(Ti1), M, E)
#
#         if ui1 == None:
#             return (M, None)
#
#         else:
#             v = get_edge(M, ui1)
#             M.remove((ui1, v))
#
#             ui = get_edge(E, v, U=Si)
#             M.append((ui, v))
#
#             return (M, ui)
#
#     else:
#         v = Ti1.difference(V).pop()
#         u = get_edge(E, v, U=Si)
#         M.append((u, v))
#
#         return (M, u)
#
#
# def Hungary(U0, V0, E):
#     U_bef = set()
#     M = []
#     cnt = 0
#     length = len(U0)
#
#     # CALC
#     while True:
#
#         # INIT
#         (U, V) = get_nodes(M)
#         u = U0[cnt % length]
#         cnt = cnt + 1
#         S0 = set()
#         S0.add(u)
#         T0 = set()
#
#         # 終了条件(すべての頂点から始まる増大道を調べて、マッチング数が変わっていなければ、それ以上増えることはない)
#         if cnt % length == 0:
#             if U.difference(U_bef) == set():
#                 break
#             U_bef = U.copy()
#
#         # 枝刈り(すでにマッチングしている頂点から始まる道は増大道ではない)
#         if u in U:
#             continue
#
#         # CALC
#         (M, u) = augpath(S0, T0, M, E)
#
#     return M
#
#
# N = int(input())
# red = [list(map(int,input().split())) for _ in range(N)]
# blue = [list(map(int,input().split())) for _ in range(N)]
# match = []
# redg = [i for i in range(N)]
# blueg = [i for i in range(N)]
#
# for i in range(N):
#     for j in range(N):
#         if red[i][0] < blue[j][0] and red[i][1] < blue[j][1]:
#             match.append((i, j))
#
# edges = Hungary(redg, blueg, match)
# print(len(edges))

Submission status: Accepted

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

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

g = []
for _ in range(2*n):
    g.append([])
match = [-1 for _ in range(2*n)]
used = [False for _ in range(2*n)]

def add_edge(v, u):
    g[u].append(v)
    g[v].append(u)

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

def dfs(v):
    used[v] = True
    for u in g[v]:
        w = match[u]
        if w<0 or not used[w] and dfs(w):
            match[v] = u
            match[u] = v
            return True
    return False

cnt = 0
for v in range(n):
    if match[v]<0:
        used = [False for _ in range(2*n)]
        if dfs(v):
            cnt += 1
print(cnt)

Submission status: Accepted

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

gr = {i:[] for i in range(2 * n)}
for i in range(n):
    ai, bi = ab[i]
    for j in range(n):
        cj, dj = cd[j]
        if ai < cj and bi < dj:
            gr[i].append(n + j)
            gr[n + j].append(i)

ans = 0
ab = list(reversed(sorted(ab)))
cd = list(sorted(cd))
used = [False for _ in range(2 * n)]
match = [-1 for _ in range(2 * n)]

def dfs(v):
    global used, n, gr, match
    used[v] = True
    for u in gr[v]:
        w = match[u]
        if w < 0 or (not used[w] and dfs(w)):
            match[v] = u
            match[u] = v
            return True
    return False

for v in range(2 * n):
    if match[v] < 0:
        used = [False for _ in range(2 * n)]
        if dfs(v):
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from bisect import bisect
from operator import itemgetter
def inpl(): return list(map(int, input().split()))
g0 = itemgetter(0)

N = int(input())
ans = 0
R = sorted([inpl() + [i] for i in range(N)])
B = sorted([inpl() + [i] for i in range(N)])

edges = []

for i, r in enumerate(R):    
    B2 = sorted([(b[1], b[2]) for b in B[bisect(list(map(g0, B)), r[0]):]])
    edges.append([b[1] for b in B2[bisect(list(map(g0, B2)), r[1]):]])

searched = [False for _ in range(N)]
matched = [-1 for _ in range(N)]

def dfs(v):
    for u in edges[v]:
        if searched[u]:
            continue
        searched[u] = True
        if matched[u] == -1:
            matched[u] = v
            return True
        elif dfs(matched[u]):
            matched[u] = v
            return True
    return False

for i in range(N):
    searched = [False]*N
    ans += dfs(i)

print(ans)

Submission status: Accepted

Solution code:
N = int(input())

red = []
blue = []
count = 0

dellist = lambda items, indexes: [item for index, item in enumerate(items) if index not in indexes]

for n in range(2*N):
    v = list(map(int, input().split()))
    if n < N:
        red.append(v)
    else:
        blue.append(v)


for x in range(2*N):

    for k in range(2):
        r_remove_list = []
        b_remove_list = []

        for i, b in enumerate(blue):
            if b[k] == x:
                cand = -1
                max_ = -1
                max_j = -1
                for j, r in enumerate(red):
                    if r[k] < x:
                        if r[1-k] < b[1-k] and max_ < r[1-k]:
                            cand = j
                            max_ = r[1-k]
                            max_j = j
                if cand >= 0:
                    r_remove_list.append(max_j)
                    b_remove_list.append(i)

        blue = dellist(blue,b_remove_list)
        red = dellist(red,r_remove_list)
        count += len(b_remove_list)


print(count)

Submission status: Accepted

Solution code:
import collections

class Dinic:
    def __init__(self, n):
        self.n = n
        self.g = [[] for i in range(n)]
    def add_edge(self, fr, to, cap):
        self.g[fr].append([to, cap, len(self.g[to])])
        self.g[to].append([fr, 0, len(self.g[fr])-1])
    def add_multi_edge(self, v1, v2, cap1, cap2):
        self.g[v1].append([v2, cap1, len(self.g[v2])])
        self.g[v2].append([v1, cap2, len(self.g[v1])-1])
    def bfs(self, s):
        level = [-1]*self.n
        deq = collections.deque()
        level[s] = 0
        deq.append(s)
        while deq:
            v = deq.popleft()
            for e in self.g[v]:
                if e[1]>0 and level[e[0]]<0:
                    level[e[0]] = level[v] + 1
                    deq.append(e[0])
        self.level = level
    def dfs(self, v, t, f):
        if v==t: return f
        es = self.g[v]
        level = self.level
        for i in range(self.it[v], len(self.g[v])):
            e = es[i]
            if e[1]>0 and level[v]<level[e[0]]:
                d = self.dfs(e[0], t, min(f, e[1]))
                if d>0:
                    e[1] -= d
                    self.g[e[0]][e[2]][1] += d
                    self.it[v] = i
                    return d
        self.it[v] = len(self.g[v])
        return 0
    def max_flow(self, s, t):
        flow = 0
        while True:
            self.bfs(s)
            if self.level[t]<0: break
            self.it = [0]*self.n
            while True:
                f = self.dfs(s, t, 10**9+7)
                if f>0:
                    flow += f
                else:
                    break
        return flow

n = int(input())

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

B = 100
dinic = Dinic(B * 2 + 2)
for i in range(n):
    dinic.add_edge(0, 2 + i, 1)
for j in range(n):
    dinic.add_edge(2 + n + j, 1, 1)
    
for i in range(n):
    for j in range(n):
        if reds[i][0] < blues[j][0] and reds[i][1] < blues[j][1]:
            dinic.add_edge(2 + i, 2 + n + j, 1)

f = dinic.max_flow(0, 1)
print(f)

Submission status: Accepted

Solution code:
n = int(input())
red = sorted([list(map(int, input().split())) for i in range(n)])
blu = sorted([list(map(int, input().split())) for i in range(n)])
ans = 0
for x,y in blu:
    r = [z for z in red if (z[0] < x) & (z[1] < y)]
    if r:
        r.sort(key=lambda x:x[1])
        red.remove(r[-1])
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = []
B = []
C = []
D = []
for i in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
for i in range(N):
    c, d = map(int, input().split())
    C.append(c)
    D.append(d)

G = [[] for i in range(2 * N + 10)]
for i in range(N):
    for j in range(N):
        if A[i] < C[j] and B[i] < D[j]:
            G[i].append(N + j)
            G[N + j].append(i)

used = [False for i in range(2 * N + 10)]
match = [-1 for i in range(2 * N + 10)]

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

ans = 0
for v in range(N):
    if match[v] < 0:
        for i in range(2 * N + 10):
            used[i] = False
        if dfs(v):
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
edges = [set() for _ in range(n)]
matched = [-1] * n
ab = [list(map(int, input().split())) for _ in range(n)]
cd = [list(map(int, input().split())) for _ in range(n)]
for j, (c, d) in enumerate(cd):
    for i, (a, b) in enumerate(ab):
        if a < c and b < d:
            edges[i].add(j)


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


print(sum(dfs(s, set()) for s in range(n)))

Submission status: Accepted

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

    for i in range(n):
        c_, d_ = map(int, input().split())
        c.append(c_)
        d.append(d_)

    import numpy as np
    a, b, c, d = np.array(a), np.array(b), np.array(c), np.array(d)

    arg = np.argsort(b)[::-1]
    a = a[arg]
    b = b[arg]

    argc = np.argsort(c)
    c = c[argc]
    d = d[argc]


    n_pair = 0
    for i in range(n):
        c_, d_ = c[i], d[i]
        for j, a_ in enumerate(a):
            b_ = b[j]
            if a_ < c_ and b_ < d_:
                n_pair += 1
                a = np.delete(a, j)
                b = np.delete(b, j)
                #print(a_, b_, c_, d_)
                break

    print(n_pair)

solve()

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

N=int(input())
    
def dfs(u):
    for v in range(nv):
        if adj[u][v] and not visited[v]:
            visited[v] = True
            if matches[v] is None or dfs(matches[v]):
                matches[v] = u
                return True
    return False
 
#nu, nv, ne = map(int, input().split(' '))
nu=N
nv=N
adj = [[False] * nv for _ in range(nu)]
matches = [None] * nv
count = 0
 
a = []
b = []
for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    a.append(x1)
    b.append(y1)
c = []
d = []
for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    for j in range(N):
        if (x1-a[j])>0 and (y1-b[j])>0:
            adj[i][j] = True
 
for u in range(nu):
    visited = [False] * nv
    if dfs(u): count += 1
 
print(count)

#print([adj])

Submission status: Accepted

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


import collections
import itertools
import sys


#: The value representing "infinity."
INF = 10 ** 8

#: The maxium number of recursion.
REC_LIMIT = 10000

#: Named tuple representing a edge in the flow network in question.
FlowEdge = collections.namedtuple("FlowEdge", "source sink capacity")


class FlowNetwork(object):

    """Class representing a flow network.

    :param int num_vertices: The number of vertices in the network.
    """

    def __init__(self, num_vertices):
        self.adj_edges = [set() for _ in range(num_vertices)]
        self.flow = None
        self.rev_edge = dict()
        self.used = None

    def get_edges_from(self, vertex):
        """Returns the set of edges adjacent to the vertex.

        :param int vertex: The index of vertex.
        :returns: The set of edges adjacent to the vertex.
        :rtype: set
        """

        return self.adj_edges[vertex]

    def add_edge(self, source, sink, capacity):
        """Add an edge u -> v to the flow network.

        :param int source: The vertex u.
        :param int sink: The vertex v.
        :param int capacity: The capacity of the edge.
        """

        assert source != sink
        forward_edge = FlowEdge(source, sink, capacity)
        backward_edge = FlowEdge(sink, source, 0)
        self.rev_edge[forward_edge] = backward_edge
        self.rev_edge[backward_edge] = forward_edge
        self.adj_edges[source].add(forward_edge)
        self.adj_edges[sink].add(backward_edge)

    def dfs(self, source, sink, flow):
        """Finding augmenting paths using depth-first search.

        This method is not supposed to be used directly.
        Instead, use :meth:`FlowNetwork.ford_fulkerson`.
        """

        if source == sink:
            return flow
        self.used[source] = True
        for edge in self.get_edges_from(source):
            rest = edge.capacity - self.flow[edge]
            if self.used[edge.sink] or rest <= 0:
                continue
            d = self.dfs(edge.sink, sink, min(flow, rest))
            if d > 0:
                self.flow[edge] += d
                self.flow[self.rev_edge[edge]] -= d
                return d
        return 0

    def ford_fulkerson(self, source, sink):
        """Computing maximum flow using the Ford-Fulkerson algorithm.

        :param int source: The source.
        :param int sink: The sink.
        :return: Maximum flow.
        """

        self.flow = collections.defaultdict(int)
        max_flow = 0
        while True:
            self.used = collections.defaultdict(bool)
            df = self.dfs(source, sink, INF)
            if df == 0:
                return max_flow
            else:
                max_flow += df


def compute_max_num_pairs(num_points, red_points, blue_points):
    network = FlowNetwork(2 + 2 * num_points)
    source_idx = 2 * num_points
    sink_idx = source_idx + 1
    # source -> each vertex
    # each vertex -> sink
    for i in range(num_points):
        network.add_edge(source_idx, i, 1)
        network.add_edge(num_points + i, sink_idx, 1)
    g = itertools.product(enumerate(red_points),
                          enumerate(blue_points, start=num_points))
    for (ri, (rx, ry)), (bi, (bx, by)) in g:
        if rx < bx and ry < by:
            network.add_edge(ri, bi, 1)
    res = network.ford_fulkerson(source_idx, sink_idx)
    return res


def main():
    sys.setrecursionlimit(REC_LIMIT)
    num_points = int(input())
    red_points = [tuple(int(z) for z in input().split())
                  for _ in range(num_points)]
    blue_points = [tuple(int(z) for z in input().split())
                   for _ in range(num_points)]
    res = compute_max_num_pairs(num_points, red_points, blue_points)
    print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def find(u, c, p, v):
    n = len(c)
    if not v[u]:
        v[u] = True
        for q in xrange(n):
            if c[u][q]:
                if p[q]==-1 or find(p[q], c, p ,v):
                    p[q] = u
                    return True
    return False

def maxMatch(c):
    foo = 0
    n = len(c)
    p = [-1 for i in xrange(n)]
    for i in xrange(n):
        v = [False for j in xrange(n)]
        if find(i, c, p, v):
            foo += 1
    return foo

def process(r, b):
    n = len(r)
    c = [[False for i in xrange(n)] for j in xrange(n)]
    for i in xrange(n):
        for j in xrange(n):
            if r[i][0]<b[j][0] and r[i][1]<b[j][1]:
                c[i][j] = True
    return maxMatch(c)

def main():
    n = int(raw_input().strip())
    r = []
    b = []
    for i in xrange(n):
        x, y = [int(sub) for sub in raw_input().strip().split()]
        r.append((x, y))
    for i in xrange(n):
        x, y = [int(sub) for sub in raw_input().strip().split()]
        b.append((x, y))
    print process(r, b)

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
a = []
for i in range(n):
    x, y = map(int, input().split())
    a.append((x, y))
b = []
for i in range(n):
    x, y = map(int, input().split())
    b.append((x, y))
sus = [[] for i 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]:
            sus[i].append(j)

conn = [-1 for i in range(n)]

def dfs(x):
    global bio
    bio[x] = 1
    for y in sus[x]:
        if conn[y] == -1:
            conn[y] = x
            return 1
        if bio[conn[y]] == 0 and dfs(conn[y]):
            conn[y] = x
            return 1
    return 0

s = 0
for i in range(n):
    bio = [0 for j in range(n)]
    s += dfs(i)
print(s)

Submission status: Runtime Error

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
import networkx as nx
def resolve():
    n = int(input())
    A = [tuple(map(int, input().split())) for _ in range(n)]
    B = [tuple(map(int, input().split())) for _ in range(n)]
    G = nx.Graph()
    G.add_nodes_from(range(n))
    G.add_nodes_from(range(n, 2 * n))
    for i in range(n):
        ax, ay = A[i]
        for j in range(n):
            bx, by = B[j]
            if ax < bx and ay < by:
                G.add_edge(i, n + j)

    A = nx.algorithms.bipartite.matching.hopcroft_karp_matching(G, top_nodes = range(n))
    print(len(A) // 2)
resolve()

Submission status: Runtime Error

Solution code:
s=input()
k=int(input())
l=list(s)
for i in range(len(s)):
 if 26-(ord(s[i])-ord("a"))<=k:k-=26-(ord(s[i])-ord("a"));l[i]="a"
print("".join(l[:-1]+list(chr((ord(l[-1])-97+k)%26+97))))

Submission status: Runtime Error

Solution code:
from operator import itemgetter
from bisect import bisect
n = int(input())
a = [tuple(map(int,input().split())) for i in range(n)]
b = [tuple(map(int,input().split())) for i in range(n)]
a.sort(key=itemgetter(1))
a.sort(key=itemgetter(0))
b.sort(key=itemgetter(1))
b.sort(key=itemgetter(0))

ans = 0
for l,r in b:
  ind = bisect(a,(l-1,r-1))
  chk = 0
  for i in range(ind):
    if a[i][1] < r:
      chk = max(chk,a[i][1])
      if chk == a[i][1]:
        d = i
  if ind > 0:
    ans += 1
    k = a[d]
    a.remove(k)
print(ans)

Submission status: Runtime Error

Solution code:
import bisect as bs
import sys

n = int(input())
array = []

for i in range(n):
  a,b = map(int, input().split())
  array.append((a,b,False))
  
for j in range(n):
  c,d = map(int, input().split())
  array.append((c,d,True))
  
array.sort()

blue = []

count = 0 
for v in array:
  if v[2]:
    index = bs.bisect_left(blue, v[1])
    if index != 0:
      blue[index-1] = sys.maxsize
      count += 1
      blue.sort()
      
  else:
    blue.append(v[1])
    blue.sort()
    
print(count)import bisect as bs
import sys

n = int(input())
array = []

for i in range(n):
  a,b = map(int, input().split())
  array.append((a,b,False))
  
for j in range(n):
  c,d = map(int, input().split())
  array.append((c,d,True))
  
array.sort()

blue = []

count = 0 
for v in array:
  if v[2]:
    index = bs.bisect_left(blue, v[1])
    if index != 0:
      blue[index-1] = sys.maxsize
      count += 1
      blue.sort()
      
  else:
    blue.append(v[1])
    blue.sort()
    
print(count)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

n,m=mii()

print((m*1900+(n-m)*100)*(2**m))

Submission status: Runtime Error

Solution code:
from numpy import*;B=searchsorted;a,b=loadtxt(open(0),'i',skiprows=1);c=0;l=2**29
while l:y=sort(hstack((b%l-l,b%l)));A=l-a%l;l//=2;c+=sum(B(y,A)-B(y,A-l))%2*l
print(c)

Submission status: Runtime Error

Solution code:
from numpy import*;B=searchsorted;a,b=loadtxt(open(0),'i',skiprows=1);c=0;l=1<<29while l:h=l;l>>=1;y=sort(hstack((b%h-h,b%h)));c+=sum(B(y,h-a%h)-B(y,l-a%h))%2*l
print(c)

Submission status: Runtime Error

Solution code:
from numpy import*;B=searchsorted;a,b=loadtxt(open(0),'i',skiprows=1);c=0;l=2**29
while l:h=l;l/=2;y=sort(hstack((b%h-h,b%h)));c+=sum(B(y,h-a%h)-B(y,l-a%h))%2*l
print(c)

Submission status: Runtime Error

Solution code:
#2d plane 2n points
n=int(input())
cnt=0
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))
red=sorted(red,key=lambda x:x[0])
blue=sorted(blue,key=lambda x:x[0])
blue=blue[::-1]
for i in range(n-1,-1,-1):
    x,y=red[i][0],red[i][1]
    d=[]
    for some in blue:
        X,Y=some[0],some[1]
        if X>x:
            d.append((X,Y))
    if d:
        d=sorted(d,key=lambda x:x[1])
        node=-1
        for some in d:
            if some[1]>y:
                node=some
                cnt+=1
                break
        blue.remove(node)
print(cnt)

Submission status: Runtime Error

Solution code:
N = int(input())
ab = [[0, 0] for i in range(N)]
b = [0]*N
cd = [[0, 0] for i in range(N)]
d = [0]*N

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

points2 = [[] for i in range(N)]
ab.sort(key=lambda x: x[0])
ab.sort(key=lambda x: x[1])

for i in range(N):
    for j in range(N):
        if ab[i][0] < cd[j][0] and ab[i][1] < cd[j][1]:
            points2[j].append(i)

points2.sort(key=lambda x: len(x))
ans = 0

for i in range(N):
    if len(points[i]) == 0:
        continue
    for j in range(i+1, N):
        if points[i][0] in points[j]:
            points[j].pop(points[j].index(points[i][0]))
    ans += 1
print(ans)

Submission status: Runtime Error

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

def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    ans = 0
    for k in range(30):
        C = [x & ((1 << (k+1)) - 1) for x in A]
        D = [x & ((1 << (k+1)) - 1) for x in B]
        C.sort()
        D.sort()
        # print(f'k = {k}')
        # print(f'C = {C}')
        # print(f'D = {D}')
        p, q, r = 0, 0, 0
        for i in range(N-1, -1, -1):
            while p < N:
                if C[i] + D[p] >= 1 << k: break
                p += 1
            while q < N:
                if C[i] + D[q] >= 2 << k: break
                q += 1
            while r < N:
                if C[i] + D[r] >= 3 << k: break
                r += 1
            x = ((q - p) + (N - r)) % 2
            # print(p, q, r, x)
            ans = ans ^ (x << k)
    print(ans)

main()

Submission status: Runtime Error

Solution code:
from collections import namedtuple

Point = namedtuple('Point', ['x', 'y'])

N = int(input())

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

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

E = [[] for _ in range(N)]
for i, r in enumerate(R):
    for j, b in enumerate(B):
        if r.x < b.x and r.y < b.y:
            E[i].append(j)


class BipartiteMatching:
    def __init__(self, max_u: int, max_v: int, edges):
        self.max_u = max_u
        self.max_v = max_v
        self.edges = edges  # u->vの隣接行列
        self.__match = None

    def dfs(self, v: int, visited: set) -> bool:
        for u in self.edges[v]:
            if u in visited:
                continue
            visited.add(u)

            if self.__match[u] == -1 or self.dfs(self.__match[u], visited):
                self.__match[u] = v
                return True
        return False

    def execute(self):
        self.__match = [-1 for _ in range(self.max_u)]
        return sum(self.dfs(u, set()) for u in range(self.max_u))


print(BipartiteMatching(N, E).execute())

Submission status: Runtime Error

Solution code:
N = int(input())
dd = list(map(int, input().split()))
d = [0]
d.extend(dd)
d.append(0)

diff = [abs(d[i + 1] - d[i]) for i in range(N + 1)]
dd = []
for i in range(N):
    temp = abs(d[i + 1] - d[i]) + abs(d[i + 2] - d[i + 1])
    temp_2 = abs(d[i + 2] - d[i])
    if temp > temp_2:
        dd.append(temp - temp_2)
    else:
        dd.append(0)
s = sum(diff)
for i in range(N):
    print(s - dd[i])

Submission status: Runtime Error

Solution code:
import bisect
import numpy
N = int(input())
A = [int(a) for a in input().split()]
B = numpy.array([int(b) for b in input().split()])
Bit = [0] * 29

for i in range(29):
    BMod = numpy.sort(B % (2 ** (i+1)))
    for a in A:
        K, ai = 2 ** i, a % (2 ** (i+1))
        Bit[i] += bisect.bisect_left(BMod, 4 * K - ai) - bisect.bisect_left(BMod, 3 * K - ai) + bisect.bisect_left(BMod, 2 * K - ai) - bisect.bisect_left(BMod, K - ai)


Ans = 0
for i in range(29):
    if Bit[i] % 2 == 1:
        Ans += 2 ** i
print(Ans)

Submission status: Runtime Error

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 red[0]<blue[0] and red[1]<blue[1]:
            answer+=1
            red.pop(j)
            break

print(answer)

Submission status: Runtime Error

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(b):
    for j,r in enumerate(r):
        if red[0]<blue[0] and red[1]<blue[1]:
            answer+=1
            red.pop(j)
            break

print(answer)

Submission status: Runtime Error

Solution code:
N=int(input())
p_x=[0]*(2*N)
p_y=[0]*(2*N)
//N未満は赤い点
for i in range(N):
	x, y =map(int, input().split())
	p_x[x]=i
	p_y[y]=i
//N以上は青い点
for j in range(N):
	x, y =map(int, input().split())
	p_x[x]=N+j
	p_y[y]=N+j

pairs=N
done_point=[]

for i in range(2*N-1, 0, -1):
	if p_x[i]<N:
		pairs -= 1
		continue
	else:
		blue_x=i
		blue_y=p_y.index(p_x[i])
		
		for j in range(i-1, -1, -1)
			if p_x[j] < N:
				if p_x.index(p_x[j]) < blue_y:
					if p_x[j] not in done_point:
						done_point.append(p_x[j])
						break
				else:
					pair -= 1
					continue
			else:
				pair -= 1
				continue

print(pairs)

Submission status: Runtime Error

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

node = n

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)