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: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from sys import stdin
import numpy as np

s_in = lambda: stdin.readline()[:-1] # s = s_in()
d_in = lambda: int(stdin.readline()) # N = d_in()
ds_in = lambda: list(map(int, stdin.readline().split())) # List = ds_in()

N = d_in()

Weights = []
for i in range(N):
    w = ds_in()
    Weights.append([w[0], i, 0])
    Weights.append([w[1], i, 1])

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

Not_used = []
L_Used = []
R_Used = []
for i in range(0, N):
    if Weights[i][2] == 0:
        L_Used.append(Weights[i][1])
    else:
        R_Used.append(Weights[i][1])
    Not_used.append(Weights[N+i][1])

N_used = N - len(set(Not_used))

ans = np.array(Weights[:N]).sum(axis=0)[0]
if len(L_Used) >= len(R_Used):
    if len(L_Used) <= N_used or len(L_Used) == 0 or len(R_Used) == 0:
        print(ans)
    else:
        if Weights[N-1][2] != Weights[N][2]:
            print(ans + Weights[N][0] - Weights[N-1][0])
        else:
            print(ans + min(Weights[N][0] - Weights[N-2][0],
                Weights[N+1][0] - Weights[N-1][0]))
else:
    if len(R_Used) <= N_used or len(L_Used) == 0 or len(R_Used) == 0:
        print(ans)
    else:
        if Weights[N-1][2] != Weights[N][2]:
            print(ans + Weights[N][0] - Weights[N-1][0])
        else:
            print(ans + min(Weights[N][0] - Weights[N-2][0],
                Weights[N+1][0] - Weights[N-1][0]))

Submission status: Wrong Answer

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: Wrong Answer

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

ans = min(sum(A_), sum(B_))

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

print S
exit()

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

print ans

Submission status: Wrong Answer

Solution code:
import itertools

def naive(N, A, B):
  ans = sum(A)+sum(B)
  ap = []
  for p in itertools.permutations(range(N)):
    a = 0
    for i in range(N):
      a += min(A[p[i-1]], B[p[i]])
    if a<ans:
      ans = a
      ap = p
  print ap
  return ans

def solve(N, A, B):
  T = []
  for i in range(N):
    T += [(A[i], 0, i), (B[i], 1, i)]
  T.sort()
  c = 0
  ans = 0
  S = 0
  for i in range(N):
    ans += T[i][0]
    c += T[i][1]
    S += T[i][2]+1
  if c!=0 and c!=N and S==sum(range(1,N+1)):
    if T[N-1][2]!=T[N][2] or (c==1 and T[N-1][1]==1 and T[N][1]==0) or (c==N-1 and T[N-1][1]==0 and T[N][1]==1):
      ans -= T[N-1][0]
      ans += T[N][0]
    else:
      ans -= T[N-1][0]
      ans += T[N+1][0]
  return ans

N = input()
A = [0]*N
B = [0]*N
for i in range(N):
  A[i],B[i] = map(int, raw_input().split())
#print naive(N, A, B)
print solve(N, A, B)

Submission status: Wrong Answer

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

ans = min(sum(A_), sum(B_))

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

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

print ans

Submission status: Wrong Answer

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

a.sort(key=lambda x: x[0])
b.sort(key=lambda x: x[0], reverse=True)

ans = 0

for i in range(n):
    ans += min(a[i][0], b[i][0])

memo = [b[i][0] for i in range(n)]

i = 0
flag = 0
while i < n-1:
    if a[i][1] == b[i][1]:
        ans += -min(a[i][0], b[i][0]) - min(a[i+1][0], b[i+1][0]) + min(a[i][0], b[i+1][0]) + min(a[i+1][0], b[i][0])
        memo[i+1] = b[i][0]
        memo[i] = b[i+1][0]
        i += 1
        if i == n - 1:
            flag = 1
    i += 1
if flag == 0 and a[n-1][1] == b[n-1][1]:
    ans += -min(a[n-1][0], b[n-1][0]) - min(a[n-2][0], memo[n-2]) + min(a[n-1][0], memo[n-2]) + min(a[n-2][0], b[n-1][0])

print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

def naive(N, A, B):
  ans = sum(A)+sum(B)
  ap = []
  for p in itertools.permutations(range(N)):
    a = 0
    for i in range(N):
      a += min(A[p[i-1]], B[p[i]])
    if a<ans:
      ans = a
      ap = p
  print ap
  return ans

