Problem:


Score : 500 points

Problem Statement

There are N integers, A_1, A_2, ..., A_N, written on a blackboard.

We will repeat the following operation N-1 times so that we have only one integer on the blackboard.

Choose two integers x and y on the blackboard and erase these two integers. Then, write a new integer x-y.

Find the maximum possible value of the final integer on the blackboard and a sequence of operations that maximizes the final integer.

Constraints

2 \leq N \leq 10^5

-10^4 \leq A_i \leq 10^4

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N

Output

Print the maximum possible value M of the final integer on the blackboard, and a sequence of operations x_i, y_i that maximizes the final integer, in the format below.

Here x_i and y_i represent the integers x and y chosen in the i-th operation, respectively.

If there are multiple sequences of operations that maximize the final integer, any of them will be accepted.

M
x_1 y_1
:
x_{N-1} y_{N-1}

Sample Input 1

3
1 -1 2

Sample Output 1

4
-1 1
2 -2

If we choose x = -1 and y = 1 in the first operation, the set of integers written on the blackboard becomes (-2, 2).

Then, if we choose x = 2 and y = -2 in the second operation, the set of integers written on the blackboard becomes (4).

In this case, we have 4 as the final integer. We cannot end with a greater integer, so the answer is 4.

Sample Input 2

3
1 1 1

Sample Output 2

1
1 1
1 0



Sample input:
3
1 -1 2


Sample output:
4
-1 1
2 -2

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

