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: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**5
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N = NI()
    A = LI()
    A.sort(reverse=True)
    p = []
    for i in range(1,len(A)-1):
        if A[i] < 0: break
        p.append((A[-1],A[i]))
        A[-1] -= A[i]
        A[i] = INF
    for a in A[1:]:
        if a < INF:
            p.append((A[0],a))
            A[0] -= a
    print(A[0])
    for a in p:
        print(a[0],a[1])


if __name__ == '__main__':
    main()

Submission status: Accepted

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

P = [a for a in A if a >= 0]
Q = [a for a in A if a < 0]

if len(P) == 0:
    P = [A[0]]
    Q = A[1:]
if len(Q) == 0:
    P = A[:-1]
    Q = [A[-1]]

print(sum(P) - sum(Q))

for i in range(1, len(P)):
    print(Q[0], P[i])
    Q[0] -= P[i]

for i in range(1, len(Q)):
    print(P[0], Q[i])
    P[0] -= Q[i]

print(P[0], Q[0])

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from bisect import bisect_right

n = int(readline())
a = list(map(int, readline().split()))
a.sort()
if a[0] <= 0 and a[-1] >= 0:
    print(sum(map(lambda x: abs(int(x)), a)))
    idx = bisect_right(a, 0)
    idx -= 1 if idx == n else 0
    x = a[0]
    y = a[idx]
    for aa in a[1:idx]:
        print(y, aa)
        y -= aa
    for aa in a[idx + 1:]:
        print(x, aa)
        x -= aa
    print(y, x)
else:
    if a[0] < 0:
        print(-sum(a) + 2 * a[-1])
        a = a[::-1]
    else:
        print(sum(a) - 2 * a[0])
    x = a[0]
    y = a[-1]
    for aa in a[1:-1]:
        print(x, aa)
        x -= aa
    if a[0] < 0:
        y, x = x, y
    print(y, x)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
from collections import deque
def main():
    n=int(input())
    A=list(map(int,input().split()))
    A.sort(reverse=True)
    Large=deque([a for a in A if a>=0])
    Small=deque([a for a in A if a<0])
    if not Large:Large.append(Small.popleft())
    if not Small:Small.append(Large.pop())
    ans=[]
    while len(Small)>=2:
        a,b=Large.pop(),Small.pop()
        ans.append((a,b))
        Large.append(a-b)
    small=Small.pop()
    while len(Large)>=2:
        a=Large.pop()
        ans.append((small,a))
        small-=a
    large=Large.pop()
    ans.append((large,small))
    print(large-small)
    for a,b in ans:
        print(a,b)

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import bisect
n = int(input())
A = list(map(int,input().split()))
A.sort()
if A[-1] <= 0:
    m = A[-1] - sum(A[:-1])
    print(m)
    now = A[-1]
    for i in range(n-1):
        print(now,A[i])
        now -= A[i]
elif A[0] >= 0:
    m = sum(A[1:]) - A[0]
    print(m)
    now = A[0]
    for i in range(1,n-1):
        print(now,A[i])
        now -= A[i]
    print(A[n-1],now)
else:
    zero = bisect.bisect_left(A,0)
    minus = A[:zero]
    plus = A[zero:]
    print(sum(plus) - sum(minus))
    now = minus[0]
    for p in plus[:-1]:
        print(now,p)
        now -= p
    print(plus[-1],now)
    now = plus[-1] - now
    for m in minus[1:]:
        print(now,m)
        now -= m

Submission status: Accepted

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

N = int(input())
As = list(map(int, input().split()))

history = []

positives = []
negatives = []
for A in As:
    if A >= 0:
        positives.append(A)
    else:
        negatives.append(A)

if not positives:
    n = max(negatives)
    negatives.remove(n)
    positives.append(n)

if not negatives:
    p = min(positives)
    positives.remove(p)
    negatives.append(p)

while len(negatives) > 1:
    p = positives.pop()
    n = negatives.pop()
    history.append((p, n))
    positives.append(p-n)

n = negatives[0]
while len(positives) > 1:
    p = positives.pop()
    history.append((n, p))
    n -= p

history.append((positives[0], n))
ans = positives[0] - n

