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
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 int(input())
from collections import defaultdict
import bisect

sys.setrecursionlimit(1000000000)

n = SI()
a_list = LI()

a_list =  sorted(a_list)
minus = bisect.bisect_left(a_list, 0)
minus_list = a_list[:minus]

plus_list = a_list[minus:]

ans = 0
p_i = 0
m_i = 0
if minus == 0:
    print(sum(plus_list) - 2*plus_list[0])
    minus_list = plus_list[0:1]
    plus_list = plus_list[1:]


elif minus == n:
    print(-sum(minus_list) + 2*minus_list[-1])
    plus_list = minus_list[-1:]
    minus_list = minus_list[:-1]

else:
    print(sum(plus_list) - sum(minus_list))

ans = minus_list[m_i]
m_i += 1
minus = len(minus_list)
plus = len(plus_list)


while p_i != (plus-1):
    print(ans, plus_list[p_i])
    ans = ans - plus_list[p_i]
    p_i += 1

print(plus_list[p_i], ans)
ans = plus_list[p_i] - ans

while m_i != minus:
    print(ans, minus_list[m_i])
    ans = ans - minus_list[m_i]
    m_i += 1

Submission status: Accepted

Solution code:
from collections import deque
def resolve():
    N = int(input())
    As = list(map(int, input().split(" ")))
    pos = []
    neg = []
    for a in As:
        if a >= 0:
            pos.append(a)
        else:
            neg.append(a)
    pos = deque(sorted(pos))
    neg = deque(sorted(neg))
    x = 0
    y = 0
    ops = []
    while True:
        if len(pos) > 0 and len(neg) > 0:
            if len(pos) > len(neg):
                x = neg.popleft()
                y = pos.pop()
            else:
                x = pos.pop()
                y = neg.popleft()
        elif len(pos) > 1 and len(neg) == 0:
                x = pos.popleft()
                y = pos.pop()
        elif len(neg) > 1 and len(pos) == 0:
                x = neg.pop()
                y = neg.popleft()
        else:
            raise Exception("Unreachable?")
        
        ops.append("{} {}".format(x, y))
        xmy = x - y

        if len(pos) == 0 and len(neg) == 0:
            print(xmy)
            break

        if xmy >= 0:
            pos.append(xmy)
        else:
            neg.appendleft(xmy)
        
    [print(i) for i in ops]

if '__main__' == __name__:
    resolve()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
check = -1
for i in range(N):
    if A[i] > 0:    
        break
    check += 1

ans = 0
if 0 <= check < N-1:
    ans = 0
    for i in range(N):
        if i <= check:
            ans -= A[i]
        else:
            ans += A[i]
else:
    ans = abs(sum(A)) - 2*min(abs(A[0]),abs(A[N-1]))
print(ans)
tmp = A[0]
i = 0
while N-i-2 > max(0,check):
    print(str(tmp) + " " + str(A[N-i-1]))
    tmp -= A[N-i-1]
    i += 1
if N-i-2 <= check or N-i-2 == 0:
    print(str(A[N-i-1]) + " " + str(tmp))
    tmp = A[N-i-1] - tmp
    i += 1
while N-i-1 > 0:
    print(str(tmp) + " " + str(A[N-i-1]))
    tmp -= A[N-i-1]
    i += 1

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort()
K = N-1
ans = []
while(K>1):
    if A[K-1] < 0:
        break
    l = A[0] - A[K]
    ans.append(str(A[0])+" "+str(A[K]))
    A[0] = l
    K -= 1
if K == 1:
    ans.append(str(A[1])+" "+str(A[0]))
    print(A[1]-A[0])
else:
    b = A[K]
    for i in range(K-1,0,-1):
        c = A[i]
        ans.append(str(b)+" "+str(c))
        b = b-c
    ans.append(str(b)+" "+str(A[0]))
    print(b-A[0])
for p in ans:
    print(p)

Submission status: Accepted

Solution code:
import sys
# input = sys.stdin.readline
inf = 10 ** 18

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

from collections import deque

A = deque(sorted(A))