def solve(N, A, B):
  T = []
  for i in range(N):
    T += [(A[i], 0, i), (B[i], 1, i)]
  T.sort()
  c = 0
  ans = 0
  S = 0
  for i in range(N):
    ans += T[i][0]
    c += T[i][1]
    S += T[i][2]+1
  if c!=0 and c!=N and S==sum(range(1,N+1)):
    if T[N-1][2]!=T[N][2]:
      ans -= T[N-1][0]
      ans += T[N][0]
    else:
      ans -= T[N-1][0]
      ans += T[N+1][0]
  return ans

N = input()
A = [0]*N
B = [0]*N
for i in range(N):
  A[i],B[i] = map(int, raw_input().split())
#print naive(N, A, B)
print solve(N, A, B)

Submission status: Wrong Answer

Solution code:
N=int(raw_input())

edge=[]
for i in range(N):
    A,B=map(int,raw_input().split())
    edge.append(A)
    edge.append(B)
    
edge.sort()
ans=0
if N%2==0:    
    for i in range(N):
        ans+=edge[i]
else:
    for i in range((N+1)/2):
        ans+=edge[i]
    for i in range((N+1)/2+1,N+1):
        ans+=edge[i]

print ans

Submission status: Wrong Answer

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

a.sort(key=lambda x: x[0])
b.sort(key=lambda x: x[0], reverse=True)

ans = 0

for i in range(n):
    ans += min(a[i][0], b[i][0])

memo = [b[i][0] for i in range(n)]

i = 0
flag = 0
while i < n-1:
    if a[i][1] == b[i][1]:
        ans += -min(a[i][0], b[i][0]) - min(a[i+1][0], b[i+1][0]) + min(a[i][0], b[i+1][0]) + min(a[i+1][0], b[i][0])
        memo[i+1] = b[i][0]
        i += 1
        if i == n - 1:
            flag = 1
    i += 1
if flag == 0 and a[n-1][1] == b[n-1][1]:
    ans += -min(a[n-1][0], b[n-1][0]) - min(a[n-2][0], memo[n-2]) + min(a[n-1][0], memo[n-2]) + min(a[n-2][0], b[n-1][0])

print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

def naive(N, A, B):
  ans = sum(A)+sum(B)
  ap = []
  for p in itertools.permutations(range(N)):
    a = 0
    for i in range(N):
      a += min(A[p[i-1]], B[p[i]])
    if a<ans:
      ans = a
      ap = p
  print ap
  return ans

def solve(N, A, B):
  T = []
  for i in range(N):
    T += [(A[i], 0, i), (B[i], 1, i)]
  T.sort()
  c = 0
  ans = 0
  S = 0
  for i in range(N):
    ans += T[i][0]
    c += T[i][1]
    S += T[i][2]+1
  if c!=0 and c!=N and S==sum(range(1,N+1)):
    ans -= T[N-1][0]
    ans += T[N][0]
  return ans

N = input()
A = [0]*N
B = [0]*N
for i in range(N):
  A[i],B[i] = map(int, raw_input().split())
#print naive(N, A, B)
print solve(N, A, B)

Submission status: Wrong Answer

Solution code:
N=int(raw_input())

edge=[]
for i in range(N):
    A,B=map(int,raw_input().split())
    edge.append(A)
    edge.append(B)
    
edge.sort()
ans=0
if N%2==0:    
    for i in range(N):
        ans+=edge[i]
else:
    for i in range((N+1)/2+1):
        ans+=edge[i]
    for i in range((N+1)/2+2,N+1):
        ans+=edge[i]

print ans

Submission status: Wrong Answer

Solution code:
import itertools

def naive(N, A, B):
  ans = sum(A)+sum(B)
  ap = []
  for p in itertools.permutations(range(N)):
    a = 0
    for i in range(N):
      a += min(A[p[i-1]], B[p[i]])
    if a<ans:
      ans = a
      ap = p
  print ap
  return ans

def solve(N, A, B):
  T = []
  for i in range(N):
    T += [(A[i], 0), (B[i], 1)]
  T.sort()
  c = 0
  ans = 0
  for i in range(N):
    ans += T[i][0]
    c += T[i][1]
  if c!=0 and c!=N:
    ans -= T[N-1][0]
    ans += T[N][0]
  return ans

N = input()
A = [0]*N
B = [0]*N
for i in range(N):
  A[i],B[i] = map(int, raw_input().split())
#print naive(N, A, B)
print solve(N, A, B)

Submission status: Wrong Answer

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

