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:
from heapq import heappop,heappush
n = int(input())
A = sorted(list(map(int,input().split())))
P = []
M = []
if n == 2:
    print(A[1]-A[0])
    print(A[1],A[0])
    exit()
def move():
    while len(P)!= 1:
        mm = heappop(M)
        pp = heappop(P)
        print(mm,pp)
        heappush(M,mm-pp)
    while len(M) != 0:
        mm = heappop(M)
        pp = heappop(P)
        print(pp,mm)
        heappush(P,pp-mm)
for a in A:
    if a>=0:
        P.append(a)
    else:
        M.append(a)

if A[-1]>=0 and A[0]<0:
    print(sum(abs(a) for a in A))
    while len(P)!= 1:
        mm = heappop(M)
        pp = heappop(P)
        print(mm,pp)
        heappush(M,mm-pp)
    while len(M) != 0:
        mm = heappop(M)
        pp = heappop(P)
        print(pp,mm)
        heappush(P,pp-mm)
elif A[0]>=0:
    print(sum(A)-min(A)*2)
    mm = heappop(P)
    pp = heappop(P)
    print(mm,pp)
    heappush(M,mm-pp)
    while len(P)!= 1:
        mm = heappop(M)
        pp = heappop(P)
        print(mm,pp)
        heappush(M,mm-pp)
    while len(M) != 0:
        mm = heappop(M)
        pp = heappop(P)
        print(pp,mm)
        heappush(P,pp-mm)
else:
    print(sum(abs(a) for a in A)+max(A)*2)
    mm = M[-1]
    pp = M[-2]
    print(mm,pp)
    M = M[:-2]
    heappush(P,mm-pp)
    while len(P)!= 1:
        mm = heappop(M)
        pp = heappop(P)
        print(mm,pp)
        heappush(M,mm-pp)
    while len(M) != 0:
        mm = heappop(M)
        pp = heappop(P)
        print(pp,mm)
        heappush(P,pp-mm)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
A = sorted(A,reverse=True)
Y, X = [A[0]], [A[-1]]
for i in range(1, N-1):
    if A[i] >= 0:
        Y.append(A[i])
    else:
        X.append(A[i])
res = []

for i in range(len(Y)-1,0,-1) :
    res.append([X[-1],Y[i]])
    X[-1] -= Y[i]

for i in range(len(X)-1,-1,-1) :
    res.append([Y[0],X[i]])
    Y[0] -= X[i]

print(Y[0])
for r in res :
    print(*r)

Submission status: Accepted

Solution code:
import bisect

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

ans = []

A = sorted(A)

if N == 2 :
    ans.append([A[1],A[0]])
    calc = A[1] - A[0]

else :
    ind = bisect.bisect_left(A,0)

    X = A[:ind]
    Y = A[ind:]
    
    if len(X) == 0 :
        ans.append([Y[0],Y[1]])
        X.append(Y.pop(0)-Y.pop(0))
    
    elif len(Y) == 0 :
        ans.append([X[-1],X[-2]])
        Y.append(X.pop(-1)-X.pop(-1))
    
    while len(Y) != 1 :
        ans.append([X[-1],Y[0]])
        X[-1] -= Y.pop(0)
    
    while len(X) :
        ans.append([Y[0],X[-1]])
        Y[0] -= X.pop(-1)
    
    calc = Y.pop(0)

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

Submission status: Accepted

Solution code:
n = int(input())
ai = [int(x) for x in input().split()]

ai.sort()

temp = [abs(x) for x in ai[1:-1]]

o1 = -ai[0] + sum(temp) + ai[-1]

print(o1)

temp1 = ai.pop(-1)
num_p = sum(x >= 0 for x in ai)
if num_p == len(ai):
  num_p -= 1
for i in range(num_p):
  temp2 = ai.pop(-1)
  print(ai[0], temp2)
  ai[0] -= temp2

for i in range(len(ai)):
  temp2 = ai.pop(0)
  print(temp1, temp2)
  temp1 -= temp2

Submission status: Accepted

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

process = []
p_seed = a.pop(0)
n_seed = a.pop(-1)
for e in a:
    if e >= 0:
        process.append((n_seed, e))
        n_seed -= e
    else:
        process.append((p_seed, e))
        p_seed -= e
process.append((p_seed, n_seed))
m = p_seed - n_seed
print(m)
for x, y in process:
    print(str(x) + ' ' + str(y))