pm = N % 2
ans = []
for i in range(N - 2):
    # print("#", list(A))
    A_min = A.popleft()
    A_max = A.pop()
    #
    A_dif = A_max - A_min
    if A_dif - A[0] > A[-1] - (-A_dif):
        ans.append((A_max, A_min))
        A.append(A_max - A_min)
    else:
        ans.append((A_min, A_max))
        A.appendleft(A_min - A_max)
    
ans.append((A[1], A[0]))

print(A[1] - A[0])
for x, y in ans: print(x, y)

Submission status: Accepted

Solution code:
import sys
n = int(input())
a = list(map(int,sys.stdin.readline().split()))
a.sort()
minA = a[0]
mx = a[-1]
ans = []
t = ''
# ans.append(t)
s =0

if a[0]<0 and a[-1]>-1:
    l = a[0]
    h = a[-1]
    for i in range(1,n-1):
        if a[i]<0:
            ans.append([h,a[i]])
            h = h-a[i]
        else:
            ans.append([l,a[i]])
            l = l-a[i]
    ans.append([h,l])
    s = h-l
elif a[0]>-1 and a[-1]>-1:
    c = a[0]-a[-1]
    ans.append([a[0],a[-1] ])
    for i in range(1, n - 2):
        ans.append([c,a[i]])
        c = c - a[i]
    if n>2:
        ans.append([a[-2],c])
        s = a[-2]-c
    else:
        s=c
else:
    c = a[-1]-a[0]
    ans.append([a[-1],a[0]])
    for i in range(1, n-1):
        ans.append([c,a[i]])
        c= c-a[i]
    s=c

print(s)
# print(ans)
for v,w in ans:
    print(v,w)

Submission status: Accepted

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

switch=0
counter=0
mazu=newlist[0]
if newlist[0]>=0:
    seihu=1
else:
    seihu=-1
konzai=0

for nl in newlist:
    if mazu!=nl:
        switch=1

if switch==1:
    wa=0
    list2=[]
    for nl in range(n):
        list2.append([newlist[nl], abs(newlist[nl])])
        if seihu*newlist[nl]<0:
            konzai=1
            numb=nl
            numba=newlist[numb]
    if konzai==1:
        wa=0
        for nl in range(n):
            wa+=abs(newlist[nl])
        print(wa)
        now=newlist[numb]
        #print(newlist)
        newlist.remove(numba)
        #print(newlist)
        #print(now,newlist[0])
        #print('d', now, newlist[0], newlist[1])
        if newlist[1]>0:
            if now>=0:
                #now*=-1
                print(newlist[0], now)
            else:
                #now*=-1
                print(now,newlist[0])
        else:
            if now>=0:
                print(now, newlist[0])
            else:
                print(newlist[0], now)
            
        now=abs(now)+abs(newlist[0])
        if newlist[1]>0:
            now=now*(-1)
        for xi in range(n-3):
            #print('d', now, newlist[xi+1], newlist[xi+2])
            if newlist[xi+2]>0:
                if now>=0:
                    print(newlist[xi+1], now)
                else:
                    print(now, newlist[xi+1])
                now=-abs(now)-abs(newlist[xi+1])
            else:
                if now>=0:
                    print(now, newlist[xi+1])
                else:
                    print(newlist[xi+1], now)
                now=abs(now)+abs(newlist[xi+1])
        if newlist[-1]>0:
            print(newlist[-1], now)
        else:
            print(now, newlist[-1])
    elif seihu==1:
        newlist=sorted(newlist)
        wa=0
        for nl in range(n):
            wa+=abs(newlist[nl])
        wa-=newlist[0]*2
        print(wa)
        print(newlist[0], newlist[1])
        now=newlist[0]-newlist[1]
        for ll in range(n-2):
            if counter==n-3:
                print(newlist[ll+2], now)
                now=-(abs(now)+abs(newlist[ll+2]))
            else:
                print(now, newlist[ll+2])
                now=-(abs(now)+abs(newlist[ll+2]))
            counter+=1
    elif seihu==-1:
        newlist=sorted(newlist, reverse=True)
        wa=0
        for nl in range(n):
            wa+=abs(newlist[nl])
        wa+=newlist[0]*2
        print(wa)
        print(newlist[0], newlist[1])
        now=newlist[0]-newlist[1]
        for ll in range(n-2):
            if counter==n-3:
                print(now, newlist[ll+2])
                now=(abs(now)+abs(newlist[ll+2]))
            else:
                print(now, newlist[ll+2])
                now=(abs(now)+abs(newlist[ll+2]))
            counter+=1
    