a.sort(key=lambda x: x[0])
b.sort(key=lambda x: x[0], reverse=True)

ans = 0

for i in range(n):
    ans += min(a[i][0], b[i][0])

memo = [b[i][1] for i in range(n)]

i = 0
flag = 0
while i < n-1:
    if a[i][1] == b[i][1]:
        ans += -min(a[i][0], b[i][0]) - min(a[i+1][0], b[i+1][0]) + min(a[i][0], b[i+1][0]) + min(a[i+1][0], b[i][0])
        memo[i+1] = b[i][0]
        i += 1
        if i == n - 1:
            flag = 1
    i += 1
if flag == 0 and a[n-1][1] == b[n-1][1]:
    ans += -min(a[n-1][0], b[n-1][0]) - min(a[n-2][0], memo[n-2]) + min(a[n-1][0], memo[n-2]) + min(a[n-2][0], b[n-1][0])

print(ans)

Submission status: Wrong Answer

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)
	if c[0][1] != not_c[0][1]:
		print(ans - c[0][0] + not_c[0][0])
	else:
		print(min(ans - c[1][0] + not_c[0][0], ans - c[0][0] + not_c[1][0]))

Submission status: Wrong Answer

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 = []
for i in range(N):
    A, B = map(int, raw_input().split())
    ls.append((A, 'A', i))
    ls.append((B, 'B', i))

ls.sort()

V = ls[:N]
V2 = ls[N:]

fA = False
fB = False
flag = False
used = [False] * N
ans = 0
for p in V:
    ans += p[0]
    if p[1] == 'A':
        fA = True
    else:
        fB = True
    if used[p[2]]:
        flag = True
    else:
        used[p[2]] = True

if not fA or not fB or flag:
    print ans
    exit()

minA = INF
maxA = 0
minB = INF
maxB = 0

for p in V:
    if p[1] == 'A':
        maxA = max(maxA, p[0])
    else:
        maxB = max(maxB, p[0])
for p in V2:
    if p[1] == 'A':
        minA = min(minA, p[0])
    else:
        minB = min(minB, p[0])

print ans + min(minB - maxA, minA - maxB)

Submission status: Wrong Answer

Solution code:
N=int(raw_input())

edge=[]
for i in range(N):
    A,B=map(int,raw_input().split())
    edge.append(A)
    edge.append(B)
    
edge.sort()
ans=0
if N%2==0:    
    for i in range(N):
        ans+=edge[i]
else:
    for i in range(N-1):
        ans+=edge[i]
    ans+=edge[N]

print ans

Submission status: Wrong Answer

Solution code:
N=int(raw_input())

edge=[]
for i in range(N):
    A,B=map(int,raw_input().split())
    edge.append(A)
    edge.append(B)
    
edge.sort()
ans=0
for i in range(N):
    ans+=edge[i]

if N%2==0:    
    print ans
else:
    print -1

Submission status: Wrong Answer

Solution code:
N=int(raw_input())

edge=[]
for i in range(N):
    A,B=map(int,raw_input().split())
    edge.append(A)
    edge.append(B)
    
edge.sort()
ans=0
for i in range(N):
    ans+=edge[i]
    
print ans

Submission status: Wrong Answer

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]))
del abli[maxminel[0]]
flattenli = list(itertools.chain.from_iterable(abli))
flattenli.sort()
tmpans = sum(flattenli[:n])

print(min(leftsum, rightsum, tmpans))

Submission status: Wrong Answer

Solution code:
import sys


n=int(sys.stdin.readline())
A=[list(map(int,sys.stdin.readline().split())) for i in range(n)]
A.sort()
A.sort(key=lambda x:x[1])

LIST=[]

for i in range(n):
    LIST.append((A[i][0],i,0))
    LIST.append((A[i][1],i,1))
LIST.sort()

from collections import deque

LIST=deque(LIST)

ANS=0
for ro in range(n):
    ANS+=LIST[0][0]
    for j in range(len(LIST)-1,-1,-1):
        if LIST[j][1]!=LIST[0][1] and LIST[j][2]!=LIST[0][2]:
            #print(LIST,LIST[0],LIST[j])
            del LIST[j]
            LIST.popleft()
            break


print(ANS)

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush, heapify

n = int(input())
aaa = [tuple(map(int, input().split())) for _ in range(n)]
aaa.sort(key=sum, reverse=True)

