Problem:


Score : 700 points

Problem Statement

We have a directed weighted graph with N vertices.
Each vertex has two integers written on it, and the integers written on Vertex i are A_i and B_i.

In this graph, there is an edge from Vertex x to Vertex y for all pairs 1 \leq x,y \leq N, and its weight is {\rm min}(A_x,B_y).

We will consider a directed cycle in this graph that visits every vertex exactly once.
Find the minimum total weight of the edges in such a cycle.

Constraints

2 \leq N \leq 10^5

1 \leq A_i \leq 10^9

1 \leq B_i \leq 10^9

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 B_1
A_2 B_2
:
A_N B_N

Output

Print the minimum total weight of the edges in such a cycle.

Sample Input 1

3
1 5
4 2
6 3

Sample Output 1

7

Consider the cycle 1→3→2→1. The weights of those edges are {\rm min}(A_1,B_3)=1, {\rm min}(A_3,B_2)=2 and {\rm min}(A_2,B_1)=4, for a total of 7.
As there is no cycle with a total weight of less than 7, the answer is 7.

Sample Input 2

4
1 5
2 6
3 7
4 8

Sample Output 2

10

Sample Input 3

6
19 92
64 64
78 48
57 33
73 6
95 73

Sample Output 3

227



Sample input:
3
1 5
4 2
6 3


Sample output:
7

Submission status: Accepted

Solution code:
# C
from heapq import heappush, heappop

N = int(input())
values = [0]*(2*N)

for i in range(N):
    A, B = map(int, input().split())
    values[i] = A
    values[i+N] = B

def argsort(R_arr):
    N = len(R_arr)
    R_args = [0]*N
    R_vars = [0]*N
    h = []
    for i in range(N):
        heappush(h, (R_arr[i], i))
    for i in range(N):
        a, b = heappop(h)
        R_args[i] = b
        R_vars[i] = a
    return R_vars, R_args

values_sorted, args = argsort(values)

# check for rare case
picked = [0]*N

for i in range(N):
    picked[args[i] % N] = 1
    
if sum(picked) == N:
    if args[N-1] % N == args[N] % N:
        res1 = sum(values_sorted[:(N-1)]) + values_sorted[N+1]
        res2 = sum(values_sorted[:(N+1)]) - values_sorted[N-2]
        res = min(res1, res2)
    else:
        res = sum(values_sorted[:(N-1)]) + values_sorted[N]
    res3 = sum(values[:N])
    res4 = sum(values[N:])
    res = min(res, res3, res4)
else:
    res = sum(values_sorted[:N])

print(res)

Submission status: Accepted

Solution code:
N = int(input())
A = []
B = []
for i in range(N):
    a, b = map(int, input().split())
    A += [a]
    B += [b]
s1 = sum(A)
s2 = sum(B)
C = A + B
C.sort()
s3 = sum(C[:N])
s4 = sum(C[N:])
check = 1
m1 = C[N-1]
m2 = C[N-2]
for i in range(N):
    a = min(A[i], B[i])
    b = max(A[i], B[i])
    if b < m1:
        check = 0
        break
    elif b == m1 and a != b:
        check = 0
        break
    elif a < m1:
        s4 = min(s4, s3 - m1 + b)
    elif a == m1:
        s4 = min(s4, s3 - m2 + b)
if check == 0:
    print(min(s1, s2, s3))
else:
    print(min(s1, s2, s4))

Submission status: Accepted

Solution code:
n=int(input())
a=[]
b=[]
for i in range(n):
    p,q=map(int,input().split())
    a.append((p,i,0))
    a.append((q,i,1))
a.sort(key=lambda x:x[0])
result=0
l=[0]*n
flag=0
for i in range(n):
    if l[a[i][1]]==1:
        flag=1
        break
    else:
        l[a[i][1]]=1
t=a[0][2]
s=0
for i in range(n):
    s+=a[i][2]-a[0][2]
if s==0:
    flag=1
if flag==1:

    for i in range(n):
        result+=a[i][0]
    print(result)
else:
    if a[n-1][1]==a[n][1]:
        for i in range(n):
            result+=a[i][0]
        result+=min(a[n+1][0]-a[n-1][0],a[n][0]-a[n-2][0])
        print(result)
    else:
        for i in range(n):
            result+=a[i][0]
        result+=a[n][0]-a[n-1][0]
        print(result)

Submission status: Accepted

Solution code:
from operator import itemgetter
from itertools import chain

n = int(input())
aaa = [tuple(map(int, input().split())) for _ in range(n)]
flatten = sorted(chain.from_iterable([(a, i), (b, i)] for i, (a, b) in enumerate(aaa)))
picked = set()
ans = 0

for ab, i in flatten[:n]:
    picked.add(i)
    ans += ab