Submission status: Accepted

Solution code:
n = int(input())
a = input().split()
for i in range(len(a)):
    a[i]=int(a[i])
# print(a)
a.sort()
# print(a)
# #両端をとっておく
hashi1 = a[0]
hashi2 = a[-1]
a.remove(a[0])
a.remove(a[-1])
# print(a)
minus_list = []
plus_list = []
printlist = []
for i in range(len(a)):
    if a[i]>0:
        plus_list.append(a[i])
    else:
        minus_list.append(a[i])
# print(minus_list)
# print(plus_list)
for j in range(len(minus_list)):
    printlist.append(hashi2)
    printlist.append(minus_list[j])
    hashi2 = hashi2-minus_list[j]
    
for l in range(len(plus_list)):
    printlist.append(hashi1)
    printlist.append(plus_list[l])
    hashi1 = hashi1 - plus_list[l]
    
printlist.append(hashi2)
printlist.append(hashi1)
print(hashi2-hashi1)
# print(printlist)
for n in range(0,len(printlist),2):
    print(printlist[n],printlist[n+1])

Submission status: Accepted

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

a.sort()

now = 0

ans = []

for i in range(n-2):
    if a[i+1] > 0:
        ans.append([a[0], a[i+1]])
        a[0] = a[0] - a[i+1]
    else:
        ans.append([a[n-1], a[i+1]])
        a[n-1] = a[n-1] - a[i+1]

ans.append([a[n-1],a[0]])
print(a[n-1]-a[0])

for i in ans:
    print(i[0],i[1])

Submission status: Accepted

Solution code:
n,*a=map(int,open(0).read().split())
a.sort()
l=[]
if a[-1]>=0>a[0]:
  a,b=[t for t in a if t>=0],[t for t in a if t<0]
  c,y=a.pop(),b.pop()
  while b:
    t=b.pop()
    l.append((c,t))
    c-=t
  while a:
    t=a.pop()
    l.append((y,t))
    y-=t
  l.append((c,y))
  c-=y
elif a[0]>=0:
  s,*a,c=a
  while a:
    t=a.pop()
    l.append((s,t))
    s-=t
  l.append((c,s))
  c-=s
else:
  *a,c=a
  while a:
    t=a.pop()
    l.append((c,t))
    c-=t
print(c)
for t in l:print(*t)

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
A = deque(maxlen=N)
x = [int(e) for e in input().split()]
x.sort()
for a in x:
    A.append(a)
l = []
for i in range(N - 2):
    (a, b, c) = (A[0], A[1], A[-1])
    if b < 0:
        l.append((c, a))
        A[-1] = c - a
    else:
        l.append((a, b))
        A[1] = a - b
    A.popleft()
print(A[1] - A[0])
l.append((A[1], A[0]))
for v in l:
    print(v[0], v[1])

Submission status: Accepted

Solution code:
from collections import deque

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

# A[cut-1] < 0 and A[cut] >= 0
cut = 0
while cut < N and A[cut] < 0:
    cut += 1

if cut == 0:
    M = sum(A[1:]) - A[0]
    print(M)
    pair = [A[0], A[N-1]]
    for i in range(N-2):
        print(' '.join(map(str, pair)))
        pair = [pair[0] - pair[1], A[N-i-2]]
    pair.reverse()
    print(' '.join(map(str, pair)))

elif cut == N:
    M = A[-1] - sum(A[:N-1])
    print(M)
    pair = [A[N-1], A[0]]
    for i in range(N-2):
        print(' '.join(map(str, pair)))
        pair = [pair[0] - pair[1], A[i+1]]
    print(' '.join(map(str, pair)))

else:
    M = sum(A[cut:]) - sum(A[:cut])
    print(M)

    B = deque(A[cut:]) # Aの正の部分
    C = deque(A[:cut]) # Aの負の部分

    while len(B) != 1:
        pair = [C[-1], B[-1]]
        print(' '.join(map(str, pair)))
        b = B.pop()
        C[-1] = C[-1] - b
    
    b = B.pop()

    while len(C) != 0:
        pair = [b, C[0]]
        print(' '.join(map(str, pair)))
        c = C.popleft()
        b = b - c

Submission status: Accepted

Solution code:
def successive_subtraction(N, A, i=1, l=[]):
    mx = max(A)
    mn = min(A)
    if i == N - 1:
        print(mx - mn)
        return l
    l.append((mn, mx))
    A.remove(mn)
    A.remove(mx)
    A.append(mn - mx)
    return successive_subtraction(N, A, i + 1, l)