q = [(abs(aaa[0][0] - aaa[1][1]), min(aaa[0][0], aaa[1][1]), aaa[0][0], aaa[1][1]),
     (abs(aaa[1][0] - aaa[0][1]), min(aaa[1][0], aaa[0][1]), aaa[1][0], aaa[0][1])]
heapify(q)

ans = q[0][1] + q[1][1]

for a, b in aaa[2:]:
    d, c, pa, pb = heappop(q)
    heappush(q, (abs(pa - b), min(pa, b), pa, b))
    heappush(q, (abs(a - pb), min(a, pb), a, pb))
    ans -= c
    ans += min(pa, b)
    ans += min(a, pb)

print(ans)

Submission status: Wrong Answer

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: min(x[1]))
del abli[maxminel[0]]
flattenli = list(itertools.chain.from_iterable(abli))
flattenli.sort()
tmpans = sum(flattenli[:n])

print(min(leftsum, rightsum, tmpans))

Submission status: Wrong Answer

Solution code:
import sys
import copy

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

LIST=[]

for i in range(n):
    LIST.append((A[i][0],i,0))
    LIST.append((A[i][1],i,1))
LIST.sort()

from collections import deque

LIST=deque(LIST)

ANS=0
for ro in range(n):
    ANS+=LIST[0][0]
    for j in range(len(LIST)-1,-1,-1):
        if LIST[j][1]!=LIST[0][1] and LIST[j][2]!=LIST[0][2]:
            #print(LIST,LIST[0],LIST[j])
            del LIST[j]
            LIST.popleft()
            break

    #print(LIST)

print(ANS)

Submission status: Wrong Answer

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)
B = B[np.argsort(A)]
A.sort()
ans1 = 0
for i in range(N-1):
    ans1 += min(A[i+1], B[i])
ans1 += min(A[0], B[N-1])
A = A[np.argsort(B)]
B.sort()
ans2 = 0
for i in range(N-1):
    ans2 += min(A[i], B[i+1])
ans2 += min(A[N-1], B[0])
print(min(ans1, ans2))

Submission status: Wrong Answer

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):
    ans1 += 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):
    ans2 += min(A[i+1], B[i])
ans2 += min(A[0], B[N-1])
print(min(ans1, ans2))

Submission status: Wrong Answer

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)]
ans = 0
for i in range(N-1):
    ans += min(A[i+1], B[i])
ans += min(A[0], B[N-1])
print(ans)

Submission status: Wrong Answer

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


li = sorted(li,key = lambda x:(x[1],-x[0]))
li.reverse()

li2 = sorted(li,key = lambda x:(x[0],-x[1]))
li2.reverse()


li3 = sorted(li,key = lambda x:(x[1],x[0]))
li3.reverse()

li4 = sorted(li,key = lambda x:(x[0],x[1]))
li4.reverse()

li5 = sorted(li,key = lambda x:(-x[1],-x[0]))
li5.reverse()

li6 = sorted(li,key = lambda x:(-x[0],-x[1]))
li6.reverse()


li7 = sorted(li,key = lambda x:(-x[1],x[0]))
li7.reverse()

li8 = sorted(li,key = lambda x:(-x[0],x[1]))
li8.reverse()



length = 0
length2 = 0
length3 = 0
length4 = 0
length5 = 0
length6 = 0
length7 = 0
length8 = 0

for i in range(len(li)-1):
    length += min(li[i][0],li[i+1][1])

length += min(li[-1][0],li[0][1])

for i in range(len(li)-1):
    length2 += min(li2[i][0],li2[i+1][1])

length2 += min(li2[-1][0],li2[0][1])

for i in range(len(li)-1):
    length3 += min(li3[i][0],li3[i+1][1])

length3 += min(li3[-1][0],li3[0][1])
for i in range(len(li)-1):
    length4 += min(li4[i][0],li4[i+1][1])

length4 += min(li4[-1][0],li4[0][1])

for i in range(len(li)-1):
    length5 += min(li5[i][0],li5[i+1][1])

length5 += min(li5[-1][0],li5[0][1])

for i in range(len(li)-1):
    length6 += min(li6[i][0],li6[i+1][1])

length6 += min(li6[-1][0],li6[0][1])
for i in range(len(li)-1):
    length7 += min(li7[i][0],li7[i+1][1])

length7 += min(li7[-1][0],li7[0][1])
for i in range(len(li)-1):
    length8 += min(li8[i][0],li8[i+1][1])

length8 += min(li8[-1][0],li8[0][1])

hikaku = [length,length2,length3,length4,length5,length6,length7,length8]