else:
    print(abs(mazu*(len(newlist)-2)))
    for i in range(len(newlist)-2):
        print(mazu*(1-i), mazu)
    if mazu>=0:
        print(mazu, mazu*(3-len(newlist)))
    else:
        print(mazu*(3-len(newlist)), mazu)

Submission status: Accepted

Solution code:
n = int(input())
ps = []
mis = []
for _ in input().split():
  item = int(_)
  if item >= 0:
    ps.append(item)
  else:
    mis.append(item)
  
mis.sort(reverse = True)
ps.sort()
if len(mis) == 0:
  mis = [ps[0]]
  ps = ps[1:]
if len(ps) == 0:
  ps = [mis[0]]
  mis = mis[1:]
print(sum(ps) - sum(mis))

pre = mis[0]
for p in ps[:len(ps) - 1]:
  print(pre, p)
  pre -= p
print(ps[-1], pre)
pre = ps[-1] - pre
for m in mis[1:]:
  print(pre, m)
  pre -= m

Submission status: Accepted

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

if N == 2:
    y, x = A
    print(x-y)
    print(x, y)
    exit()

XY = []

PLUS = 0
MINUS = 0
for a in A:
    if a >= 0:
        PLUS += 1
    else:
        MINUS += 1

XY = []
tmp = A[0]
if PLUS and MINUS:
    while PLUS >= 2:
        x, y = tmp, A.pop()
        XY.append((x, y))
        tmp = x-y
        PLUS -= 1
    x, y = A.pop(), tmp
    XY.append((x, y))
    tmp = x-y
    N = len(A)
    for i in range(1, N):
        a = A[i]
        x, y = tmp, a
        XY.append((x, y))
        tmp = x-y
elif PLUS:
    for i in range(N-1):
        if i < N-2:
            x, y = tmp, A.pop()
            XY.append((x, y))
            tmp = x-y
        if i == N-2:
            x, y = A.pop(), tmp
            XY.append((x, y))
            tmp = x-y
else:
    for i in range(N-1):
        if i == 0:
            x, y = A.pop(), tmp
            XY.append((x, y))
            tmp = x-y
        else:
            x, y = tmp, A.pop()
            XY.append((x, y))
            tmp = x-y       
ans = tmp
print(ans)
for x, y in XY:
    print(x, y)

Submission status: Accepted

Solution code:
import sys
import collections

n = int(input())
a = sorted([int(i) for i in input().split()])
# print(a)
top = a.pop(-1)

nega = sorted([i for i in a if i < 0])
posi = sorted([i for i in a if i >= 0])
#print(nega,posi)

if len(nega) == 0:
    nega.append(posi.pop(0))

process = []

for _ in range(len(posi)):
    x = nega.pop(0)
    y = posi.pop(0)
    nega.append(x - y)
    process.append([x, y])
x = top
y = nega.pop(0)
process.append([x, y])
x -= y
for _ in range(len(nega)):
    y = nega.pop(0)
    process.append([x, y])
    x -= y
ans = x

print(ans)
for i in range(len(process)):
    print('{} {}'.format(process[i][0], process[i][1]))

Submission status: Accepted

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

left = nums[0]
right = sum(nums[1:])

ans = right - left
arg = 0
for i in range(1, n - 1):
	left += nums[i]
	right -= nums[i]
	if right - left > ans:
		arg = i
		ans = right - left

print(ans)

l_list = nums[:(arg + 1)]
r_list = nums[(arg + 1):]

while len(l_list) > 1:
	x = r_list.pop()
	y = l_list.pop()
	print(str(x) + " " + str(y))
	r_list.append(x - y)