N = int(input())
A = [int(e) for e in input().split()]
A.sort()
l = []
for i in range(N - 2):
    (a, b, c) = (A[0], A[1], A[-1])
    if b < 0:
        l.append((c, a))
        A[-1] = c - a
    else:
        l.append((a, b))
        A[1] = a - b
    A.pop(0)
print(A[1] - A[0])
l.append((A[1], A[0]))
for v in l:
    print(v[0], v[1])

Submission status: Accepted

Solution code:
import bisect
n=int(input())
a=[int(i) for i in input().split()]
a.sort()
ans=[]
x=bisect.bisect_left(a, 0)
m=a[:x]
p=a[x:]

if n==2 and len(p)==2:
    print(p[1]-p[0])
    print(p[1],p[0])
    
    exit()
if m==[]:
    m+=[p[0]-p[-1]]
    ans+=[[p[0],p[-1]]]
    del p[0]
    del p[-1]

if p==[]:
    p+=[m[-1]-m[0]]
    ans+=[[m[-1],m[0]]]
    del m[-1]
    del m[0]

while len(p)!=1:

    m+=[m[0]-p[0]]
    ans+=[[m[0],p[0]]]
    del p[0]
    del m[0]
cnt=p[0]
for i in m:
    ans+=[[cnt,i]]
    cnt-=i
print(cnt)
for i,j in ans:print(i,j)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
N=int(input())
A=list(map(int,input().split()))
A.sort()
ans=[]

if A[0]>0:
    num=A[0]
    for i in range(1,N-1):
        ans.append([num,A[i]])
        num-=A[i]
    ans.append([A[-1],num])
    print(A[-1]-num)
    for i in range(len(ans)):
        print(ans[i][0],ans[i][1])
elif A[-1]<0:
    A.sort(reverse=True)
    num=A[0]
    for i in range(1,N):
        ans.append([num,A[i]])
        num-=A[i]
    print(num)
    for i in range(len(ans)):
        print(ans[i][0],ans[i][1])
else:
    M=A[-1]
    m=A[0]
    for i in range(1,N-1):
        if A[i]<0:
            ans.append([M,A[i]])
            M-=A[i]
        else:
            ans.append([m,A[i]])
            m-=A[i]
    ans.append([M,m])
    print(M-m)
    for i in range(len(ans)):
        print(ans[i][0],ans[i][1])

Submission status: Accepted

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

if A[0]>0:
    num=A[0]
    for i in range(1,N-1):
        ans.append([num,A[i]])
        num-=A[i]
    ans.append([A[-1],num])
    print(A[-1]-num)
    for i in range(len(ans)):
        print(ans[i][0],ans[i][1])
elif A[-1]<0:
    A.sort(reverse=True)
    num=A[0]
    for i in range(1,N):
        ans.append([num,A[i]])
        num-=A[i]
    print(num)
    for i in range(len(ans)):
        print(ans[i][0],ans[i][1])
else:
    M=A[-1]
    m=A[0]
    for i in range(1,N-1):
        if A[i]<0:
            ans.append([M,A[i]])
            M-=A[i]
        else:
            ans.append([m,A[i]])
            m-=A[i]
    ans.append([M,m])
    print(M-m)
    for i in range(len(ans)):
        print(ans[i][0],ans[i][1])

Submission status: Accepted

Solution code:
N = int(input())
A = [int(_) for _ in input().split()]

mxs = sorted(x for x in A if x < 0)
pxs = sorted(x for x in A if x >= 0)

if len(mxs) == 0:
    mxs = [pxs[0]]
    pxs = pxs[1:]

if len(pxs) == 0:
    pxs = [mxs[-1]]
    mxs = mxs[:-1]

#print(mxs, pxs)

result = sum(pxs) - sum(mxs)
print(result)

if len(pxs) == 1:
    for y in mxs:
        print(pxs[0], y)
        pxs[0] -= y
else:
    for y in pxs[:-1]:
        print(mxs[0], y)
        mxs[0] -= y
    print(pxs[-1], mxs[0])
    pxs[-1] -= mxs[0]
    for y in mxs[1:]:
        print(pxs[-1], y)
        pxs[-1] -= y

#for i in range

Submission status: Accepted

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