print(ans)
for elem in history:
    print(*elem)

Submission status: Accepted

Solution code:
import sys
import copy
from collections import deque

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()

    if A[0] >= 0:
        ans = sum(A[1:]) - A[0]
        plus = copy.deepcopy(A[1:])
        minus = [A[0]]
    elif A[-1] <= 0:
        ans = -sum(A[:-1]) + A[-1]
        plus = [A[-1]]
        minus = copy.deepcopy(A[:-1])
    else:
        plus = []
        minus = []
        ans = 0
        for a in A:
            if a >= 0:
                ans += a
                plus.append(a)
            else:
                ans -= a
                minus.append(a)

    plus = deque(plus)
    minus = deque(minus)
    print(ans)

    # minusをまず一つにする
    while len(minus) > 1:
        p = plus.pop()
        m = minus.pop()
        print(p, m)
        plus.append(p - m)

    # minusが1つになったあとの処理
    p = plus.pop()
    m = minus.pop()
    if len(plus) == 0:
        print(p, m)
        return

    print(m, p)
    cur = m - p
    while len(plus) > 1:
        p = plus.pop()
        print(cur, p)
        cur -= p
    if len(plus) != 0:
        p = plus.pop()
        print(p, cur)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#diverta 2019 Programming Contest 2 -C Successive Subtraction
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
n = int(readline())
lst1 = list(map(int,readline().split()))

lst1.sort()
lst2 = []
l,r = lst1[0],lst1[-1]
for i in range(1,n-1):
    mid = lst1[i]
    if mid < 0:
        lst2.append([r,mid])
        r -= mid
    else:
        lst2.append([l,mid])
        l -= mid
lst2.append([r,l])
print(r-l)
for i in lst2:
    print(*i)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

n = int(input())
a = list( map(int, input().split()))

a.sort()

from bisect import bisect_left
from bisect import bisect_right

pos = n - bisect_left(a, 1)
neg = bisect_right(a, -1)


ans_exec = []

if pos>=neg:
    aa = a[max(0,neg-1):n-neg+1]
    for i in range(neg-1):
        ans_exec.append((a[-1-i], a[i]))
        aa.append(a[-1-i] - a[i])
    aa.sort()
    tmp = aa[0]
    for i in range(1,len(aa)-1):
        ans_exec.append((tmp, aa[i]))
        tmp = tmp-aa[i]
    ans_exec.append((aa[-1], tmp))
    ans = aa[-1] - tmp

elif pos<=neg:
    aa = a[max(0,pos-1):n-pos+1]
    for i in range(pos-1):
        ans_exec.append((a[i], a[-1-i]))
        aa.append(a[i] - a[-1-i])
    aa.sort()
    tmp = aa[-1]
    ans_exec.append((aa[-1], aa[0]))
    tmp = aa[-1]-aa[0]
    for i in range(1,len(aa)-1):
        ans_exec.append((tmp, aa[i]))
        tmp = tmp-aa[i]
    ans = tmp


print(ans)
for a,b in ans_exec:
    print(a,b)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
plus,minus=[],[]
for i in range(n):
    if a[i]>=0:
        plus.append(a[i])
    else:
        minus.append(a[i])
order=[]
if plus and minus:
    if len(plus)>=2:
        for num in plus[:-1]:
            order.append((minus[0],num))
            minus[0]-=num
    for num in minus:
        order.append((plus[-1],num))
        plus[-1]-=num
    print(plus[-1])
else:
    if minus:
        a=a[::-1]
    for i in range(1,n-1):
        order.append((a[0],a[i]))
        a[0]-=a[i]
    if minus:
        a=a[::-1]
    order.append((a[-1],a[0]))
    a[-1]-=a[0]
    print(a[-1])
for x,y in order:
    print(x,y)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
a = [int(i) for i in input().split()]
from collections import deque
l = []
r = []
for i in a:
  if i < 0:
    l.append(i)
  else:
    r.append(i)
    
ll = len(l)
rr = len(r)
r.sort()
l.sort()
ans = []
l = deque(l)
r = deque(r)