x = l_list.pop()
while len(r_list) > 1:
	y = r_list.pop()
	print(str(x) + " " + str(y))
	x = x - y

print(str(r_list.pop()) + " " + str(x))

Submission status: Accepted

Solution code:
from sys import stdin
import math
import fractions
from collections import deque
import itertools

INF = 10 ** 10


# N個整数A1～AN, N=10^5
N = int(stdin.readline().rstrip())
A = list(map(int, stdin.readline().rstrip().split()))
A_abs = [abs(x) for x in A]

# 2個の整数x, yを選んで消し、新たに1個の整数x-yを書く
# ただ1つ残る整数としてありうる値の最大値Mと、その最大値を達成する操作列を求める

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

# 答え
result = []

plus_num = []
minus_num = []

for Ai in A:
    if Ai > 0:
        plus_num.append(Ai)
    else:
        minus_num.append(Ai)

plus_num_cnt = len(plus_num)
minus_num_cnt = len(minus_num)

if minus_num_cnt == 0:
    # マイナスを作る
    plus_num.sort(reverse=True)
    x = plus_num.pop()
    y = plus_num.pop()
    if x > y:
        tmp = x
        x = y
        y = tmp
    
    result.append([x, y])
    minus_num.append(x-y)
    plus_num_cnt -= 2
    minus_num_cnt += 1

elif plus_num_cnt == 0:
    # プラスを作る
    minus_num.sort()
    x = minus_num.pop()
    y = minus_num.pop()
    if x < y:
        tmp = x
        x = y
        y = tmp

    result.append([x, y])
    plus_num.append(x-y)
    minus_num_cnt -= 2
    plus_num_cnt += 1

    


if plus_num_cnt > 0 and minus_num_cnt > 0:

    while(plus_num_cnt > 0):
        if plus_num_cnt == 1:
            break

        x = minus_num.pop()
        y = plus_num.pop()

        result.append([x, y])
        minus_num.append(x-y)
        plus_num_cnt -= 1


    while minus_num_cnt > 0:
        x = plus_num.pop()
        y = minus_num.pop()

        result.append([x, y])
        plus_num.append(x-y)
        minus_num_cnt -= 1

    print(plus_num[0])
    for i, j in result:
        print(i, j)

Submission status: Accepted

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

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


if(max(a)>0 and min(a)>0):
    a.sort()
    total = sum(a)-2*a[0]
    print(total)
    temp=a[0]
    for i in range(n-2):
        print(temp,a[i+1])
        temp=temp-a[i+1]
    print(a[n-1],temp)
elif(max(a)<0 and min(a)<0):
    b = [abs(a[i]) for i in range(len(a))]
    b.sort()
    total = sum(b)-2*b[0]
    print(total)
    temp= -b[0]
    for i in range(n-2):
        print(temp,-b[i+1])
        temp=temp+b[i+1]
    print(temp, -b[n-1])
else:
    b = [abs(a[i]) for i in range(len(a))]
    total = sum(b)
    print(total)
    a.sort()
    temp=a[n-1]
    for i in range(n-1):
        if(i==n-2):
            print(max(a[i],temp),min(a[i],temp))
        elif(a[i+1]>=0):
            print(min(a[i],temp),max(a[i],temp))
            temp=min(a[i],temp)-max(a[i],temp)
        else:
            print(max(a[i],temp),min(a[i],temp))
            temp=max(a[i],temp)-min(a[i],temp)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int, input().split()))
A.sort()
positive=[x for x in A if x >=0]
negative=[x for x in A if x <0]
ans=[]



if len(negative)>0 and len(positive)>0:
    y=negative[0]
    for i in positive[1:]:
        ans.append([y,i])
        y-=i
        
    x=positive[0]
    for i in negative[1:]:
        ans.append([x,i])
        x-=i

    M=x-y
    ans.append([x,y])

elif len(negative)==0:
    x=positive[N-1]
    y=positive[0]
    for i in positive[1:N-1]:
        ans.append([y,i])
        y-=i
    M=x-y
    ans.append([x,y])