for i in range(1,n-1):
  if a[i] < 0:
    anslist.append([a[-1], a[i]])
    a[-1] -= a[i]
  else:
    anslist.append([a[0], a[i]])
    a[0] -= a[i]
anslist.append([a[-1], a[0]])
ans = a[-1]-a[0]
print(ans)
for i in range(len(anslist)):
  print(anslist[i][0], anslist[i][1])

Submission status: Accepted

Solution code:
N = int(input())
l = list(map(int,input().split()))
l.sort()
sousa = []
next_m = l[0]
next_p = l[N-1]
for i in range(1,N-1):
    if l[i] > 0:
        sousa.append([next_m,l[i]])
        next_m -= l[i]
    else:
        sousa.append([next_p,l[i]])
        next_p -= l[i]
ans = next_p - next_m
print(ans)
sousa.append([next_p,next_m])
for i in range(N-1):
    print(str(sousa[i][0])+" "+str(sousa[i][1]))

Submission status: Accepted

Solution code:
import bisect
N = int(input())
A = sorted([int(_) for _ in input().split()])
i = bisect.bisect_left(A, 0)
if i == N:
    i -= 2
elif i:
    i -= 1
now = A[i]
ans = []
for a in A[i + 1:N - 1]:
    ans += [[now, a]]
    now -= a
ans += [[A[N - 1], now]]
now = A[N - 1] - now
for a in A[:i]:
    ans += [[now, a]]
    now -= a
print(now)
[print(*xy) for xy in ans]

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
inpt = input()
A = [int(a) for a in inpt.split()]
A = deque(sorted(A))
outputs = []
negative = 0
positive = 0

for a in A:
    if a > 0:
        positive += 1
    elif a <= 0:
        negative += 1
for i in range(N-1):
    maxA = A[-1]
    minA = A[0]
    if minA>0:
        positive -= 1
    else:
        negative -= 1
    if maxA>0:
        positive -= 1
    else:
        negative -= 1
    A.pop()
    A.popleft()
    if positive > negative:
        newnum = minA-maxA
        A.appendleft(newnum)
        outputs.append(str(minA)+" "+str(maxA))
    else:
        newnum = maxA - minA
        A.append(newnum)
        outputs.append(str(maxA)+" "+str(minA))
    if newnum > 0:
        positive += 1
    else:
        negative += 1

print(A[0])
for output in outputs:
    print(output)

Submission status: Accepted

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

p,m = [],[]
p_total = 0
m_total = 0
p_max,p_min = 0,10**10
m_max,m_min = -10**10,0
p_count,p_min_idx,p_max_idx = 0,0,0
m_count,m_min_idx,m_max_idx = 0,0,0
for a in A:
    if a < 0:
        if m_min > a:
            m_min = a
            m_min_idx = m_count
        if m_max < a:
            m_max = a
            m_max_idx = m_count
        m_total += a
        m.append(a)
        m_count += 1
    else:
        if p_min > a:
            p_min = a
            p_min_idx = p_count
        if p_max < a:
            p_max = a
            p_max_idx = p_count
        p_total += a
        p.append(a)
        p_count += 1

if len(m) == 0:
    print(p_total-2*p_min)
    for i in range(len(p)-1):
        if i != p_min_idx:
            print(p[p_min_idx],p[i])
            p[p_min_idx] -= p[i]
    print(p[-1],p[p_min_idx])

elif len(p) == 0:
    print(2*m_max-m_total)
    for i in range(len(m)-1):
        if i != m_max_idx:
            print(m[m_max_idx],m[i])
            m[m_max_idx] -= m[i]
    print(m[m_max_idx],m[-1])

else:
    print(p_total-m_total)
    for i,v in enumerate(p):
        if i != p_max_idx:
            print(m[0], v)
            m[0] -= v
    for i in range(len(m)):
        print(p[p_max_idx],m[i])
        p[p_max_idx] -= m[i]

Submission status: Accepted

Solution code:
import sys
import itertools
import collections
sys.setrecursionlimit(10**7)
def lmi(): return list(map(int, input().split()))

n = int(input())
a = lmi()
a.sort()
b = [-1 for i in range(n)]
b[-1] = 1
for i in range(1, n-1):
    if a[i] > 0:
        b[i] = 1


print(sum([a[i]*b[i] for i in range(n)]))

x = a[0]
for y in [a[i] for i in range(n-1) if b[i] == 1]:
    print(x, y)
    x -= y