for i in range(n-1):
  if ll == 0:
    mi = r.popleft()
    ma = r.pop()
    ans.append((mi,ma))
    l.append(mi-ma)
    ll += 1
  else:
    if rr > 1:
      L = l.pop()
      R = r.pop()
      ans.append((L,R))
      l.append(L-R)
      rr -= 1
    elif rr == 1:
      L = l.pop()
      R = r.pop()
      ans.append((R,L))
      r.append(R-L)
    else:
      mi = l.popleft()
      ma = l.pop()
      ans.append((ma,mi))
      r.append(ma-mi)
      rr += 1
      
p,q = ans[-1]
print(abs(p-q))
if p < q:
  ans[-1] = (q,p)
for i,j in ans:
  print(i,j)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
A.sort()
ans=[0]*(N-1)
a=A[0]
z=A[-1]

for i in range(1,N-1):
    if A[i]>=0:
        ans[i-1]=(a,A[i])
        a-=A[i]
    else:
        ans[i-1]=(z,A[i])
        z-=A[i]
ans[N-2]=(z,a)
print(z-a)
for s in ans:
    print(*s)

Submission status: Accepted

Solution code:
n = int(input())
a = [int(x) for x in input().split()]
a.sort()
ans = [0]*(n-1)

k1, k2 = a[0], a[-1]
for i in range(1, n-1):
  if a[i] >= 0:
    ans[i-1] = (k1, a[i])
    k1 -= a[i]
  else:
    ans[i-1] = (k2, a[i])
    k2 -= a[i]
ans[n-2] = (k2, k1)
print(k2-k1)
for value in ans:
  print(*value)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
m,p=[],[]
for i in A:
    if i>=0:
        p.append(i)
    else:
        m.append(i)
if m and p:
    print(sum(p)-sum(m))
    t=m[0]
    for i in p[:-1]:
        print(t,i)
        t-=i
    print(p[-1],t)
    t=p[-1]-t
    for i in m[1:]:
        print(t,i)
        t-=i
elif p:
    p.sort()
    print(sum(p[1:])-p[0])
    t=p[0]
    for i in p[1:-1]:
        print(t,i)
        t-=i
    print(p[-1],t)
else:
    m.sort(reverse=1)
    print(m[0]-sum(m[1:]))
    t=m[0]
    for i in m[1:]:
        print(t,i)
        t-=i

Submission status: Accepted

Solution code:
# 符号が異なる数同士の引き算をすれば絶対値が大きくなる
# 基本は負から正を引いて大きな負の数を作る
# 最後だけ正から負を引いて大きな正の数を作る
# 正と正しか存在しない場合は最も小さい数からその他の数を引くことで負の数を作れる
# 負と負しか存在しない場合は最も大きい数からその他の数を引くことで正の数を作れる
# 正のリストと負のリスト両方を管理する
# 0は何も影響を与えないのでとりあえず正のリストに入れておく

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

if len(A) == 2:
  x = max(A)
  y = min(A)
  print(x-y)
  print(x,y)
  exit(0)

plusA = []
minusA = []
for a in A:
  if a >= 0:
    plusA += [a]
  else:
    minusA += [a]
    
method = [] # 計算過程をメモ
if len(plusA) == 0:
  minusA = sorted(minusA) # 最も小さな数を取り出すため
#  print("minusA",minusA)
  x = minusA.pop()
  y = minusA.pop()
#  print("x",x,"y",y)
  method.append([x,y])
  plusA.append(x-y)
#  print("plusA",plusA,"minusA",minusA,"method",method)
elif len(minusA) == 0:
  plusA = sorted(plusA)[::-1] # 最も小さな数を取り出すため
  x = plusA.pop()
  y = plusA.pop()
  method.append([x,y])
  minusA.append(x-y)
  
while True:
  if len(minusA) + len(plusA) == 1:
    print(x-y)
    for m in method:
      print(*m)
    break
  if len(plusA) == 1:
    # 正の数が一つのときは、この数から残りの負の数を引いていく
    x = plusA.pop()
    y = minusA.pop()
    method.append([x,y])
    plusA.append(x-y)
  else:
    # 正の数が複数あるときは、負の数を作り続ける
    x = minusA.pop()
    y = plusA.pop()
    method.append([x,y])
    minusA.append(x-y)