if len(picked) == n:
    exclude = flatten[n - 1]
    include = flatten[n]
    if exclude[1] == include[1]:
        tmp1 = include[0] - flatten[n - 2][0]
        tmp2 = flatten[n + 1][0] - exclude[0]
        ans += min(tmp1, tmp2)
    else:
        ans -= exclude[0]
        ans += include[0]

ans = min(ans, sum(map(itemgetter(0), aaa)), sum(map(itemgetter(1), aaa)))

print(ans)

Submission status: Accepted

Solution code:
from operator import itemgetter
from itertools import chain

n = int(input())
aaa = [tuple(map(int, input().split())) for _ in range(n)]
flatten = list(chain.from_iterable([(a, i), (b, i)] for i, (a, b) in enumerate(aaa)))
flatten.sort()
flag = True
picked = set()
ans = 0

for ab, i in flatten[:n]:
    if flag and i in picked:
        flag = False
    picked.add(i)
    ans += ab

if flag:
    exclude = flatten[n - 1]
    include = flatten[n]
    if exclude[1] == include[1]:
        tmp1 = include[0] - flatten[n - 2][0]
        tmp2 = flatten[n + 1][0] - exclude[0]
        ans += min(tmp1, tmp2)
    else:
        ans -= exclude[0]
        ans += include[0]

ans = min(ans, sum(map(itemgetter(0), aaa)), sum(map(itemgetter(1), aaa)))

print(ans)

Submission status: Accepted

Solution code:
#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#

"""
AGC028 C
"""

from operator import itemgetter

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

abli.sort(key=itemgetter(0))
tmpans0 = sum(map(itemgetter(0), abli[:n]))
aiset = set([i for x, i, aorb in abli[:n] if not aorb])
biset = set([i for x, i, aorb in abli[:n] if aorb])
flag = bool(set.intersection(aiset, biset))


y, j, arob2 = abli[n]
z, k, arob3 = abli[n+1]

if flag:
    tmpans = tmpans0
else:
    min1 = y-max([x for x, i, aorb in abli[:n] if j != i])
    min2 = z-max([x for x, i, aorb in abli[:n] if j == i])
    tmpans = tmpans0 + min(min1, min2)

leftsum = sum([aa for aa, i, aorb in abli if not aorb])
rightsum = sum([bb for bb, i, aorb in abli if aorb])

print(min(leftsum, rightsum, tmpans))

Submission status: Accepted

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

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18
MOD = 10 ** 9 + 7

N = input()
ls = []
A_ = []
B_ = []
for i in range(N):
    A, B = map(int, raw_input().split())
    A_.append(A)
    B_.append(B)
    ls.append((A, 'A', i))
    ls.append((B, 'B', i))

ls.sort()

used = [[False] * N, [False] * N]

S = 0
for i in range(N):
    p = ls[i]
    S += p[0]
    if p[1] == 'A':
        used[0][p[2]] = True
    else:
        used[1][p[2]] = True

if True in used[0] and True in used[1]:
    pass
else:
    print S
    exit()

for i in range(N):
    if used[0][i] and used[1][i]:
        print S
        exit()

ans = INF
for i in range(N):
    T = S
    pos = N
    if ls[pos][2] == i:
        pos += 1
    if used[0][i]:
        T -= A_[i]
        T += ls[pos][0]
    else:
        T -= B_[i]
        T += ls[pos][0]
    ans = min(ans, T)

print ans

Submission status: Accepted

Solution code:
n = int(input())
c = []
not_c = []
chosen = set()
ans = 0
for i in range(n):
	a, b = map(int, input().split())
	not_c.append([max(a, b), i])
	c.append([min(a, b), i])
	ans += min(a, b)
	if a < b:
		chosen.add("a")
	elif a > b:
		chosen.add("b")

if len(chosen) < 2:
	print(ans)
else:
	c = sorted(c, reverse=True)
	not_c = sorted(not_c)
	#print(c, not_c)
	#used_c = [False] * n
	#used_n = [False] * n

	if c[0][1] != not_c[0][1]:
		ans = ans - c[0][0] + not_c[0][0]
		c_cur = 1
		not_cur = 1
	else:
		ans = min(ans - c[1][0] + not_c[0][0], ans - c[0][0] + not_c[1][0])
		if ans - c[1][0] + not_c[0][0] <= ans - c[0][0] + not_c[1][0]:
			c_cur = 2
			not_cur = 1
		else:
			c_cur = 1
			not_cur = 2
	if c_cur < n and not_cur < n:
		while c[c_cur][0] > not_c[not_cur][0]:
			if c[c_cur][1] != not_c[not_cur][1]:
				ans = ans - c[c_cur][0] + not_c[not_cur][0]
				c_cur += 1
				not_cur += 1
			else:
				ans = min(ans - c[c_cur+1][0] + not_c[not_cur][0], ans - c[c_cur][0] + not_c[not_cur+1][0])
				if ans - c[c_cur+1][0] + not_c[not_cur][0] <= ans - c[c_cur][0] + not_c[not_cur+1][0]:
					c_cur += 2
					not_cur += 1
				else:
					c_cur += 1
					not_cur += 2
			if c_cur >= n or not_cur >= n:
				break
	print(ans)