print(min(hikaku))

Submission status: Wrong Answer

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


li = sorted(li,key = lambda x:(x[1],x[0]))
li.reverse()

li2 = li = sorted(li,key = lambda x:(x[0],x[1]))
li2.reverse()


length = 0
length2 = 0

for i in range(len(li)-1):
    length += min(li[i][0],li[i+1][1])

length += min(li[-1][0],li[0][1])

for i in range(len(li)-1):
    length2 += min(li2[i][0],li2[i+1][1])

length2 += min(li2[-1][0],li2[0][1])


print(min(length,length2))

Submission status: Wrong Answer

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]
                p -= q[c][0]
                c -= 1
        if ans > p:
            ans = p
    print ans
main()

Submission status: Wrong Answer

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


li = sorted(li,key = lambda x:(x[1],-x[0]))
li.reverse()

li2 = li = sorted(li,key = lambda x:(x[0],-x[1]))
li2.reverse()


length = 0
length2 = 0

for i in range(len(li)-1):
    length += min(li[i][0],li[i+1][1])

length += min(li[-1][0],li[0][1])

for i in range(len(li)-1):
    length2 += min(li2[i][0],li2[i+1][1])

length2 += min(li2[-1][0],li2[0][1])


print(min(length,length2))

Submission status: Wrong Answer

Solution code:
# -*- encoding: utf-8 -*-
SCORE_NONE = -1

class Life(object):
      """个体类"""
      def __init__(self, aGene = None):
            self.gene = aGene
            self.score = SCORE_NONE

import random

class GA(object):
      """遗传算法类"""
      def __init__(self, aCrossRate, aMutationRage, aLifeCount, aGeneLenght, aMatchFun = lambda life : 1):
            self.croessRate = aCrossRate
            self.mutationRate = aMutationRage
            self.lifeCount = aLifeCount
            self.geneLenght = aGeneLenght
            self.matchFun = aMatchFun                 # 适配函数
            self.lives = []                           # 种群
            self.best = None                          # 保存这一代中最好的个体
            self.generation = 1
            self.crossCount = 0
            self.mutationCount = 0
            self.bounds = 0.0                         # 适配值之和，用于选择是计算概率

            self.initPopulation()


      def initPopulation(self):
            """初始化种群"""
            self.lives = []
            for i in range(self.lifeCount):
                  gene = [ x for x in range(self.geneLenght) ] 
                  random.shuffle(gene)
                  life = Life(gene)
                  self.lives.append(life)


      def judge(self):
            """评估，计算每一个个体的适配值"""
            self.bounds = 0.0
            self.best = self.lives[0]
            for life in self.lives:
                  life.score = self.matchFun(life)
                  self.bounds += life.score
                  if self.best.score < life.score:
                        self.best = life


      def cross(self, parent1, parent2):
            """交叉"""
            index1 = random.randint(0, self.geneLenght - 1)
            index2 = random.randint(index1, self.geneLenght - 1)
            tempGene = parent2.gene[index1:index2]   # 交叉的基因片段
            newGene = []
            p1len = 0
            for g in parent1.gene:
                  if p1len == index1:
                        newGene.extend(tempGene)     # 插入基因片段
                        p1len += 1
                  if g not in tempGene:
                        newGene.append(g)
                        p1len += 1
            self.crossCount += 1
            return newGene


      def  mutation(self, gene):
            """突变"""
            index1 = random.randint(0, self.geneLenght - 1)
            index2 = random.randint(0, self.geneLenght - 1)

            newGene = gene[:]       # 产生一个新的基因序列，以免变异的时候影响父种群
            newGene[index1], newGene[index2] = newGene[index2], newGene[index1]
            self.mutationCount += 1
            return newGene


      def getOne(self):
            """选择一个个体"""
            r = random.uniform(0, self.bounds)
            for life in self.lives:
                  r -= life.score
                  if r <= 0:
                        return life

            raise Exception("选择错误", self.bounds)


      def newChild(self):
            """产生新后的"""
            parent1 = self.getOne()
            rate = random.random()

            # 按概率交叉
            if rate < self.croessRate:
                  # 交叉
                  parent2 = self.getOne()
                  gene = self.cross(parent1, parent2)
            else:
                  gene = parent1.gene

            # 按概率突变
            rate = random.random()
            if rate < self.mutationRate:
                  gene = self.mutation(gene)

            return Life(gene)


      def next(self):
            """产生下一代"""
            self.judge()
            newLives = []
            newLives.append(self.best)            #把最好的个体加入下一代
            while len(newLives) < self.lifeCount:
                  newLives.append(self.newChild())
            self.lives = newLives
            self.generation += 1
		