elif len(positive)==0:
    negative.reverse()
    y=negative[N-1]
    x=negative[0]
    for i in negative[1:N-1]:
        ans.append([x,i])
        x-=i
    M=x-y
    ans.append([x,y])
    
print(M)
for i in ans:
    print(i[0],i[1])

Submission status: Accepted

Solution code:
n = int(input())
a_s = [int(v) for v in input().split()]

a_s.sort()
#max_a = a_s[len(a_s) - 1]
#min_a = a_s[0]
m = a_s[-1] - a_s[0]
for a in a_s[1:-1]:
  m += abs(a)
  
#m = sum(a_s[1:]) - a_s[0]

print(m)

max_a = a_s[-1]
min_a = a_s[0]

for a in a_s[1:-1]:
  if a < 0:
    print("{} {}".format(max_a, a))
    max_a -= a
  else:
    print("{} {}".format(min_a, a))
    min_a -= a
    
print("{} {}".format(max_a, min_a))

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
A = list(map(int, input().split()))
A.sort()
if A[0] >= 0:
    M = sum(A[1:])-A[0]
    print(M)
    for i in range(N-1):
        if i == 0:
            x = A[0]
            y = A[N-1]
            print(x, y)
        elif i <= N - 3:
            x = new
            y = A[N-1-i]
            print(x, y)
        else:
            x = A[N-1-i]
            y = new
            print(x, y)
        new = x - y
elif A[-1] <= 0:
    M = sum(A[:-1]) * (-1) + A[-1]
    print(M)
    for i in range(N-1):
        if i == 0:
            x = A[N-1]
            y = A[0]
            print(x, y)
        elif i <= N-3:
            x = new
            y = A[i]
            print(x, y)
        else:
            x = new
            y = A[i]
            print(x,y)
        new = x- y
else:
    absa = [abs(i) for i in A]
    M = sum(absa)
    print(M)
    if A[1] >= 0 :
        for i in range(N - 1):
            if i == 0:
                x = A[0]
                y = A[N - 1]
                print(x, y)
            elif i <= N - 3:
                x = new
                y = A[N - 1 - i]
                print(x, y)
            else:
                x = A[N - 1 - i]
                y = new
                print(x, y)
            new = x - y
    else:
        A = deque(A)
        for i in range(N - 1):
            if i <= N - 3 and A[1] < 0:
                x = A.pop()
                y = A.popleft()
                print(x, y)
                A.append(x-y)
            elif i <= N-3 :
                x = A.popleft()
                y = A.pop()
                print(x,y)
                A.appendleft(x-y)
            else:
                # print(A)
                x = A.pop()
                y = A.popleft()
                print(x, y)

Submission status: Accepted

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

B=[]
for i in range(1,N-1):
    if A[i]>=0:
        B.append([A[0],A[i]])
        A[0]-=A[i]
    else:
        B.append([A[-1],A[i]])
        A[-1]-=A[i]
print(A[-1]-A[0])
for b in B:
    print(b[0],b[1])
print(A[-1],A[0])

Submission status: Accepted

Solution code:
#

import itertools
from collections import Counter
from collections import defaultdict
import bisect
from heapq import heappush, heappop

def reverse_insort(a, x, lo=0, hi=None):
    """Insert item x in list a, and keep it reverse-sorted assuming a
    is reverse-sorted.

    If x is already in a, insert it to the right of the rightmost x.

    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.
    """
    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if x > a[mid]: hi = mid
        else: lo = mid+1
    a.insert(lo, x)