Submission status: Accepted

Solution code:
n = int(input())
c = []
not_c = []
chosen = set()
ans = 0
for i in range(n):
	a, b = map(int, input().split())
	not_c.append([max(a, b), i])
	c.append([min(a, b), i])
	ans += min(a, b)
	if a < b:
		chosen.add("a")
	elif a > b:
		chosen.add("b")

if len(chosen) < 2:
	print(ans)
else:
	c = sorted(c, reverse=True)
	not_c = sorted(not_c)
	#print(c, not_c)
	#used_c = [False] * n
	#used_n = [False] * n

	if c[0][1] != not_c[0][1]:
		ans = ans - c[0][0] + not_c[0][0]
		c_cur = 1
		not_cur = 1
	else:
		ans = min(ans - c[1][0] + not_c[0][0], ans - c[0][0] + not_c[1][0])
		if ans - c[1][0] + not_c[0][0] <= ans - c[0][0] + not_c[1][0]:
			c_cur = 2
			not_cur = 1
		else:
			c_cur = 1
			not_cur = 2
	if c_cur < n and not_cur < n:
		while c[c_cur][0] > not_c[not_cur][0]:
			if c[c_cur][1] != not_c[not_cur][1]:
				ans = ans - c[c_cur][0] + not_c[not_cur][0]
				c_cur += 1
				not_cur += 1
			elif c_cur == n - 1 or not_cur == n - 1:
				break
			else:
				ans = min(ans - c[c_cur+1][0] + not_c[not_cur][0], ans - c[c_cur][0] + not_c[not_cur+1][0])
				if ans - c[c_cur+1][0] + not_c[not_cur][0] <= ans - c[c_cur][0] + not_c[not_cur+1][0]:
					c_cur += 2
					not_cur += 1
				else:
					c_cur += 1
					not_cur += 2
			if c_cur >= n or not_cur >= n:
				break
	print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
pairs = []
for i in range(N):
    tmp = input()
    pairs.append([int(a) for a in tmp.split()])

pos_and_vals = []
for i, (from_, to_) in enumerate(pairs):
    pos_and_vals.append(((i, 0), from_))
    pos_and_vals.append(((i, 1), to_))

pos_and_vals_sorted = sorted(pos_and_vals, key=(lambda x: x[1]))
pos_and_vals_sorted_toN = pos_and_vals_sorted[:N]

directions = [[False, False] for _ in range(N)]
for (i, direction), val in pos_and_vals_sorted_toN:
    directions[i][direction] = True

smallest_sum = sum([val for (i, direction), val in pos_and_vals_sorted_toN])
first_direction = pos_and_vals_sorted[0][0][1]
if all([direction == first_direction for (i, direction), val in pos_and_vals_sorted_toN]):
    # if all to or all from
    # let it go
    answer = smallest_sum
elif any([(not direction[0]) and (not direction[1]) for direction in directions]):
    # if x exists and x is unused, then let it go
    answer = smallest_sum
else:
    highest_inner = pos_and_vals_sorted[N-1]
    lowest_outer = pos_and_vals_sorted[N]
    if highest_inner[0][0] != lowest_outer[0][0]:
        # replace and make it unused
        answer = smallest_sum - highest_inner[1] + lowest_outer[1]
    elif all([direction == lowest_outer[0][1]
              for (i, direction), val in pos_and_vals_sorted_toN[:N-1]]):
        # if all except target is all the same direction, then let it go
        answer = smallest_sum - highest_inner[1] + lowest_outer[1]
    else:
        assert N >= 2
        # candidates are only two
        second_highest_inner = pos_and_vals_sorted[N-2]
        second_lowest_outer = pos_and_vals_sorted[N + 1]
        candidate_one = smallest_sum - second_highest_inner[1] + lowest_outer[1]
        candidate_two = smallest_sum - highest_inner[1] + second_lowest_outer[1]
        answer = min(candidate_one, candidate_two)

print(answer)

Submission status: Accepted

Solution code:
import sys
n=input()
pair=[]
sort=[]
for i in range(n):
	a, b=map(int, raw_input().split())
	pair.append([[a, 0], [b, 0]])
	sort.append((a, i, 0))
	sort.append((b, i, 1))
sum=0
sort.sort()
for i in range(n):
	assert pair[sort[i][1]][sort[i][2]][0]==sort[i][0]
	pair[sort[i][1]][sort[i][2]][1]=1
	sum+=sort[i][0]