y = x
x = a[-1]
print(x, y)
x -= y
for y in [a[i] for i in range(1,n-1) if b[i] == -1]:
    print(x, y)
    x -= y

Submission status: Accepted

Solution code:
import bisect
import os
from collections import Counter, deque
from fractions import gcd
from functools import lru_cache
from functools import reduce
import functools
import heapq
import itertools
import math
import numpy as np
import re
import string
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))

plus = []
minus = []

for a in A:
    if a >= 0:
        plus.append(a)
    else:
        minus.append(a)
if not plus:
    mm = max(minus)
    plus.append(mm)
    minus.remove(mm)
if not minus:
    mp = min(plus)
    minus.append(mp)
    plus.remove(mp)

hist = []
x = minus.pop()
while len(plus) > 1:
    y = plus.pop()
    hist.append((x, y))
    x = x - y
minus.append(x)

x = plus.pop()
while len(minus) > 1:
    y = minus.pop()
    hist.append((x, y))
    x = x - y
y = minus.pop()
hist.append((x, y))

print(x - y)
for h in hist:
    print(*h)

Submission status: Accepted

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

leftest_val = A[0]
rightest_val = A[-1]
left_idx = 1
right_idx = N - 2
history = []
for i in range(N - 1):
    left_val = A[left_idx]
    right_val = A[right_idx]
    if i == N - 2:
        history.append("{} {}".format(rightest_val, leftest_val))
        print(rightest_val - leftest_val)
    elif left_val < 0:
        history.append("{} {}".format(rightest_val, left_val))
        rightest_val -= left_val
        left_idx += 1
    else:
        history.append("{} {}".format(leftest_val, right_val))
        leftest_val -= right_val
        right_idx -= 1

for h in history:
    print(h)

Submission status: Accepted

Solution code:
N = int(input())
A = sorted([int(a) for a in input().split()])
print(A[-1]-A[0]+sum([abs(a) for a in A[1:-1]]))

p = A[-1]
for i in range(N-1):
    a, b = max(p, A[i]), min(p, A[i])
    if i == N-2 or A[i+1] < 0:
        print(a, b)
        p = a - b
    else:
        print(b, a)
        p = b - a

Submission status: Accepted

Solution code:
n = int(input())
a = [int(x) for x in input().split()]
a.sort(reverse=True)
add, sub = [a[0]], [a[-1]]
for i in range(1, n-1):
    if a[i] >= 0:
        add.append(a[i])
    else:
        sub.append(a[i])
res = []
it = len(add)-1
while it > 0:
    res.append([sub[-1],add[it]])
    sub[-1] -= add[it]
    it -= 1
it = len(sub)-1
while it >= 0:
    res.append([add[0],sub[it]])
    add[0] -= sub[it]
    it -= 1
print(add[0])
print("\n".join([" ".join(map(str,x)) for x in res]))

Submission status: Accepted

Solution code:
import bisect
n = int(input())
a = list(map(int, input().split()))

a.sort()
ope = []
max_num = a[-1]
min_num = a[0]
p = bisect.bisect_left(a, 0)
for i in range(1, min(p, n - 1)):
    ope.append([max_num, a[i]])
    max_num -= a[i]
for i in range(max(p, 1), n - 1):
    ope.append([min_num, a[i]])
    min_num -= a[i]
ope.append([max_num, min_num])
print(max_num - min_num)
for i in range(n - 1):
    print(" ".join(map(str, ope[i])))

Submission status: Accepted

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

from collections import deque

deq = deque(a_list)
res = []
while len(deq) > 2:
    min_num = deq.popleft()
    max_num = deq.pop()
    if min_num < 0 and max_num > 0:
        ne = deq.pop()
        if ne >= 0:
            res.append((min_num, ne))
            min_num -= ne
            deq.appendleft(min_num)
            deq.append(max_num)
        else:
            res.append((max_num, ne))
            max_num -= ne
            deq.append(max_num)
            deq.appendleft(min_num)
    else:
        if max_num <= 0:
            res.append((max_num, min_num))
            max_num = max_num - min_num
            deq.append(max_num)
        else:
            res.append((min_num, max_num))
            min_num = min_num - max_num
            deq.appendleft(min_num)

tmp1 = deq[0]
tmp2 = deq[1]
res.append((max(tmp1, tmp2), min(tmp2, tmp1)))
ans = max(tmp1, tmp2) - min(tmp2, tmp1)
print(ans)
for x,y in res:
    print(x, y)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(s) for s in input().split(' ')]