Submission status: Accepted

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

def main():
    N = int(input())
    A = list(map(int,input().split()))
    A.sort()

    li = []
    mm1 = A[N-1]
    mm2 = A[0]
    i = 1
    while(i<N-1):
        if A[i]<=0:
            li.append([mm1,A[i]])
            mm1 -= A[i]
        else:
            li.append([mm2,A[i]])
            mm2 -= A[i]
        i += 1
    li.append([mm1,mm2])
    print(mm1-mm2)
    for i in range(N-1):
        print(*li[i])
    

        


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int , input().split()))
pos = sorted([i for i in a if i >= 0], reverse=True)
neg = sorted([i for i in a if i < 0], reverse=True)

ans = []
if len(neg) == 0 and len(pos) == 2:
    print(pos[0] - pos[1])
    print(pos[0], pos[1])
    exit()
elif len(pos) == 0:
    tmp = neg[0]
    for i in range(1,len(neg)):
        ans.append([tmp, neg[i]])
        tmp -= neg[i]
    print(tmp)
    [print(*i) for i in ans]
    exit()
elif len(neg) == 0:
    neg.append(pos.pop())

tmp = neg.pop()
while len(pos) > 1:
    a = pos.pop()
    ans.append([tmp, a])
    tmp -= a
neg.append(tmp)

tmp = pos[0]
for i in neg:
    ans.append([tmp, i])
    tmp -= i

print(tmp)
[print(*i) for i in ans]

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


n = I()
A = LI()
if all([a > 0 for a in A]):
    now = min(A)
    print(sum(A) - now * 2)
    A.remove(now)
    last = A.pop()
    while A:
        nxt = A.pop()
        print(now, nxt)
        now -= nxt
    print(last, now)
elif all([a < 0 for a in A]):
    now = max(A)
    print(-sum(A) + now * 2)
    A.remove(now)
    while A:
        nxt = A.pop()
        print(now, nxt)
        now -= nxt
else:
    print(sum([abs(i) for i in A]))
    minus = []
    plus = []
    for a in A:
        if a > 0:
            plus += [a]
        elif a < 0:
            minus += [a]
        else:
            if not plus:
                plus += [a]
            else:
                minus += [a]
    minus_now = minus.pop()
    plus_now = plus.pop()
    while plus:
        nxt = plus.pop()
        print(minus_now, nxt)
        minus_now -= nxt
    while minus:
        nxt = minus.pop()
        print(plus_now, nxt)
        plus_now -= nxt
    print(plus_now, minus_now)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


n = I()
A = LI()
if all([a > 0 for a in A]):
    now = min(A)
    print(sum(A) - now * 2)
    A.remove(now)
    last = A.pop()
    while A:
        nxt = A.pop()
        print(now, nxt)
        now -= nxt
    print(last, now)
elif all([a < 0 for a in A]):
    now = max(A)
    print(-sum(A) + now * 2)
    A.remove(now)
    while A:
        nxt = A.pop()
        print(now, nxt)
        now -= nxt
else:
    print(sum([abs(i) for i in A]))
    minus = []
    plus = []
    for a in A:
        if a > 0:
            plus += [a]
        elif a < 0:
            minus += [a]
        else:
            if not plus:
                plus += [a]
            else:
                minus += [a]
    minus_now = minus.pop()
    plus_now = plus.pop()
    while plus:
        nxt = plus.pop()
        print(minus_now, nxt)
        minus_now -= nxt
    print(plus_now, minus_now)
    plus_now -= minus_now
    while minus:
        nxt = minus.pop()
        print(plus_now, nxt)
        plus_now -= nxt

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


n = I()
A = LI()
if all([a > 0 for a in A]):
    now = min(A)
    print(sum(A) - now * 2)
    A.remove(now)
    last = A.pop()
    while A:
        nxt = A.pop()
        print(now, nxt)
        now -= nxt
    print(last, now)
elif all([a < 0 for a in A]):
    now = max(A)
    print(-sum(A) + now * 2)
    A.remove(now)
    while A:
        nxt = A.pop()
        print(now, nxt)
        now -= nxt