cnt=[[0, 0], [0, 0]]
for i in range(n):
	cnt[pair[i][0][1]][pair[i][1][1]]+=1
assert cnt[0][0]==cnt[1][1]
if cnt[0][0]>0 or cnt[0][1]==n or cnt[1][0]==n:
	print sum
else:
	min_value=1000000000000000000
	max_value=-1
	for i in range(n):
		if pair[i][0][1]:
			assert pair[i][1][1]==0
			min_value=min(min_value, pair[i][1][0])
			max_value=max(max_value, pair[i][0][0])
		else:
			assert pair[i][1][1]==1
			min_value=min(min_value, pair[i][0][0])
			max_value=max(max_value, pair[i][1][0])
	min_id=-1
	max_id=-1
	for i in range(n):
		if pair[i][0][1]:
			assert pair[i][1][1]==0
			if min_value==pair[i][1][0]:
				min_id=i
			if max_value==pair[i][0][0]:
				max_id=i
		else:
			assert pair[i][1][1]==1
			if min_value==pair[i][0][0]:
				min_id=i
			if max_value==pair[i][1][0]:
				max_id=i
	assert min_value>=max_value
	if min_id!=max_id:
		print sum-max_value+min_value
	else:
		new_min_value=1000000000000000000
		new_max_value=-1
		for i in range(n):
			if i==min_id:
				continue
			if pair[i][0][1]:
				new_min_value=min(new_min_value, pair[i][1][0])
				new_max_value=max(new_max_value, pair[i][0][0])
			else:
				assert pair[i][1][1]==1
				new_min_value=min(new_min_value, pair[i][0][0])
				new_max_value=max(new_max_value, pair[i][1][0])
		print min(sum-max_value+new_min_value, sum-new_max_value+min_value)
		print>>sys.stderr, "\n\n\n"

Submission status: Accepted

Solution code:
from sys import stdin
from heapq import heapify, heappop
from itertools import repeat
def main():
    n = int(stdin.readline())
    dat = map(int, stdin.read().split(), repeat(10, 2 * n))
    q = [(x, i) for i, x in enumerate(dat)]
    q.sort()
    d = [0] * n
    ans = min(sum(dat[::2]), sum(dat[1::2]))
    s = 0
    for i in xrange(n):
        s += q[i][0]
        d[q[i][1]/2] |= 1 << (q[i][1] % 2)
    for i in xrange(n):
        p = s
        c = n - 1
        for j in xrange(2):
            if not (d[i] >> j & 1):
                p += dat[i*2+j]
                while q[c][1] / 2 == i:
                    c -= 1
                p -= q[c][0]
                c -= 1
        if ans > p:
            ans = p
    print ans
main()

Submission status: Accepted

Solution code:
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict, Counter
from bisect import bisect

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

N = read()
A = [0] * N; B = [0] * N
for i in range(N):
  A[i], B[i] = reads()

ans = 10 ** 18
ans = min(ans, sum(A))
ans = min(ans, sum(B))

s = sorted([(A[i], i) for i in range(N)] + [(B[i], i) for i in range(N)])

used = [False] * N
for i in range(N):
  used[s[i][1]] = True
cand = sum(a for a, i in s[:N])
if not all(used):
  ans = min(ans, cand)
else:
  if s[N-1][1] != s[N][1]:
    ans = min(ans, cand - s[N-1][0] + s[N][0])
  else:
    ans = min(ans, cand - s[N-2][0] + s[N][0])
    ans = min(ans, cand - s[N-1][0] + s[N+1][0])
print(ans)

Submission status: Runtime Error

Solution code:
import sys

input=sys.stdin.readline

N=int(input())
A=[-1]*N;B=[-1]*N
for i in range(N):
    A[i],B[i]=map(int,input().split())

ans=min(sum(A),sum(B))

temp=[(A[i],i) for i in range(N)]+[(B[i],i) for i in range(N)]
temp.sort()
data=[0]*N
for i in range(N):
    val,id=temp[i]
    data[id]+=1
S=sum(temp[i][0] for i in range(N))

for i in range(N):
    if data[i]==2:
        test=S
    elif data[i]==1:
        if temp[N-1][1]!=i:
            test=S+max(A[i],B[i])-temp[N-1][0]
        else:
            test=S+max(A[i],B[i])-temp[N-2][0]
    ans=min(test,ans)

print(ans)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
import bisect
n = int(input())
ab = [list(map(int,input().split())) for i in range(n)]
both = []
for i in range(n):
  both.extend(ab[i])
both.sort()
ans = 10**18
sm = sum(both[:n])
for i in range(n):
  ai = bisect.bisect_left(both,ab[i][0])
  bi = bisect.bisect_left(both,ab[i][1])
  if ai < n and bi < n:
    ans = min(ans,sm)
  elif ai < n:
    ans = min(ans,sm-both[n-1]+ab[i][1])
  elif bi < n:
    ans = min(ans,sm-both[n-1]+ab[i][0])
  else:
    ans = min(ans,sm-both[n-1]-both[n-2]+sum(ab[i]))