A.sort()
print(A[N - 1] + sum([abs(a) for a in A[1:N - 1]]) - A[0])
answer = ''
for i in range(1, len(A) - 1):
    if(A[i] > 0):
        answer += "{} {}\n".format(A[0], A[i])
        A[0] -= A[i]
    else:
        answer += "{} {}\n".format(A[N - 1], A[i])
        A[N - 1] -= A[i]
answer += "{} {}\n".format(A[N - 1], A[0])
print(answer)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
A=[a[0]]
x=0
sum=sum(a)
sumL=-9999999999
if n==2:
  print(max(a)-min(a))
  print(max(a),min(a))
else:
  for i in range(1,n):
    A.append(A[i-1]+a[i])
  for i in range(1,n):
    if sumL<-A[i-1]+sum-A[i-1]:
      sumL=-A[i-1]+sum-A[i-1]
      x=i
  print(sumL)
  L1=a[0:x]
  L2=a[x:n]

  if x!=1:
    print(L2[0],L1[0])
    z=L2[0]-L1[0]
    for i in range(1,x-1):
      print(z,L1[i])
      z=z-L1[i]
  else:
    z=L2[0]

  if x!=n-1:
    print(L1[x-1],L2[1])
    y=L1[x-1]-L2[1]
    for i in range(2,len(L2)):
      print(y,L2[i])
      y=y-L2[i]
  else:
    y=L1[len(L1)-1]

  print(z,y)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from collections import deque

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

positives = deque(sorted(a))
negatives = deque([positives.popleft()])
while len(positives) > 1:
    if positives[0] < 0:
        negatives.append(positives.popleft())
    else:
        break

# print M
print(sum(positives) - sum(negatives))

while len(positives) > 1:
    y = positives.popleft()
    x = negatives.pop()
    print(x, y)
    negatives.append(x - y)

x = positives.popleft()

while len(negatives) > 0:
    y = negatives.pop()
    print(x, y)
    x = x - y

Submission status: Accepted

Solution code:
###template###
import sys
def input(): return sys.stdin.readline().rstrip()
def mi(): return map(int, input().split())
###template###

N = int(input())
As = list(mi())

TL = [[], [], []]
#[0] : zeroList
#[1] : minusList
#[2] : plusList

for a in As:
  if a == 0: TL[0].append(a)
  elif a < 0: TL[1].append(a)
  else: TL[2].append(a)

#print(TL)

ans = 0
printlist = []
#全てxxの場合（3パターン）
if len(TL[0])==N: #全てゼロの場合
  print(0)
  for i in range(N-1):
    print(0, 0)
  exit()
elif len(TL[1])==N: #全てminusの場合
  TL[1] = sorted(TL[1], reverse=True) #降順に並べる（-値の低いものから）
  printlist.append((TL[1][0],TL[1][1])) #痛みを最小に
  hand = TL[1][0]-TL[1][1] #これでプラスになった
  idx = 2
  while idx < N:
    printlist.append((hand, TL[1][idx]))
    hand -= TL[1][idx]
    idx += 1
  ans = hand
  #答えを出力する
  print(ans)
  for x, y in printlist:
    print(x, y)
  exit()
elif len(TL[2])==N: #全てplusの場合
  TL[2] = sorted(TL[2]) #昇順に並べる
  printlist.append((TL[2][0],TL[2][1])) #痛みを最小に
  hand = TL[2][0]-TL[2][1] #これで-になった
  idx = 2
  while idx < N-1:
    printlist.append((hand, TL[2][idx]))
    hand -= TL[2][idx]
    idx += 1
  #idx==N-1
  printlist.append((TL[2][idx], hand))
  hand = TL[2][idx]-hand
  ans = hand
  #答えを出力する
  print(ans)
  for x, y in printlist:
    print(x, y)
  exit()

# ここから先は、0,-,+のうちどれか2つはあるので、全て集合させられる
# ただし、0と-が1つずつ、0と+が1つずつというパターンは別途処理する必要がある
# 以下、そのパターンを処理
if len(TL[0])==1 and len(TL[1])==1:
  #0と-が1つずつ。0から-を引いて終わり
  left, right = TL[0].pop(), TL[1].pop()
  print(left-right)
  print(left, right)
  exit()