else:
    print(sum([abs(i) for i in A]))
    minus = []
    plus = []
    for a in A:
        if a > 0:
            plus += [a]
        elif a < 0:
            minus += [a]
        else:
            if not plus:
                plus += [a]
            else:
                minus += [a]
    ret = minus.pop()
    plus_now = plus.pop()
    while plus:
        nxt = plus.pop()
        print(ret, nxt)
        ret -= nxt
    print(plus_now, ret)
    ret = plus_now - ret
    while minus:
        nxt = minus.pop()
        print(ret, nxt)
        ret -= nxt

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


n = I()
A = LI()
A.sort()
if all([a > 0 for a in A]):
    now = min(A)
    print(sum(A) - now * 2)
    A.remove(now)
    last = A.pop()
    while A:
        nxt = A.pop()
        print(now, nxt)
        now -= nxt
    print(last, now)
elif all([a < 0 for a in A]):
    now = max(A)
    print(-sum(A) + now * 2)
    A.remove(now)
    while A:
        nxt = A.pop()
        print(now, nxt)
        now -= nxt
else:
    print(sum([abs(i) for i in A]))
    minus = []
    plus = []
    for a in A:
        if a > 0:
            plus += [a]
        elif a < 0:
            minus += [a]
        else:
            if not plus:
                plus += [a]
            else:
                minus += [a]
    ret = minus.pop()
    for j in range(len(plus) - 1):
        print(ret, plus[j])
        ret -= plus[j]
    print(plus[-1], ret)
    ret = plus[-1] - ret
    for k in range(len(minus)):
        print(ret, minus[k])
        ret -= minus[k]

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


n = I()
A = LI()
A.sort()
if all([a > 0 for a in A]):
    now = min(A)
    print(sum(A) - now * 2)
    A.remove(now)
    last = A.pop()
    while A:
        nxt = A.pop()
        print(now, nxt)
        now -= nxt
    print(last, now)
elif all([a < 0 for a in A]):
    now = max(A)
    print(-sum(A) + now * 2)
    A.remove(now)
    while A:
        nxt = A.pop()
        print(now, nxt)
        now -= nxt
else:
    print(sum([abs(i) for i in A]))
    minus = []
    plus = []
    for a in A:
        if a > 0:
            plus += [a]
        elif a < 0:
            minus += [a]
        else:
            if not plus:
                plus += [a]
            else:
                minus += [a]
    ret = minus[-1]
    for j in range(len(plus) - 1):
        print(ret, plus[j])
        ret -= plus[j]
    print(plus[-1], ret)
    ret = plus[-1] - ret
    for k in range(len(minus) - 1):
        print(ret, minus[k])
        ret -= minus[k]

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


n = I()
A = LI()
A.sort()
if all([a > 0 for a in A]):
    now = min(A)
    print(sum(A) - now * 2)
    A.remove(now)
    last = A.pop()
    while A:
        nxt = A.pop()
        print(now, nxt)
        now -= nxt
    print(last, now)
elif all([a < 0 for a in A]):
    now = max(A)
    print(-sum(A) + now * 2)
    A.remove(now)
    while A:
        nxt = A.pop()
        print(now, nxt)
        now -= nxt
else:
    print(sum([abs(i) for i in A]))
    minus = []
    plus = []
    for a in A:
        if a > 0:
            plus += [a]
        elif a < 0:
            minus += [a]
        else:
            if not plus:
                plus += [a]
            else:
                minus += [a]
    ret = minus[0]
    for j in range(1, len(plus)):
        print(ret, plus[j])
        ret -= plus[j]
    print(plus[0], ret)
    ret = plus[0] - ret
    for k in range(1, len(minus)):
        print(ret, minus[k])
        ret -= minus[k]

Submission status: Accepted

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

XY=[]
left,right=A[0],A[-1]
for i in range(1,n-1):
    num=A[i]
    if num<0:
        XY.append([right,num])
        right -=num
    else:
        XY.append([left,num])
        left -=num
XY.append([right,left])
print(right-left)
for x,y in XY:print(x,y)

Submission status: Accepted