a,b = list(zip(*ab))
ans = min(ans,sum(a),sum(b))
if ans != sm:
  print(2/0)
else:
  print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
C = [list(map(int,input().split())) for i in range(N)]
C.sort()
ans0 = 0
ans1 = 0
ans2 = 0
AM = []
Am = []
BM = []
Bm = []
for i in range(N):
    ans0 += C[i][0]
    ans1 += C[i][1]
    Min = min(C[i][0],C[i][1])
    Max = max(C[i][0],C[i][1])
    ans2 += Min
    if Min == C[i][0]:
        Am.append(C[i][0])
        BM.append(C[i][1])
    else:
        AM.append(C[i][0])
        Bm.append(C[i][1])
ans3 = sum(sorted(A+B)[:N])
if ans3 == ans2:
    ans3 += min(min(AM)-max(Am),min(BM)-max(Bm))
    
ans = min(ans0,ans1,ans3)
print(ans)

Submission status: Runtime Error

Solution code:
 import sys
import socket

if socket.gethostname() in ['N551J', 'F551C']:
    sys.stdin = open('c1.in')


def read_int_list():
    return list(map(int, input().split()))


def read_int():
    return int(input())


def read_str_list():
    return input().split()


def read_str():
    return input()


def solve():
    n = read_int()
    rows = [read_int_list() for i in range(n)]
    a, b = map(list, zip(*rows))
    res = sum(a)
    res = min(res, sum(b))
    all_values = [(a[i], i, 0) for i in range(n)]
    all_values.extend([(b[i], i, 1) for i in range(n)])
    all_values.sort()
    index_of_value = {v: i for i, v in enumerate(all_values)}
    first_values = [
        set(all_values[:n - 2]),
        set(all_values[:n - 1]),
        set(all_values[:n]),
    ]

    s = [sum([t[0] for t in v]) for v in first_values]

    for i in range(n):
        rest = []
        k = 0
        if index_of_value[(a[i], i, 0)] < n:
            k += 1
        else:
            rest.append(a[i])
        if index_of_value[(b[i], i, 1)] < n:
            k += 1
        else:
            rest.append(b[i])
        t = s[k] + sum(rest)
        res = min(res, t)
    return res


def main():
    res = solve()
    print(res)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
4
1 5
2 6
3 7
4 8

Submission status: Runtime Error

Solution code:
'''
辺のコストをmin(Ax, By)とする代わりに、
辺のコストをAxもしくはByの好きな方にしてよいとしたときの最小値を求める

各頂点vについて、
１．Av, Bvともに選ばれる
２．Avのみ選ばれる
３．Bvのみ選ばれる
４．Av, Bvとも選ばれない

すべてタイプ2のときはsum(A), すべてタイプ3のときはsum(B)
それ以外は、タイプ1 = タイプ4 
2...2 4141..4 3...3 1
と構成すればよい
A, Bを合併したリストから小さい順にN個取る
この時に、最初のN個に同じ頂点由来のAv, Bvが両方含まれていたら上のように構成してしまえばよい
明らかにこれが最小値
含まれていないときは, 最初のn項についてそれぞれ取り除いたときにどうなるかを考える
Aw/Bwを取り除いたとすると, N+1番目の項がBw/AwでなければN+1番目の項を追加
Bw/Awの時はN+2番目の項を追加
（最初のN項が頂点について被りがないという条件から、これにより必ずあるvについてAv, Bv両方が含まれることになる
'''

n = int(input())
x = []
for i in range(n):
    ai, bi = map(int, input().split())
    x += [[i, ai, 0], [i, bi, 1]]
s1 = sum([x[2 * i][1] for i in range(n)])
s2 = sum([x[2 + i + 1][1] for i in range(n)])


x.sort(key = lambda x: x[1])
s3 = sum([x[i][1] for i in range(n)])
if len(set([x[i][0] for i in range(n)])) != n:
    print(min(s1, s2, s3))
else:
    if x[n - 1][0] == x[n][0]:
        s4 = min(s3 - x[n - 1][1] + x[n + 1][1], s3 - x[n - 2][1] + x[n][1])
    else:
        s4 = s3 - x[n - 1][1] + x[n][1]
    print(min(s1, s2, s4))

Submission status: Runtime Error

Solution code:
n = int(input())
c = []
not_c = []
chosen = set()
ans = 0
for i in range(n):
	a, b = map(int, input().split())
	not_c.append([max(a, b), i])
	c.append([min(a, b), i])
	ans += min(a, b)
	if a < b:
		chosen.add("a")
	elif a > b:
		chosen.add("b")