def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    index = bisect.bisect_left(A, 0)
    minus = A[:index]
    minus.reverse()
    plus = A[index:]
    # print(minus)
    # print(plus)
    progres = []
    ans = 0
    while True:
        if len(plus) == 1 and len(minus) == 1:
            p = plus.pop()
            m = minus.pop()
            progres.append((p, m))
            ans = p - m
            # print('{} {}'.format(p, m))
            break

        if len(plus) == 1 and len(minus) == 0:
            ans = plus.pop()
            break
        if len(plus) == 0 and len(minus) == 1:
            ans = minus.pop()
            break

        # まだ2つ以上入ってる
        if len(plus) == 0:
            val1 = minus.pop()  # 一番小さい
            val2 = minus.pop(0)
            new_val = val2 - val1
            plus.append(new_val)
            progres.append((val2, val1))
            # print('{} {}'.format(val1, val2))
            continue
        if len(minus) == 0:
            val1 = plus.pop(0)
            val2 = plus.pop()
            new_val = val1 - val2
            minus.append(new_val)
            progres.append((val1, val2))
            # print('{} {}'.format(val2, val1))
            continue

        if len(plus) > len(minus):
            val1 = plus.pop()
            val2 = minus.pop()
            new_val = val2 - val1
            reverse_insort(minus, new_val)
            progres.append((val2, val1))
            # print('{} {}'.format(val2, val1))
        else:
            val1 = plus.pop()
            val2 = minus.pop()
            new_val = val1 - val2
            index = bisect.bisect_left(plus, new_val)
            plus.insert(index, new_val)
            progres.append((val1, val2))
            # print('{} {}'.format(val1, val2))

    print(ans)
    for p, q in progres:
        print('{} {}'.format(p, q))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
inp = input()
large_n = int(inp)
inp = input()
split_input = inp.split()
a_list = [int(i) for i in split_input]
plus_list = []
minus_list = []
zero_count = 0
for n in a_list:
    if n > 0:
        plus_list.append(n)
    elif n < 0:
        minus_list.append(n)
    else:
        zero_count += 1
if zero_count == large_n:
    print(0)
    for _ in range(large_n-1):
        print("0 0")
    exit()
print_list = []
m = 0
if zero_count == 0:
    if len(plus_list) == 0:
        max_number = max(minus_list)
        hoge = minus_list.pop(minus_list.index(max_number))
        present_number = max_number
        for number in minus_list:
            print_list.append(str(present_number) + " " + str(number))
            present_number = present_number - number
        m = present_number
    elif len(minus_list) == 0:
        mini_number = plus_list.pop(plus_list.index(min(plus_list)))
        present_number = mini_number
        for number in plus_list[:-1]:
            print_list.append(str(present_number) + " " + str(number))
            present_number = present_number - number
        print_list.append(str(plus_list[-1]) + " " + str(present_number))
        m = plus_list[-1] - present_number
    else:
        present_number = minus_list.pop()
        for number in plus_list[:-1]:
            print_list.append(str(present_number) + " " + str(number))
            present_number -= number
        print_list.append(str(plus_list[-1]) + " " + str(present_number))
        present_number = plus_list[-1] - present_number
        for number in minus_list:
            print_list.append(str(present_number) + " " + str(number))
            present_number -= number
        m = present_number
else:
    for _ in range(zero_count-1):
        print_list.append("0 0")
    # 0 一つ残る
    plus_number = 0
    if len(plus_list) > 0:
        plus_number = plus_list.pop()
    present_number = 0
    # plus なくす
    for number in plus_list:
        print_list.append(str(present_number) + " " + str(number))
        present_number -= number
    if plus_number != 0:
        print_list.append(str(plus_number) + " " + str(present_number))
        present_number = plus_number - present_number
    for number in minus_list:
        print_list.append(str(present_number) + " " + str(number))
        present_number -= number
    m = present_number


print(m)
for p in print_list:
    print(p)

Submission status: Accepted

Solution code:
n = int(input())
a = [int(_) for _ in input().split()]
ans = []
a.append(0)
a.sort()

if a.index(0) == 0:
    x = a.pop(1)
    y = a.pop()
    tmp = x-y
    ans.append([x,y])
    a.append(tmp)
    a.sort()
elif a.index(0) == n:
    x = a.pop(-2)
    y = a.pop(0)
    tmp = x-y
    ans.append([x,y])
    a.append(tmp)
    a.sort()

a.remove(0)
if len(a) == 1:
    print(a[0])
    print(ans[0][0], ans[0][1])