Solution code:
n= int(input())
a = list(map(int,input().split()))
xy = []
xyap = xy.append
ap = max(a)
a.remove(ap)
am = min(a)
a.remove(am)
for i in a:
  if i>0:
    xyap((am,i))
    am -= i
  else:
    xyap((ap,i))
    ap -= i
xyap((ap,am))
print(ap-am)
for i in xy:
  print(*i)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    N = int(rl())
    A = list(map(int, rl().split()))
    A.sort()
    
    ope = [[] for _ in range(N - 1)]
    for i in range(N - 2):
        if 0 <= A[i + 1]:
            ope[i] = [A[0], A[i + 1]]
            A[0] -= A[i + 1]
        else:
            ope[i] = [A[-1], A[i + 1]]
            A[-1] -= A[i + 1]
    ope[N - 2] = [A[-1], A[0]]
    
    ans = A[-1] - A[0]
    print(ans)
    for x, y in ope:
        print(x, y)


if __name__ == '__main__':
    solve()

Submission status: Accepted

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

A.sort()
from collections import deque
d = deque(A)
ans = []
r = d.pop()
for i in range(N-1):
  l = d.popleft()
  if i < N-2:
    nex = d.pop()
  else:
    nex = -1
  if nex>=0:
    ans.append((min(l,r),max(l,r)))
    d.appendleft((-1)*abs(l-r))
  else:
    ans.append((max(l,r),min(l,r)))
    d.appendleft(abs(l-r))
  r = nex
print(d.pop())
for a in ans:
  print(*a,sep=' ')

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int,input().split()))
A.sort()
ans = []

# 全て正
if min(A)>=0:
    print(sum(A)-2*A[0])
    for i in range(n):
        if i==0:
            x = A[i]
        elif i==n-1:
            print(A[i], x)
        else:
            print(x, A[i])
            x -= A[i]

# 全て負
elif max(A)<=0:
    A = A[::-1]
    print(sum(A)*(-1)+2*A[0])
    for i in range(n):
        if i==0:
            x = A[i]
        else:
            print(x, A[i])
            x -= A[i]

# 正負
else:
    m,p = [], []
    for a in A:
        if a<0:
            m.append(a)
        else:
            p.append(a)
    print(sum(p)-sum(m))
    m.sort()
    p.sort()
    x = m[0]
    for i in range(len(p)-1):
        print(x, p[i])
        x -= p[i]
    else:
        print(p[-1], x)
        x = p[-1] - x
        
    for j in range(1, len(m)):
        print(x, m[j])
        x -= m[j]

Submission status: Accepted

Solution code:
# coding: utf-8
N=int(input())
A=list(map(int,input().split()))

A.sort()

MIN=A[0]
MAX=A[-1]

if MIN>0:
    print(sum(A)-MIN*2)
elif MAX<0:
    print(-(sum(A)-MAX*2))
else:
    M=0
    for i in range(N):
        M+=abs(A[i])
    print(M)
    

for i in range(1,N-1):
    if A[i]<0:
        print(MAX,A[i])
        MAX-=A[i]
    else:
        print(MIN,A[i])
        MIN-=A[i]

print(MAX,MIN)

Submission status: Accepted

Solution code:
from collections import *
from heapq import *
from itertools import *
from fractions import gcd
import sys
from decimal import *
import copy
from bisect import *
input=lambda :sys.stdin.readline().rstrip()
N=int(input())
A=list(map(int,input().split()))
if N==2:
    A.sort()
    print(A[1]-A[0])
    print(A[1],A[0])
else:
    plus= [i for i in A if i>=0]
    minus=[i for i in A if i<0]

    plus.sort(reverse=True)
    minus.sort()
    lst=[]
    if not minus:
        a=plus.pop()
        b=plus.pop()
        minus.append(a-b)
        lst.append([a,b])
    if not plus:
        a=minus.pop()
        b=minus.pop()
        plus.append(a-b)
        lst.append([a,b])

    while len(plus)>1:
        a=plus.pop()
        lst.append([minus[0],a])
        minus[0]-=a

    while len(minus)>1:
        a=minus.pop()
        lst.append([plus[0],a])
        plus[0]-=a

    print(plus[0]-minus[0])
    lst.append([plus[0],minus[0]])
    for a,b in lst:
        print(a,b)