if len(chosen) < 2:
	print(ans)
else:
	c = sorted(c, reverse=True)
	not_c = sorted(not_c)
	#print(c, not_c)
	#used_c = [False] * n
	#used_n = [False] * n

	if c[0][1] != not_c[0][1]:
		ans = ans - c[0][0] + not_c[0][0]
		c_cur = 1
		not_cur = 1
	else:
		ans = min(ans - c[1][0] + not_c[0][0], ans - c[0][0] + not_c[1][0])
		if ans - c[1][0] + not_c[0][0] <= ans - c[0][0] + not_c[1][0]:
			c_cur = 2
			not_cur = 1
		else:
			c_cur = 1
			not_c = 2
	if c_cur < n and not_cur < n:
		while c[c_cur][0] > not_c[not_cur][0]:
			if c[c_cur][1] != not_c[not_cur][1]:
				ans = ans - c[c_cur][0] + not_c[not_cur][0]
				c_cur += 1
				not_cur += 1
			elif c_cur == n - 1 or not_cur == n - 1:
				break
			else:
				ans = min(ans - c[c_cur+1][0] + not_c[not_cur][0], ans - c[c_cur][0] + not_c[not_cur+1][0])
				if ans - c[c_cur+1][0] + not_c[not_cur][0] <= ans - c[c_cur][0] + not_c[not_cur+1][0]:
					c_cur += 2
					not_cur += 1
				else:
					c_cur += 1
					not_cur += 2
			if c_cur >= n or not_cur >= n:
				break
	print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
c = []
not_c = []
chosen = set()
ans = 0
for i in range(n):
	a, b = map(int, input().split())
	not_c.append([max(a, b), i])
	c.append([min(a, b), i])
	ans += min(a, b)
	if a < b:
		chosen.add("a")
	elif a > b:
		chosen.add("b")

if len(chosen) < 2:
	print(ans)
else:
	c = sorted(c, reverse=True)
	not_c = sorted(not_c)
	#print(c, not_c)
	#used_c = [False] * n
	#used_n = [False] * n

	if c[0][1] != not_c[0][1]:
		ans = ans - c[0][0] + not_c[0][0]
		c_cur = 1
		not_cur = 1
	else:
		ans = min(ans - c[1][0] + not_c[0][0], ans - c[0][0] + not_c[1][0])
		if ans - c[1][0] + not_c[0][0] <= ans - c[0][0] + not_c[1][0]:
			c_cur = 2
			not_cur = 1
		else:
			c_cur = 1
			not_c = 2
	if c_cur < n and not_cur < n:
		while c[c_cur][0] > not_c[not_cur][0]:
			if c[c_cur][1] != not_c[not_cur][1]:
				ans = ans - c[c_cur][0] + not_c[not_cur][0]
				c_cur += 1
				not_cur += 1
			elif c_cur == n - 1 or not_cur == n - 1:
				break
			else:
				ans = min(ans - c[c_cur+1][0] + not_c[not_cur][0], ans - c[c_cur][0] + not_c[not_cur+1][0])
				if ans - c[c_cur+1][0] + not_c[not_cur][0] <= ans - c[c_cur][0] + not_c[not_cur+1][0]:
					c_cur += 2
					not_cur += 1
				else:
					c_cur += 1
					not_c += 2
			if c_cur >= n or not_cur >= n:
				break
	print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
c = []
not_c = []
chosen = set()
ans = 0
for i in range(n):
	a, b = map(int, input().split())
	not_c.append([max(a, b), i])
	c.append([min(a, b), i])
	ans += min(a, b)
	if a < b:
		chosen.add("a")
	elif a > b:
		chosen.add("b")

if len(chosen) < 2:
	print(ans)
else:
	c = sorted(c, reverse=True)
	not_c = sorted(not_c)
	#print(c, not_c)
	#used_c = [False] * n
	#used_n = [False] * n

	if c[0][1] != not_c[0][1]:
		ans = ans - c[0][0] + not_c[0][0]
		c_cur = 1
		not_cur = 1
	else:
		ans = min(ans - c[1][0] + not_c[0][0], ans - c[0][0] + not_c[1][0])
		if ans - c[1][0] + not_c[0][0] <= ans - c[0][0] + not_c[1][0]:
			c_cur = 2
			not_cur = 1
		else:
			c_cur = 1
			not_c = 2
	if c_cur < n and not_cur < n:
		while c[c_cur][0] > not_c[not_cur][0]:
			if c[c_cur][1] != not_c[not_cur][1]:
				ans = ans - c[c_cur][0] + not_c[not_cur][0]
				c_cur += 1
				not_cur += 1
			else:
				ans = min(ans - c[c_cur+1][0] + not_c[not_cur][0], ans - c[c_cur][0] + not_c[not_cur+1][0])
				if ans - c[c_cur+1][0] + not_c[not_cur][0] <= ans - c[c_cur][0] + not_c[not_cur+1][0]:
					c_cur += 2
					not_cur += 1
				else:
					c_cur += 1
					not_c += 2
			if c_cur >= n or not_cur >= n:
				break
	print(ans)