elif len(TL[0])==1 and len(TL[2])==1:
  #0と+が1つずつ。+から0を引いて終わり
  left, right = TL[2].pop(), TL[0].pop()
  print(left-right)
  print(left, right)
  exit()

# ここから先は、0,-,+のうちどれか2つはあり、前述のパターンも無いので、全て集合させられるし、最後に-と+が1つずつという最終処理パターンに持っていける
# よって一律のループ処理でOK
# 0が0個、+が1つ、-が1つになったら処理を抜け、最終手順に向かう
# 最初からそうなら、while文は実行されないのでＯＫ
# また、全てを集合させられる＝取り出す順番はどうでもいいので、高速化のため全てpop()で取り出していく
while not (len(TL[0])==0 and len(TL[1])==1 and len(TL[2])==1):
  left = 0
  right = 0
  if len(TL[0])>=1:
    #0があれば、まず0を消化する
    if len(TL[1])==0: #-がなければ、0を使って-を作る
      left, right = TL[0].pop(), TL[2].pop()
      printlist.append((left, right))
      TL[1].append(left-right)
    elif len(TL[2])==0: #+がなければ、0を使って+を作る
      left, right = TL[0].pop(), TL[1].pop()
      printlist.append((left, right))
      TL[2].append(left-right)
    else: #-も+もあるなら消化するだけなので、どっちでもいいが、-で消化する
      left, right = TL[1].pop(), TL[0].pop()
      printlist.append((left, right))
      TL[1].append(left-right)
    continue
  #ここからは、0がなくなったパターン
  #0がなくなったということは、+と-は必ず両方あることになる
  #またwhile文の条件から、「どちらも1つしかない」ということはありえない
  if len(TL[1])>=len(TL[2]): #-のが多い、もしくは同じ（もちろん2:2以上）
    left, right = TL[2].pop(), TL[1].pop()
    printlist.append((left, right))
    TL[2].append(left-right)
  else: #+のが多いパターン
    left, right = TL[1].pop(), TL[2].pop()
    printlist.append((left, right))
    TL[1].append(left-right)

# 最後に、プラス-マイナスでプラス数字を作って終わり
left, right = TL[2].pop(), TL[1].pop()
printlist.append((left, right))
ans = left-right


#答えを出力する
print(ans)
for x, y in printlist:
  print(x, y)

Submission status: Accepted

Solution code:
def c(N, A):
    A.sort()
    maximum = A.pop()
    minimum = A.pop(0)
    operation = []
    for a in A:
        if a >= 0:
            operation.append('{} {}'.format(minimum, a))
            minimum -= a
        else:
            operation.append('{} {}'.format(maximum, a))
            maximum -= a
    operation.append('{} {}'.format(maximum, minimum))
    return str(maximum - minimum) + '\n' + '\n'.join(operation)

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

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n = I()
    a = sorted(LI())
    i = 0
    if a[0] >= 0:
        i = 0
    elif a[-1] <= 0:
        i = n - 2
    else:
        i = bisect.bisect_right(a,0) - 1

    r = []
    j = i + 1
    # print(a,i,j)
    for k in range(i-1,-1,-1):
        r.append('{} {}'.format(a[j], a[k]))
        a[j] -= a[k]
    for k in range(j+1,n):
        r.append('{} {}'.format(a[i], a[k]))
        a[i] -= a[k]
    r.append('{} {}'.format(a[j],a[i]))

    return '{}\n{}'.format(a[j]-a[i], JA(r, '\n'))


print(main())

Submission status: Accepted

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

## 2個しかない場合
if N == 2:
  A.sort()
  print(A[-1] - A[0])
  print(A[-1], A[0])
  exit()

## 全部非負整数の場合
if sum(a < 0 for a in A) == 0:
  A.sort()
  solver = []
  var = A[0]
  for i in range(1,N-1):
    solver.append((var, A[i]))
    var = var - A[i]
  else:
    solver.append((A[-1], var))
    var = A[-1] - var

  print(var)
  for i in range(len(solver)):
    print(solver[i][0], solver[i][1])
  exit()
  
## 全部非正整数の場合
if sum(a > 0 for a in A) == 0:
  A.sort(reverse=True)
  solver = []
  var = A[0]
  for i in range(1,N):
    solver.append((var, A[i]))
    var = var - A[i]

  print(var)
  for i in range(len(solver)):
    print(solver[i][0], solver[i][1])
  exit()
  