import math

class TSP(object):
      def __init__(self, aLifeCount = 100,):
            self.initCitys()
            self.lifeCount = aLifeCount
            self.ga = GA(aCrossRate = 0.7, 
                  aMutationRage = 0.02, 
                  aLifeCount = self.lifeCount, 
                  aGeneLenght = len(self.citys), 
                  aMatchFun = self.matchFun())


      def initCitys(self):
            self.citys = []
            n=int(input())
            for i in range(0,n):
                a,b=map(int,input().split())
                self.citys.append((a,b))
            
      def distance(self, order):
            distance = 0
            for i in range(-1, len(self.citys) - 1):
                  index1, index2 = order[i], order[i + 1]
                  city1, city2 = self.citys[index1], self.citys[index2]
                  distance+=min(city1[0],city2[1])

                  """
                  R = 6371.004
                  Pi = math.pi 
                  LatA = city1[1]
                  LatB = city2[1]
                  MLonA = city1[0]
                  MLonB = city2[0]
                  C = math.sin(LatA*Pi / 180) * math.sin(LatB * Pi / 180) + math.cos(LatA * Pi / 180) * math.cos(LatB * Pi / 180) * math.cos((MLonA - MLonB) * Pi / 180)
                  D = R * math.acos(C) * Pi / 100
                  distance += D
                  """
            return distance


      def matchFun(self):
            return lambda life: 1.0 / self.distance(life.gene)


      def run(self, n = 0):
            while n > 0:
                  self.ga.next()
                  distance = self.distance(self.ga.best.gene)
                  #print (("%d : %f") % (self.ga.generation, distance))
                  n -= 1
            print(distance)


def main():
      tsp = TSP()
      tsp.run(10)


if __name__ == '__main__':
      main()

Submission status: Wrong Answer

Solution code:
import heapq
N = int(input())
AB = []
for i in range(N):
  a, b = map(int, input().split())
  heapq.heappush(AB, [a, i, 0])
  heapq.heappush(AB, [b, i, 1])
AB = AB[:N+1]
ans = sum([ab[0] for ab in AB])
A = []
B = []
C = []
AB.sort(key=lambda x: x[1])
while AB:
  if len(AB) > 1 and AB[0][1] == AB[1][1]:
    if AB[0][2] == 0:
      C.append([AB[0][0], AB[1][0]])
    else:
      C.append([AB[1][0], AB[0][0]])
    AB = AB[2:]
  elif AB[0][2] == 0:
    A.append(AB[0][0])
    AB = AB[1:]
  else:
    B.append(AB[0][0])
    AB = AB[1:]
if len(A) == 0:
  ans -= max(max(B), max([c[0] for c in C]))
elif len(B) == 0:
  ans -= max(max(A), max([c[1] for c in C]))
elif len(C) == 1:
  ans -= max(max(A), max(B))
else:
  ans -= max(max(A), max(B), max([max(c) for c in C]))
print(ans)

Submission status: Wrong Answer

Solution code:
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])
	assert min_value>=max_value
	print sum-max_value+min_value

Submission status: Wrong Answer

Solution code:
n = int(input())
lisa = []
lisb = []
lia = []
lib = []
for i in range(n):
  a,b = map(int,input().split())
  lisa.append(a)
  lisb.append(b)
lia = sorted(lisa)
lib = sorted(lisb,reverse=True)
ans = 0
key = [int(i) for i in range(n)]
for i in range(n):
  lib.sort(reverse=True)
  if key[lisa.index(lia[i])] != lisb.index(lib[0]) and key[lisa.index(lia[i])] != lisa.index(lia[0]):
    key[lisa.index(lia[i])] = lisb.index(lib[0])
    ans += min(lia[i],lib[0])
    lib[0] = -1
  elif key[lisa.index(lia[i])] != lisb.index(lib[1]) and key[lisa.index(lia[i])] != lisa.index(lia[1]):
    key[lisa.index(lia[i])] = lisb.index(lib[1])
    ans += min(lia[i],lib[1])
    lib[1] = -1
  else:
    key[lisa.index(lia[i])] = lisb.index(lib[2])
    ans += min(lia[i],lib[2])
    lib[1] = -1
print(ans)

Submission status: Wrong Answer

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()
s = sorted(A + B)
print(sum(s[:N]))