def main():
    N = II()
    A = LI()

    A.sort()
    from collections import deque

    if N%2 != 0:
        if -sum(A[:N//2])+sum(A[N//2:]) > -sum(A[:N//2+1]) + sum(A[N//2+1:]):
            minus = deque(A[:N//2])
            plus = deque(A[N//2:])
            ans_li = []
            p = plus.popleft()
            m = minus.popleft()
            tmp = m - p
            ans_li.append('{} {}'.format(m, p))
            while True:
                try:
                    p = plus.popleft()
                    ans_li.append('{} {}'.format(p, tmp))
                    tmp = p - tmp
                    m = minus.popleft()
                    ans_li.append('{} {}'.format(m, tmp))
                    tmp = m - tmp
                except:
                    print(tmp)
                    for i in ans_li: print(i)
                    return

        else:
            minus = deque(A[:N//2+1])
            plus = deque(A[N//2+1:])
            m = minus.popleft()
            p = plus.popleft()
            tmp = p - m
            ans_li = ['{} {}'.format(p, m)]
            while True:
                try:
                    m = minus.popleft()
                    if len(minus) == 0:
                        ans_li.append('{} {}'.format(tmp, m))
                        tmp = tmp - m
                    else:
                        ans_li.append('{} {}'.format(m, tmp))
                        tmp = m - tmp
                    p = plus.popleft()
                    ans_li.append('{} {}'.format(p, tmp))
                    tmp = p - tmp
                except:
                    print(tmp)
                    for i in ans_li: print(i)
                    return

    else:
        minus = deque(A[:N//2])
        plus = deque(A[N//2:])
        m = plus.popleft()
        p = minus.popleft()
        tmp = m - p
        ans_li = ['{} {}'.format(m, p)]
        while True:
            try:
                m = minus.popleft()
                ans_li.append('{} {}'.format(m, tmp))
                tmp = m - tmp
                p = plus.popleft()
                ans_li.append('{} {}'.format(p, tmp))
                tmp = p - tmp
            except:
                print(tmp)
                for i in ans_li: print(i)
                return


main()

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
a = sorted(a)
ans = []
ma, a = a[-1],a[:-1]
mi = a[0]
for i in range(1,len(a)):
    ans.append([mi,a[i]])
    mi -= a[i]
ans.append([ma,mi])
print(ma-mi)
for x,y in ans:
    print(x,y)

Submission status: Wrong Answer

Solution code:
import sys
N = int(input())
A = sorted(list(map(int,input().split())))

mn = A[0]
mx = A[-1]
if N ==2:
    print(A[1] - A[0])
    print(A[1],A[0])
    sys.exit()
ope = []
for a in A[1:-1]:
    if a <=0:
        ope.append([mx, a])
        mx -= a
    else:
        ope.append([a, mn])
        mn -= a
ope.append([mx,mn])
print(mx-mn)
for o in ope:
    print(o[0],o[1])

Submission status: Wrong Answer

Solution code:
N=int(input())
a = list(reversed(sorted(map(int,input().split()))))

same = []
diff = []

while len(a) > 1:
    mx = a.pop(0)
    mn = a.pop(-1)
    if mx > 0 and mn < 0:
        same.append((mx,mn))
    else:
        if mx > 0 or mn > 0:
            # 両方+
            diff.append((mx,mn))
        else:
            # 両方-
            diff.append((mn,mx))

result = []
cs = []
c = True
if len(a) == 1 and a[0] > 0:
    cs.append(a[0])
    c = False

for x,y in same:
    if c:
        x,y = y,x
        c = False
    result.append((y,x))
    cs.append(y-x)

for x,y in diff:
    if c:
        x,y = y,x
        c = False
    if x < 0 or y < 0:
        x,y = y,x
        c = False
    result.append((y,x))
    cs.append(y-x)

if len(a) == 1 and a[0] < 0:
    cs.append(a[0])

sm = cs.pop(0)
while len(cs) > 0:
    y = cs.pop(0)
    result.append((sm, y))
    sm += -1*y

print(sm)

for r in result:
    print(r[0],r[1])

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort()
ans = 0
hoge = sum(A)
p = 0
for i in range(N-1):
    hoge -= A[i]*2
    if hoge > ans:
        ans = hoge
        p = i
print(ans)
hoge = A[0]
for i in range(p+1,N-1):
    print(hoge,A[i])
    hoge -= A[i]
print(A[N-1],hoge)
hoge = A[N-1] - hoge
for i in range(1,p):
    print(hoge,A[i])
    hoge -= A[i]

Submission status: Wrong Answer

Solution code:
n=int(input())
lst=[int(i) for i in input().split()]
lst.sort()
cnt=0
for i in range(n):
    if lst[i]>0:
        break
    if lst[i]<0:
        cnt+=1
ans=0
for i in lst:
    if i<0:
        ans-=i
    else:
        ans+=i
if cnt!=n and cnt!=0:
    print(ans)
    if n>2:
        if n-cnt>1:
            for i in range(cnt+1,n):
                if i==cnt+1:
                    print(lst[0],lst[i])
                    res=lst[0]-lst[i]
                else:
                    print(res,lst[i])
                    res-=lst[i]
            if cnt>1:
                for i in range(1,cnt):
                    print(lst[cnt],lst[i])
                    res-=lst[i]
            print(lst[cnt],res)
        else:
            for i in range(cnt):
                if i==0:
                    print(lst[-1],lst[0])
                    res=lst[-1]-lst[0]
                else:
                    print(res,lst[i])
                    res-=lst[i]
    else:
        print(lst[1],lst[0])
            
elif cnt==n:
    ans=ans+2*lst[-1]
    print(ans)
    for i in range(n-1):
        if i==0:
            print(lst[-1],lst[i])
            res=lst[-1]-lst[i]
        else:
            print(res,lst[i])
            res-=lst[i]
else:
    ans=ans-2*lst[0]
    print(ans)
    if n>2:
        for i in range(1,n-1):
            if i==1:
                print(lst[0],lst[i])
                res=lst[0]-lst[i]
            else:
                print(res,lst[i])
                res-=lst[i]
        print(lst[-1],res)
    
    else:
        print(lst[1],lst[0])

Submission status: Wrong Answer

Solution code:
N = int(input())
a = sorted(list(map(int, input().split())))
nyu = []
i=0
while i!=N-2:
    if a[1]>=0:
        x=a.pop(0)
        y=a.pop(0)
        nyu.append([x,y])
        a.insert(0, x-y)
    else:
        x=a.pop(2)
        y=a.pop(1)
        nyu.append([x,y])
        a.append(x-y)
        a.sort()
    i += 1
nyu.append([a[1], a[0]])
print(nyu[N-2][0]-nyu[N-2][1])
for i in range(N-1):
    print(nyu[i][0], nyu[i][1])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
# input
n = int(input())
a = list(map(int, input().split()))
# calc
ap = [i for i in a if i > 0]
am = [i for i in a if i < 0]
a0 = [i for i in a if i == 0]
ans = 0
t = 0
t2 = 0
lap = len(ap)
lam = len(am)
la0 = len(a0)
if lap > 0 and lam > 0:
    ans = sum(ap)+abs(sum(am))
    print(ans)
    for i in range(la0):
        print(am[0], 0)

    if lam == 1 and lap > 1:
        print(am[0], ap[0])
        t = am[0]-ap[0]
        for i in range(1, lap-1):
            print(t, ap[i])
            t -= ap[i]
        print(ap[lap-1], t)
    elif lam > 1 and lap == 1:
        print(ap[0], am[0])
        t = ap[0]-am[0]
        for i in range(1, lam):
            print(t, am[i])
            t -= am[i]
    elif lam == 1 and lap == 1:
        print(ap[0], am[0])
    else:
        t = am[0]
        t2 = ap[0]
        for i in range(1, lap):
            print(t, ap[i])
            t -= ap[i]
        for i in range(1, lam):
            print(t2, am[i])
            t2 -= am[i]
        print(t2, t)
elif lap == 0 and lam > 1:
    am.sort()
    for i in range(lam-1):
        t += am[i]
    ans = t*(-1) + am[lam-1]
    print(ans)
    for i in range(la0):
        print(am[0], 0)
    t2 = am[lam-1]
    for i in range(lam-1):
        print(t2, am[i])
        t2 -= am[i]
elif lap > 1 and lam == 0:
    ap.sort()
    for i in range(1, lap):
        t += ap[i]
    ans = t - ap[0]
    print(ans)
    for i in range(la0):
        print(ap[0], 0)
    t2 = ap[0]
    for i in range(1, lap-1):
        print(t2, ap[i])
        t2 -= ap[i]
    print(ap[lap-1], t2)
elif lap == 1 and lam == 0:
    print(ap[0])
    for i in range(la0):
        print(ap[0], 0)
elif lap == 0 and lam == 1:
    print(abs(am[0]))
    for i in range(la0-1):
        print(0, 0)
    print(0, am[0])
elif lap == 0 and lam == 0:
    print(0)
    for i in range(la0-1):
        print(0, 0)

Submission status: Wrong Answer

Solution code:
def solve():
    N = int(raw_input())
    A = [int(_) for _ in raw_input().split()]
    A.sort()
    ret = abs(A[N-1] - A[0])
    rever_cnt = 0
    for i in range(1, N-1):
        if A[i] >= 0:
            ret = ret + A[i]
            rever_cnt += 1
        else:
            ret = ret - A[i]
    print ret
    def ManPrint(a, b):
        if rever_cnt % 2 == 0:
            print a, b
        else:
            print b, a
    def PrintAndCalcSave(a, b):
        print a, b
        return a - b

    save = abs(A[N-1] - A[0])
    if rever_cnt % 2 == 1:
        save = - save
    if A[N-1] > A[0]:
        if rever_cnt % 2 == 0:
            save = PrintAndCalcSave(A[N-1], A[0])
        else:
            save = PrintAndCalcSave(A[0], A[N-1])
    else:
        if rever_cnt % 2 == 0:
            save = PrintAndCalcSave(A[0], A[N-1])
        else:
            save = PrintAndCalcSave(A[N-1], A[0])
    for i in range(1, N - 1):
        if rever_cnt % 2 == 0:
            save = PrintAndCalcSave(save, A[i])
        else:
            save = PrintAndCalcSave(A[i], save)

if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))

A = sorted(A)
plus = []
minus = []

for i in range(N):
    if i == 0:
        minus.append(A[i])
    elif i == N-1:
        plus.append(A[i])
    else:
        if A[i] > 0:
            plus.append(A[i])
        else:
            minus.append(A[i])

print(sum(plus)-sum(minus))
tmp = minus[0]
for i in range(len(plus)-1):
    print(tmp,plus[i])
    tmp -= plus[i]

A[0] = tmp
tmp2 = A[-1]
for i in range(len(minus)):
    print(tmp2,minus[i])
    tmp2 -= minus[i]

Submission status: Wrong Answer

Solution code:
N = int( input())
A = list( map( int, input().split()))
A.sort(reverse = True)
plus = 0
zero = 0
for i in range(N):
    if A[i] > 0:
        plus += 1
    elif A[i] == 0:
        zero += 1
minus = N - plus - zero
if plus + zero== N:
    print(sum(A)-A[-1]*2)
    now = A[-1]
    for i in range(N-2):
        print(now, A[i])
        now -= A[i]
    print(A[N-2], now)
elif minus + zero== N:
    print(A[0]*2 - sum(A))
    now = A[0]
    for i in range(1,N):
        print(now, A[i])
        now -= A[i]
elif plus+zero == 1:
    print( sum( list( map( abs, A))))
    now = A[0]
    for i in range(1,N):
        print(now, A[i])
        now -= A[i]
else:
    print( sum( list( map( abs, A))))
    now = A[N-1]
    k = N-1
    for i in range(1,N-1):
        if A[i] <= 0:
            k = i
            break
        print(now, A[i])
        now -= A[i]
    print(A[0], now)
    now = A[0] - now
    for i in range(k+1,N-1):
        if A[i] > 0:
            pass
        print(now, A[i])
        now -= A[i]

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
a = sorted(a)
minus = len([i for i in a if i < 0])
if minus == 0:
  minus = 0
elif minus == len(a):
  minus = len(a)-2
  
print(sum(a[minus:])- sum(a[:minus]))
for e in a[minus+1:-1]:
  print(str(a[0])+" "+str(e))
  a[0] -= e
for e in a[:minus+1]:
  print(str(a[-1])+" "+str(e))
  a[-1] -= e

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
N = int(input())
a_list = np.array(list(map(int, input().split())))
a_list = np.sort(a_list)
ans = 10 ** 9
pr_list = []
pos_list = a_list[a_list >= 0]
neg_list = a_list[a_list < 0]
while ans == 10 ** 9:
    print(pos_list, neg_list)
    if len(pos_list) + len(neg_list) == 2:
        final_a_list = np.concatenate([pos_list, neg_list])
        ans = max(final_a_list) - min(final_a_list)
        pr_list.append("{} {}".format(max(final_a_list), min(final_a_list)))
    elif len(pos_list) == 0:
        neg_list = np.sort(neg_list)
        dif = neg_list[-1] -  neg_list[-2]
        pr_list.append("{} {}".format(neg_list[-1], neg_list[-2]))
        neg_list = np.delete(neg_list, -1)
        neg_list = np.delete(neg_list, -2)
        if dif >= 0:
            pos_list= np.append(pos_list, dif)
        else:
            neg_list= np.append(neg_list, dif)            
    elif len(neg_list) == 0:
        pos_list = np.sort(pos_list)
        dif = pos_list[0] - pos_list[1]
        pr_list.append("{} {}".format(pos_list[0], pos_list[1]))
        pos_list = np.delete(pos_list, 0)
        pos_list = np.delete(pos_list, 1)    
        if dif >= 0:
            pos_list= np.append(pos_list, dif)
        else:
            neg_list= np.append(neg_list, dif)            
    elif len(pos_list) > 0 and len(neg_list) > 0:
        while len(pos_list) > 1:
            dif = neg_list[0] - pos_list[0]
            pr_list.append("{} {}".format(neg_list[0], pos_list[0]))
            pos_list = np.delete(pos_list, 0)
            neg_list = np.delete(neg_list, 0)
            neg_list = np.append(neg_list, dif)
        while len(neg_list) > 1:
            dif = pos_list[0] - neg_list[0]
            pr_list.append("{} {}".format(pos_list[0], neg_list[0]))
            pos_list = np.delete(pos_list, 0)
            neg_list = np.delete(neg_list, 0)
            pos_list = np.append(pos_list, dif)

print(ans)
for i in pr_list:
    print(i)

Submission status: Wrong Answer

Solution code:
import sys

def bigsmall(x,y):
    if x > y:
        return x,y
    else:
        return y,x

def main():
    n = int(input())
    a = [int(x) for x in input().split()]

    diff_idx = -1
    min_idx = -1
    _min = 10*6
    for i in range(len(a)-1):
        if a[i] * a[i+1] <= 0:
            diff_idx = i
            break
        tmp_min = abs(a[i]) + abs(a[i+1])
        if tmp_min < _min:
            _min = tmp_min
            min_idx = i

    start_idx = diff_idx if diff_idx != -1 else min_idx
    ops = []

    a2 = a[start_idx:]
    a2.extend(a[:start_idx])

    if len(a2) > 2:
        b,s = bigsmall(a2[0],a2[1])
        if a2[2] < 0:
            ops.append((b,s))
            curr = b - s
        else:
            ops.append((s,b))
            curr = s - b

        for i in range(2,len(a2)-1):
            b,s = bigsmall(curr,a2[i])

            if a2[i+1] < 0:
                ops.append((b,s))
                curr = b - s
            else:
                ops.append((s,b))
                curr = s - b

        if a2[-1] < 0:
            ops.append((curr, a2[-1]))
            curr = curr - a2[-1]
        else:
            ops.append((a2[-1], curr))
            curr = a2[-1] - curr
    else:
        b,s = bigsmall(a2[0],a2[1])
        curr = b-s
        ops.append((b,s))

    print(curr)
    for x,y in ops:
        print(x,y)

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int( input())
A = list( map( int, input().split()))
A.sort(reverse = True)
plus = 0
zero = 0
for i in range(N):
    if A[i] > 0:
        plus += 1
    elif A[i] == 0:
        zero += 1
minus = N - plus - zero
if plus == N:
    print(sum(A)-A[-1]*2)
    now = A[-1]
    for i in range(N-2):
        print(now, A[i])
        now -= A[i]
    print(A[N-2], now)
elif minus == N:
    print(A[0]*2 - sum(A))
    now = A[0]
    for i in range(1,N):
        print(now, A[i])
        now -= A[i]
elif plus+zero == 1:
    print( sum( list( map( abs, A))))
    now = A[0]
    for i in range(1,N):
        print(now, A[i])
        now -= A[i]
else:
    print( sum( list( map( abs, A))))
    now = A[N-1]
    for i in range(1,N-1):
        if A[i] <= 0:
            break
        print(now, A[i])
        now -= A[i]
    print(A[0], now)
    now = A[0] - now
    for i in range(2,N-1):
        if A[i] > 0:
            pass
        print(now, A[i])
        now -= A[i]

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(x) for x in input().split()]
plus = [x for x in A if x > 0]
minus = [x for x in A if x <= 0]
plus.sort()
minus.sort()
minA = minus.pop() if minus else plus.pop(0)
M = sum(plus) - sum(minus) - minA
print(M)
xy = minA
for i in range(N - 1):
  if len(plus) > 1:
    y = plus.pop()
    print('{} {}'.format(xy, y))
    xy -= y
  elif len(plus) == 1:
    x = plus[0]
    print('{} {}'.format(x, xy))
    xy = x - xy
  else:
    y = minus.pop()
    print('{} {}'.format(xy, y))
    xy -= y

Submission status: Wrong Answer

Solution code:
l = input().split()
N = int(l[0])

l = input().split()
A = [int(x) for x in l]

# print(N, A)

A.sort()

ans = A[0]
pairs = []
for i in range(1, N - 1):
    pairs.append((ans, A[i]))
    ans -= A[i]

pairs.append((A[N - 1], ans))
ans = A[N - 1] - ans
print(ans)
for p in pairs:
    print(p[0], p[1])

Submission status: Wrong Answer

Solution code:
import sys

def bigsmall(x,y):
    if x > y:
        return x,y
    else:
        return y,x

def main():
    n = int(input())
    a = [int(x) for x in input().split()]

    diff_idx = -1
    min_idx = -1
    _min = 10*6
    for i in range(len(a)-1):
        if a[i] * a[i+1] <= 0:
            diff_idx = i
            break
        tmp_min = abs(a[i]) + abs(a[i+1])
        if tmp_min < _min:
            _min = tmp_min
            min_idx = i

    start_idx = diff_idx if diff_idx != -1 else tmp_min
    ops = []

    a2 = a[start_idx:]
    a2.extend(a[:start_idx])

    if len(a2) > 2:
        b,s = bigsmall(a2[0],a2[1])
        if a2[2] < 0:
            ops.append((b,s))
            curr = b - s
        else:
            ops.append((s,b))
            curr = s - b

        for i in range(2,len(a2)-1):
            b,s = bigsmall(curr,a2[i])

            if a2[i+1] < 0:
                ops.append((b,s))
                curr = b - s
            else:
                ops.append((s,b))
                curr = s - b

        if a2[-1] < 0:
            ops.append((curr, a2[-1]))
            curr = curr - a2[-1]
        else:
            ops.append((a2[-1], curr))
            curr = a2[-1] - curr
    else:
        b,s = bigsmall(a2[0],a2[1])
        curr = b-s
        ops.append((b,s))

    print(curr)
    for x,y in ops:
        print(x,y)

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
A.sort(reverse=True)

while len(A) >= 3 :
    a = A.pop(1)
    b = A.pop()
    print(b, a)
    A.append(b - a)
    
print(A[0], A[1])
print(A[0] - A[1])

Submission status: Wrong Answer

Solution code:
N = int( input())
A = list( map( int, input().split()))
A.sort(reverse = True)
plus = 0
zero = 0
for i in range(N):
    if A[i] > 0:
        plus += 1
    elif A[i] == 0:
        zero += 1
minus = N - plus - zero
if plus == N:
    print(sum(A)-A[-1]*2)
    now = A[-1]
    for i in range(N-2):
        print(now, A[i])
        now -= A[i]
    print(A[N-2], now)
elif minus == N:
    print(A[0]*2 - sum(A))
    now = A[0]
    for i in range(1,N):
        print(now, A[i])
        now -= A[i]
elif plus+zero == 1:
    print( sum( list( map( abs, A))))
    now = A[0]
    for i in range(1,N):
        print(now, A[i])
        now -= A[i]
else:
    print( sum( list( map( abs, A))))
    now = A[N-1]
    for i in range(1,N):
        if A[i] < 0:
            break
        print(now, A[i])
        now -= A[i]
    print(A[0], now)
    now = A[0] - now
    for i in range(2,N-1):
        if A[i] <= 0:
            pass
        print(now, A[i])
        now -= A[i]

Submission status: Wrong Answer

Solution code:
import logging
import unittest
from collections import (
    Counter,
)

import functools as ft
from collections import (
    namedtuple,
    deque,
)
from heapq import (
    heappush,
    heappop,
)

debug = logging.getLogger(__name__).debug


@ft.total_ordering
class PrioritizedItem(namedtuple('PrioritizedItem', 'priority, value')):
    def __lt__(self, other):
        return self.priority < other.priority


def a_star(succ, cost, heuristic, start):
    cost_dict = {start: (heuristic(start), 0)}
    prev_dict = {}
    close = set()
    q = [PrioritizedItem(cost_dict[start], start)]

    while q:
        cost_u, u = heappop(q)
        if u not in close and cost_u <= cost_dict[u]:
            close.add(u)

            yield u, prev_dict, cost_dict

            for v in succ(u):
                cost_uv = cost(u, v)
                heuristic_v = heuristic(v)

                cost_v_old = cost_dict.get(v)
                cost_v_new = (
                    cost_u[1] + cost_uv + heuristic_v,
                    cost_u[1] + cost_uv,
                )
                if cost_v_old is None or cost_v_new < cost_v_old:
                    cost_dict[v] = cost_v_new
                    prev_dict[v] = u
                    heappush(q, PrioritizedItem(cost_v_new, v))
                    try:
                        close.remove(v)
                    except KeyError:
                        pass


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


def _main():
    n, = input_ints()
    a = input_ints()

    path = []
    while len(a) > 2:
        a.sort()
        path.append((a[0], a[-2]))
        a.append(a.pop(0) - a.pop(-2))

    path.append((a[0], a[1]))
    print(a[0] - a[1])
    for p in path:
        print(*p)


class Test(unittest.TestCase):
    def setUp(self):
        import run
        self._test = run

    def test_main(self):
        self._test.test_files(self, _main)


if __name__ == '__main__':
    _main()

Submission status: Wrong Answer

Solution code:
import sys

def bigsmall(x,y):
    if x > y:
        return x,y
    else:
        return y,x

def main():
    n = int(input())
    a = [int(x) for x in input().split()]

    diff_idx = -1
    min_idx = -1
    _min = 10*6
    for i in range(len(a)-1):
        if a[i] * a[i+1] <= 0 and (a[i] != 0 or a[i+1] != 0):
            diff_idx = i
            break
        tmp_min = abs(a[i]) + abs(a[i+1])
        if tmp_min < _min:
            _min = tmp_min
            min_idx = i

    start_idx = diff_idx if diff_idx != -1 else tmp_min
    ops = []

    a2 = a[start_idx:]
    a2.extend(a[:start_idx])

    b,s = bigsmall(a[0],a[1])

    if len(a2) > 2:
        if a2[2] < 0:
            ops.append((b,s))
            curr = b - s
        else:
            ops.append((s,b))
            curr = s - b

        for i in range(2,len(a2)-1):
            b,s = bigsmall(curr,a[i])

            if a2[i+1] < 0:
                ops.append((b,s))
                curr = b - s
            else:
                ops.append((s,b))
                curr = s - b

        if a2[-1] < 0:
            ops.append((curr, a2[-1]))
            curr = curr - a2[-1]
        else:
            ops.append((a2[-1], curr))
            curr = a2[-1] - curr
    else:
        b,s = bigsmall(a2[0],a2[1])
        curr = b-s
        ops.append((b,s))

    print(curr)
    for x,y in ops:
        print(x,y)

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
Max = sys.maxsize
def l():
    return list(map(int,input().split()))
def m():
    return map(int,input().split())
def onem():
    return int(input())
def s(x):
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa == x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x):
    return " ".join(map(str,x))

n = onem()

a = l()
a.sort()
a = cl.deque(a)
aa = []
co = 0
up = a.pop()
do = a.popleft()

for i in range(len(a)):
    if a[i] >= 0:
        aa.append([do,a[i]])
        do -= a[i]
    else:
        aa.append([up,a[i]])
        up += a[i]    
aa.append([up,do])
print(up-do)
for i in range(n-1):
    print(jo(aa[i]))

Submission status: Wrong Answer

Solution code:
N = int(input())						# 5
A = sorted(list( map(int, input().split()) ))	# 1 2 3 4 5 ...(ソート付き)

ans=0
ANS=[]

for i in range(N-1):
	x=A[i]
	y=A[i+1]
	if i==N-2:
		x,y=y,x
		ans = x-y
	else:
		if x==y:
			j=i
			B=[]
			while A[i]==A[j]:
				j+=1
				B.append((A[i],A[j]))
				if j==N-1:
					print(ans)
					for a in ANS:
						print(*a)
					for a in B:
						print(*a)
					exit()
			
			x=A[i]
			y=A[j]
			A[j] = A[i+1]
			
			A[i+1]=x-y
		else:
			A[i+1]=x-y
		

	ANS.append((x,y))


print(ans)
for a in ANS:
	print(*a)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
a = sorted(a)
print(sum(a[len(a)//2:])- sum(a[:len(a)//2]))
for e in a[len(a)//2:-1]:
  print(str(a[0])+" "+str(e))
  a[0] -= e
for e in a[1:len(a)//2]:
  print(str(a[-1])+" "+str(e))
  a[-1] -= e

print(str(a[-1])+" "+str(a[0]))

Submission status: Wrong Answer

Solution code:
import sys
N=int(input())
A=list(map(int,input().split()))

plus=[]
minus=[]

if min(A)>=0:
    tmp=min(A)
    print(sum(A)-tmp*2)
    if len(A)==2:
        print(max(A),min(A))
        sys.exit()
    tmpind=A.index(tmp)
    if tmpind==len(A)-1:
        tmpind=0
        aa=A[0]
        A[0]=A[-1]
        A[-1]=aa
    for i in range(len(A)-1):
        if i==tmpind:continue
        print(tmp,A[i])
        tmp-=A[i]
    print(A[-1],tmp)
    
elif max(A)<=0:
    tmp=max(A)
    print(-(sum(A)-tmp*2))
    if len(A)==2:
        print(max(A),min(A))
        sys.exit()
    tmpind=A.index(tmp)
    if tmpind==len(A)-1:
        tmpind=0
        aa=A[0]
        A[0]=A[-1]
        A[-1]=aa
    for i in range(len(A)-1):
        if i==tmpind:continue
        print(tmp,A[i])
        tmp-=A[i]
    print(tmp,A[-1])
    
else:
    print(sum(map(abs,A)))
    for i in range(len(A)):
        if A[i]>0:
            plus.append(A[i])
        else:
            minus.append(A[i])
    if len(plus)==1 and len(minus)==1:
        print(plus[0],minus[0])
    elif len(minus)==1:
        tmp=minus[0]
        for i in range(len(plus)-1):
            print(tmp,plus[i])
            tmp-=A[i]
        print(plus[-1],tmp)
    else:
        for i in range(1,len(minus)):
            print(plus[-1],minus[i])
            plus[-1]-=minus[i]
        tmp=minus[0]
        for i in range(len(plus)-1):
            print(tmp,plus[i])
            tmp-=plus[i]
        print(plus[-1],tmp)

Submission status: Wrong Answer

Solution code:
N = int(input())						# 5
A = sorted(list( map(int, input().split()) ))	# 1 2 3 4 5 ...(ソート付き)

ans=0
ANS=[]

for i in range(N-1):
	x=A[i]
	y=A[i+1]
	if i==N-2:
		x,y=y,x
		ans = x-y
	else:
		if x==y:
			j=i
			
			while A[i]==A[j]:
				j+=1
				if j==N-1:
					print(ans)
					exit()
			
			x=A[i]
			y=A[j]
			A[j] = A[i+1]
			
			A[i+1]=x-y
		else:
			A[i+1]=x-y
		

	ANS.append((x,y))


print(ans)
for a in ANS:
	print(*a)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
a_sorted = sorted(a)
print(sum(a[len(a)//2:])- sum(a[:len(a)//2]))
for e in a[len(a)//2:-1]:
  print(str(a[0])+" "+str(e))
  a[0] -= e
for e in a[1:len(a)//2]:
  print(str(a[-1])+" "+str(e))
  a[-1] -= e

print(str(a[-1])+" "+str(a[0]))

Submission status: Wrong Answer

Solution code:
count = int(input())
As = input().split(" ")
intAs = [0 for _ in range(count)]
ARray = []
for i in range(count):
	intAs[i] = int(As[i])
intAs.sort()
ARray.append(intAs)
prints = []
while len(ARray[-1]) != 1:
  if(len(ARray[-1])%2 == 1):
    #奇数だったら
    ARray.append([0 for _ in range(int(len(ARray[-1])/2) + 1)])
    #print(ARray[-1])
    for i in range(int(len(ARray[-1])/2) + 1):
      if(i != int(len(ARray[-1])/2)):
        ARray[-1][i] = ARray[-2][int(len(ARray[-1])/2 + 1)-i] - ARray[-2][i] 
        prints.append(ARray[-2][int(len(ARray[-1])/2 + 1)-i])
        prints.append(ARray[-2][i])
      else:
        ARray[-1][i] = ARray[-2][i]
  else:
    ARray.append([0 for _ in range(int(len(ARray[-1])/2))])
    #print(ARray[-1])
    #print(int(len(ARray[-1])/2))
    if(len(ARray[-1]) != 1):
      for i in range(int(len(ARray[-1])/2)):
          #print(int(len(ARray[-1])/2)+1-i,i)
          ARray[-1][i] = ARray[-2][int(len(ARray[-1])/2)+1-i] - ARray[-2][i]
          prints.append(ARray[-2][int(len(ARray[-1])/2)+1-i])
          prints.append(ARray[-2][i])
    else:
      ARray[-1][0] = ARray[-2][1] - ARray[-2][0] 
      prints.append(ARray[-2][1])
      prints.append(ARray[-2][0])
  ARray[-1].sort()
#print(intAs)
#print(ARray)
#print(prints)
print(ARray[-1][0])
for i in range(int(len(prints)/2)):
  print(str(prints[i*2])+" "+str(prints[i*2+1]))

Submission status: Wrong Answer

Solution code:
N = int(input())
a = list(map(int, input().split()))
a.sort()
b = a[0] - a[N - 1]
d = a[0]
e = a[N - 1]
if N > 2:
    for i in range(N - 3):
        b = b - a[N - 2 - i] 
    if b > a[1]:
        print(b - a[1])
    else:
        print(a[1] - b)
    for j in range(N - 2):
        print(d, end = ' ')
        print(e)
        d = d - e
        e = a[N - 2 - j]
    if e >= d:
        print(e, end = ' ')
        print(d, end = ' ')
    else:
        print(d, end = ' ')
        print(e, end = ' ')
else:
    print(a[1] - a[0])
    print(a[1], end = ' ')
    print(a[0], end = ' ')