## 正整数も負整数もある場合
A.sort()
n_nega = sum(a < 0 for a in A)
n_posi = sum(a > 0 for a in A)
solver = []
var = A[n_nega-1]
if n_posi > 1:
  for i in range(n_nega,N-1):
    solver.append((var, A[i]))
    var = var - A[i]
solver.append((A[-1], var))
var = A[-1] - var
if n_nega > 1:
  for i in range(n_nega-1):
    solver.append((var, A[i]))
    var = var - A[i]

print(var)
for i in range(len(solver)):
  print(solver[i][0], solver[i][1])

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
A = list(map(int, input().split()))
A.sort(reverse = True)
p = sum(1 for a in A if a > 0)
if A[-1] > 0:
    print(sum(A[:-1]) - A[-1])
    k = A[-1]
    for a in A[:-2]:
        print(k, a)
        k -= a
    print(A[-2], k)

elif A[0] < 0:
    print(A[0] - sum(A[1:]))
    k = A[0]
    for a in A[1:]:
        print(k, a)
        k -= a
else:
    print(sum(abs(a) for a in A))
    A = deque(A)
    k = A.pop()
    for _ in range(p-1):
        t = A.popleft()
        print(k, t)
        k -= t
    t = A.popleft()
    print(t, k)
    t -= k
    for a in A:
        print(t, a)
        t -= a

Submission status: Accepted

Solution code:
N = int(input())
*A, = map(int, input().split())
INF = 10**9
p = q = 0
for i, a in enumerate(A):
    if a > 0:
        p += 1
    elif a < 0:
        q += 1

def solve(s, t):
    R = []
    i = A.index(s)
    if s == t:
        j = A.index(t, i+1)
    else:
        j = A.index(t)
    for k, a in enumerate(A):
        if i == k or j == k:
            continue
        if a >= 0:
            R.append("%d %d\n" % (s, a))
            s -= a
    for k, a in enumerate(A):
        if i == k or j == k:
            continue
        if a < 0:
            R.append("%d %d\n" % (t, a))
            t -= a
    R.append("%d %d\n" % (t, s))
    t -= s
    return t, R
ans = 0
if p > 0 and q > 0:
    s = t = 0
    for a in A:
        if a > 0:
            t = a
        elif a < 0:
            s = a
    ans, R = solve(s, t)
elif p > 0:
    A.sort()
    ans, R = solve(A[0], A[1])
elif q > 0:
    A.sort()
    ans, R = solve(A[-2], A[-1])
else:
    R = ["0 0\n"]*(N-1)
print(ans)
print("".join(R))

Submission status: Accepted

Solution code:
import sys
from collections import deque  # 双方向キュー
from collections import defaultdict  # 初期化済み辞書
from heapq import heapify, heappush, heappop, heappushpop  # プライオリティキュー
from bisect import bisect_left, bisect_right  # 二分探索
#import numpy as np  # 1.8.2
#import scipy  # 0.13.3

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    N = i2n()
    A = i2nn()
    A.sort()
    a0 = A[0]
    a3 = A[N-1]
    A12 = A[1:N-1]
    iz = bisect_left(A12, 0)
    A1 = A12[:iz]
    A2 = A12[iz:]

    logs = []
    def logging(x, y):
        logs.append('%d %d' % (x, y))
        return x - y
    x = a0
    for y in A2:
        x = logging(x, y)
    y = x
    x = a3
    x = logging(x, y)
    for y in A1:
        x = logging(x, y)
    print(x)
    for log in logs:
        print(log)

main()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
ps = []
ms = []

cnt = 0
ans = 0
anss = []
for e in a:
  if e<0:
    cnt += 1
    ms.append(e)
  else:
    ps.append(e)
  ans += abs(e)
if cnt==n:
  ans += a[n-1]*2
elif cnt==0:
  ans -= a[0]*2
print(ans)

if cnt==0:
  cur = a[0]
  a.remove(cur)
  for i in range(n-2):
    print(cur, a[i])
    cur = cur-a[i]
  print(a[n-2], cur)
elif cnt==n:
  cur = a[n-1]
  a.remove(cur)
  for i in range(n-1):
    print(cur, a[i])
    cur = cur-a[i]
else:
  while len(ps)>1:
    t = ps.pop()
    print(ms[0], t)
    ms[0] -= t
  while len(ms):
    t = ms.pop()
    print(ps[0], t)
    ps[0] -= t

for e in anss:
  print(*e)