Submission status: Runtime Error

Solution code:
import sys
from collections import deque
import copy

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)


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 = int(input_raw[0])
    A_list = []
    B_list = []
    for i in range(N):
        input_raw = read_func().strip().split()
        [A, B] = [long(input_raw[0]), long(input_raw[1])]
        A_list.append((A, i))
        B_list.append((B, i))

    A_list.sort(reverse = True)
    B_list.sort()
    uf = UnionFind(N)
    score = 0L
    is_used = [False for i in range(N)]
    visited = set([])
    for i in range(N):
        for j in range(N):
            if A_list[j][0] <= B_list[i][0]:
                break
            if is_used[A_list[j][1]] == True:
                continue
            
            if uf.same_check(A_list[j][1], B_list[i][1]) == False:
                uf.union(A_list[j][1], B_list[i][1])
                is_used[A_list[j][1]] = True
                score += B_list[i][0]
                break

    for i in range(N):
        if is_used[A_list[i][1]] == False:
            score += A_list[i][0]
    print score


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#include<bits/stdc++.h>
#include<tuple>
using namespace std;
#define ll long long
#define INF 1e+9
#define geta 1000000
using P = pair<int,int>;
int main(){
  priority_queue<P, vector<P> greater<P> > q;
  priority_queue<P> dq;
  int used[100001]={};
  int n, cnt = 0;
  int acnt = 0, bcnt = 0, scnt = 0;
  ll ans = 0;
  cin >> n;
  int a,b;
  for(int i=0;i<n;i++){
    cin >> a >> b;
    q.push(P(a,i));
    q.push(P(b,i + geta));
  }
  while(cnt < n){
    int d,p;
    tie(d,p)=q.top();q.pop();
    if(p > geta){
      if(used[p-geta] == 1){
        scnt++;
        used[p-geta] = 2;
      }
      bcnt++;
      cnt++;
      used[p-geta] = 1;
      ans += d;
    }else{
      if(used[p] == 1){ 
        scnt++;
        used[p] = 2;
      }
      acnt++;
      cnt++;
      used[p] = 1;
      ans += d;
    }
    dq.push(P(d,p));
  }
  while(scnt > max(acnt,bcnt)- min(acnt,bcnt)){
    int d,p;
    tie(d,p)=dq.top();dq.pop();
    if(p>geta){
      if(used[p-geta] == 2) continue;
      used[p-geta]--;
      ans -= d;
    }else{
      if(used[p] == 2) continue;
      used[p]--;
      ans -= d;
    }
    tie(d,p)=q.top();q.pop();
    if(p > geta){
      if(used[p-geta] == 1){
        scnt++;
        used[p-geta] = 2;
      }
      bcnt++;
      cnt++;
      used[p-geta] = 1;
      ans += d;
    }else{
      if(used[p] == 1){ 
        scnt++;
        used[p] = 2;
      }
      acnt++;
      cnt++;
      used[p] = 1;
      ans += d;
    }
  }
  cout << ans << endl;
}

/* 
  全通りやる -> (n-1)!回ずつ同じ位置で取り除く
  n-1回コスト1で、n-1回コストsumで抜く

*/

Submission status: Runtime Error

Solution code:
n = int(input())
c = []
not_c = []
chosen = set()
ans = 0
for i in range(n):
	a, b = map(int, input().split())
	not_c.append([max(a, b), i])
	c.append([min(a, b), i])
	ans += min(a, b)
	if a < b:
		chosen.add("a")
	elif a > b:
		chosen.add("b")

if len(chosen) < 2:
	print(ans)
else:
	c = sorted(c, reverse=True)
	not_c = sorted(not_c)
	#print(c, not_c)
	#used_c = [False] * n
	#used_n = [False] * n

	if c[0][1] != not_c[0][1]:
		ans = ans - c[0][0] + not_c[0][0]
		c_cur = 1
		not_cur = 1
	else:
		ans = min(ans - c[1][0] + not_c[0][0], ans - c[0][0] + not_c[1][0])
		if ans - c[1][0] + not_c[0][0] <= ans - c[0][0] + not_c[1][0]:
			c_cur = 2
			not_cur = 1
		else:
			c_cur = 1
			not_c = 2
	while c[c_cur][0] > not_c[not_cur][0]:
		if c[c_cur][1] != not_c[not_cur][1]:
			ans = ans - c[c_cur][0] + not_c[not_cur][0]
			c_cur += 1
			not_cur += 1
		else:
			ans = min(ans - c[c_cur+1][0] + not_c[not_cur][0], ans - c[c_cur][0] + not_c[not_cur+1][0])
			if ans - c[c_cur+1][0] + not_c[not_cur][0] <= ans - c[c_cur][0] + not_c[not_cur+1][0]:
				c_cur += 2
				not_cur += 1
			else:
				c_cur += 1
				not_c += 2
		if c_cur >= n or not_cur >= n:
			break
	print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