else:
    maximum = a.pop()
    minimum = a.pop(0)
    while len(a) > 0:
        x = a.pop()
        if x > 0:
            ans.append([minimum, x])
            minimum -= x
        else:
            ans.append([maximum, x])
            maximum -= x

    m = maximum-minimum
    print(m)
    ans.append([maximum, minimum])
    for i in ans:
        print(i[0], i[1])

Submission status: Accepted

Solution code:
N = int(input())
A = [int(x) for x in input().split()]
p = []
m = []
for a in A:
    if a < 0:
        m.append(a)
    else:
        p.append(a)
was = []
if N == 2:
    print(max(A)-min(A))
    print(max(A), min(A))
    quit()
if len(m) == 0:
    p.sort()
    m.append(p[0] - p[-1])
    was.append((p[0], p[-1]))
    p = p[1:-1]
elif len(p) == 0:
    m.sort()
    p.append(m[-1] - m[0])
    was.append((m[-1], m[0]))
    m = m[1:-1]

mm = m[0]
m = m[1:]
pp = p[0]
p = p[1:]
for x in p:
    was.append((mm,x))
    mm -= x
for x in m:
    was.append((pp,x))
    pp -= x
was.append((pp, mm))
print(pp-mm)
for p,m in was:
    print(p,m)

Submission status: Accepted

Solution code:
n = int(input())
li = list(map(int,input().split()))
lipos = [i for i in li if i>0]
lineg = [i for i in li if i<0]
li0 = [i for i in li if i==0]
np = len(lipos)
ng = len(lineg)
n0 = len(li0)

if ng == 0:
  lipos = lipos + li0
  np = len(lipos)
  print(sum(lipos)-2*min(lipos))
  lipos.sort()
  tmp = lipos[0]
  for i in range(1,np-1):
    print("{} {}".format(tmp,lipos[i]))
    tmp -= lipos[i]
  print("{} {}".format(lipos[np-1],tmp))
elif np == 0:
  lineg = lineg + li0
  ng = len(lineg)
  print(2*max(lineg)-sum(lineg))
  lineg.sort()
  lineg.reverse()
  tmp = lineg[0]
  for i in range(1,ng):
    print("{} {}".format(tmp,lineg[i]))
    tmp -= lineg[i]
else:
  lipos = lipos + li0
  np = len(lipos)
  print(sum(list(map(abs,lineg))) + sum(lipos))
  lipos.sort()
  lineg.sort()
  lineg.reverse()
  tmp = lineg[0]
  for i in range(1,np):
    print("{} {}".format(tmp,lipos[i]))
    tmp -= lipos[i]
  print("{} {}".format(lipos[0],tmp))
  tmp = lipos[0] - tmp
  for i in range(1,ng):
    print("{} {}".format(tmp,lineg[i]))
    tmp -= lineg[i]

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
A = (map(int, input().split()))
A = sorted(A)
A = deque(A)
l = []
for i in range(N - 1):
    if i == N - 2:
        ans = A[1] - A[0]
        l.append("{} {}".format(A[1], A[0]))
    elif i == N - 3:
        left = A.popleft()
        right = A.pop()
        center = A.pop()

        temp_left = abs(right - (left - center))
        temp_right = abs(left - (right - center))

        if temp_left >= temp_right:
            A.appendleft(left - center)
            A.append(right)
            l.append("{} {}".format(left, center))
        else:
            A.append(right - center)
            A.appendleft(left)
            l.append("{} {}".format(right, center))


    else:
        left = A.popleft()
        left2 = A.popleft()
        right = A.pop()
        right2 = A.pop()
        
        temp_left = abs(right - (left - right2))
        temp_right = abs(left - (right - left2))
        if temp_left >= temp_right:
            A.appendleft(left2)
            A.appendleft(left - right2)
            A.append(right)
            l.append("{} {}".format(left, right2))
        else:
            A.append(right2)
            A.append(right - left2)
            A.appendleft(left)
            l.append("{} {}".format(right, left2))

print(ans)
for line in l:
    print(line)

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
A = list(map(int, input().split()))
A.sort()
negative = deque([])
positive = deque([])

for n in A:
    if n < 0:
        negative.append(n)
    else:
        positive.append(n)

output = N-1

if negative and positive:
    print(abs(sum(negative)) + sum(positive))
elif not negative:
    print(sum(positive)-positive[0]*2)
    x = positive.popleft()
    y = positive.popleft()
    print(x, y)
    negative.append(x-y)
    output -= 1
else:
    print(abs(sum(negative)-negative[-1]*2))
    x = negative.pop()
    y = negative.pop()
    print(x, y)
    positive.append(x-y)
    output -= 1

for i in range(output):
    if len(negative) >= 2:
        y = negative.pop()
        x = positive.pop()
        print(x, y)
        positive.append(x-y)
    elif len(positive) >= 2:
        x = negative.pop()
        y = positive.pop()
        print(x, y)
        negative.append(x-y)
    else:
        print(positive.pop(), negative.pop())

Submission status: Accepted

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

################################################################################

n = int(input())
a = list(map(int, input().split()))
pt = []
nt = []
for x in a:
    if x >= 0:
        pt.append(x)
    elif x < 0:
        nt.append(x)

res = []

s = 0
if len(pt) == n:
    a.sort()
    s = a[0]
    for i in range(1, n-1):
        res.append((s, a[i]))
        s -= a[i]

    res.append((a[-1], s))
    s = a[-1] - s

elif len(nt) == n:
    a.sort(reverse=True)
    s = a[0]
    for i in range(1, n):
        res.append((s, a[i]))
        s -= a[i]

else:
    s = nt[0]
    for i in range(1, len(pt)):
        res.append((s, pt[i]))
        s -= pt[i]

    res.append((pt[0], s))
    s = pt[0] - s

    for i in range(1, len(nt)):
        res.append((s, nt[i]))
        s -= nt[i]

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

Submission status: Accepted

Solution code:
import heapq

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

max_heap = []
plus_min = 100000
min_heap = []
minus_max = -100000
ope = []

for i in range(N):
    if A[i] >= 0:
        plus_min = min(plus_min, A[i])
        heapq.heappush(max_heap,(-A[i], A[i]))
    else:
        minus_max = max(minus_max, A[i])
        heapq.heappush(min_heap,(A[i], A[i]))

k = 0
for i in range(N-1):
    if len(min_heap)==0:
        x, y = plus_min, heapq.heappop(max_heap)[1]
        m = x - y
        ope.append("" + str(x) + " " + str(y))
        k+=1
        heapq.heappush(min_heap,(m, m))
    elif len(max_heap)==0:
        x, y = heapq.heappop(min_heap)[1], minus_max
        m = y - x
        ope.append("" + str(y) + " " + str(x))
        heapq.heappush(max_heap,(-m, m))
    elif len(max_heap)>1+k:
        x, y = heapq.heappop(min_heap)[1], heapq.heappop(max_heap)[1]
        m = x - y
        ope.append("" + str(x) + " " + str(y))
        heapq.heappush(min_heap,(m, m))
    else:
        x, y = heapq.heappop(min_heap)[1], heapq.heappop(max_heap)[1]
        m = y - x
        ope.append("" + str(y) + " " + str(x))
        heapq.heappush(max_heap,(-m, m))

print(heapq.heappop(max_heap)[1])
print("\n".join(ope))

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
s=sorted([i for i in a if i<0])
t=sorted([i for i in a if i>=0])
if len(s)==0:
    print(t[-1]-t[0]+sum(t[1:-1]))
    k=t[0]
    if n!=2:
        for i in range(1,n-1):
            print(k,t[i])
            k-=t[i]
    print(t[-1],k)
elif len(t)==0:
    d=s[-1]
    print(s[-1]-sum(s[:-1]))
    for i in range(n-1):
        print(d,s[i])
        d-=s[i]
else:
    print(t[-1]-sum(s)+sum(t[:-1]))
    p=t[-1]
    for i in range(1,len(s)):
        print(p,s[i])
        p-=s[i]
    g=s[0]
    for i in range(len(t)-1):
        print(g,t[i])
        g-=t[i]
    print(p,g)