c = []
not_c = []
chosen = set()
ans = 0
for i in range(n):
	a, b = map(int, input().split())
	not_c.append([max(a, b), i])
	c.append([min(a, b), i])
	ans += min(a, b)
	if a < b:
		chosen.add("a")
	elif a > b:
		chosen.add("b")

if len(chosen) < 2:
	print(ans)
else:
	c = sorted(c, reverse=True)
	not_c = sorted(not_c)
	#print(c, not_c)
	#used_c = [False] * n
	#used_n = [False] * n

	if c[0][1] != not_c[0][1]:
		ans = ans - c[0][0] + not_c[0][0]
		c_cur = 1
		not_cur = 1
	else:
		ans = min(ans - c[1][0] + not_c[0][0], ans - c[0][0] + not_c[1][0])
		if ans - c[1][0] + not_c[0][0] <= ans - c[0][0] + not_c[1][0]:
			c_cur = 2
			not_cur = 1
		else:
			c_cur = 1
			not_c = 2
	while c[c_cur][0] > not_c[not_cur][0]:
		if c[c_cur][1] != not_c[not_cur][1]:
			ans = ans - c[c_cur][0] + not_c[not_cur][0]
			c_cur += 1
			not_cur += 1
		else:
			ans = min(ans - c[c_cur+1][0] + not_c[not_cur][0], ans - c[c_cur][0] + not_c[not_cur+1][0])
			if ans - c[c_cur+1][0] + not_c[not_cur][0] <= ans - c[c_cur][0] + not_c[not_cur+1][0]:
				c_cur += 2
				not_cur += 1
			else:
				c_cur += 1
				not_c += 2
	print(ans)

Submission status: Runtime Error

Solution code:
#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#

"""
AGC028 C
"""

import itertools

n = int(input())
abli = [tuple(map(int, input().split())) for i in range(n)]

leftsum = sum(map(lambda x: x[0], abli))
rightsum = sum(map(lambda x: x[1], abli))

maxminel = max(enumerate(abli), key=lambda x: 10**10*min(x[1])+max(x[1]))
maxminmax = max(abli[maxminel[0]])
del abli[maxminel[0]]
flattenli = list(itertools.chain.from_iterable(abli))
flattenli.sort()
tmpans = sum(flattenli[:n])
if flattenli[n] > maxminmax:
    tmpans = tmpans-flattenli[n]+maxminmax


print(min(leftsum, rightsum, tmpans))

Submission status: Runtime Error

Solution code:
import numpy as np
N = int(input())
A = []
B = []
for _ in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
A = np.array(A)
B = np.array(B)
A.sort()
B = B[np.argsort(A)]
ans1 = 0
for i in range(N-1):
    ans += min(A[i+1], B[i])
ans1 += min(A[0], B[N-1])
B.sort()
A = A[np.argsort(B)]
ans2 = 0
for i in range(N-1):
    ans += min(A[i+1], B[i])
ans2 += min(A[0], B[N-1])
print(min(ans1, ans2))

Submission status: Runtime Error

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


AA = sorted(X, key=lambda x:x[1])
BB = sorted(X, key=lambda x:x[2])

n = len(A)
a_l = 0
a_r = n - 1
b_l = 0
b_r = n - 1
ans = 0
l_list = [[AA[i][0], AA[i][1], [AA[i][0]]] for i in range(n)]
r_list = [[BB[i][0], BB[i][2], [BB[i][0]]] for i in range(n)]

K = [0] * n
for i in range(n):
    K[r_list[i][0]] = i



m = n-1
for i in range(len(A)):
    j1 = m
    while j1 in l_list[0][2]:
        j1 -= 1
    d1 = abs(l_list[0][1] - r_list[j1][1])
    
    j2 = 0
    while j2 in l_list[m][2]:
        j2 += 1
    d2 = abs(l_list[m][1] - r_list[j2][1])
    
    if d1 > d2:
        
        for ii in range(len(l_list)):
            if l_list[ii][0] == r_list[j1][0]:
                l_list[ii][2] += l_list[0][2]
            
        del l_list[0]
        del r_list[j1]
        ans += d1
    else:
        for ii in range(len(l_list)):
            if l_list[ii][0] == r_list[j2][0]:
                l_list[ii][2] = l_list[ii][2] + l_list[m][2]

        del l_list[m]
        del r_list[j2]
        ans += d2
        
    m -= 1
print ((sum(A) + sum(B) - ans)//2)