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 sys import stdout
from bisect import bisect_left as binl
from copy import copy, deepcopy
from collections import defaultdict
import math


mod = 1


def intin():
    input_tuple = input().split()
    if len(input_tuple) <= 1:
        return int(input_tuple[0])
    return tuple(map(int, input_tuple))


def intina():
    return [int(i) for i in input().split()]


def intinl(count):
    return [intin() for _ in range(count)]


def modadd(x, y):
    global mod
    return (x + y) % mod


def modmlt(x, y):
    global mod
    return (x * y) % mod


def mod_inv(x):
    # available only when mod is prime
    global mod
    return pow(x, mod - 2, mod)


def gcm(x, y):
    while y != 0:
        z = x % y
        x = y
        y = z
    return x


def combination(x, y):
    assert(x >= y)

    ret = math.factorial(x)
    ret = ret // (math.factorial(x - y) * math.factorial(y))

    return ret


def get_divisors(x):
    retlist = []
    for i in range(1, int(x**0.5) + 3):
        if x % i == 0:
            retlist.append(i)
            retlist.append(x // i)
    return retlist


def get_factors(x):
    retlist = []
    for i in range(2, int(x**0.5) + 3):
        while x % i == 0:
            retlist.append(i)
            x = x // i
    retlist.append(x)
    return retlist


def make_linklist(xylist):
    linklist = {}
    for a, b in xylist:
        linklist.setdefault(a, [])
        linklist.setdefault(b, [])
        linklist[a].append(b)
        linklist[b].append(a)
    return linklist


def calc_longest_distance(linklist, v=1):
    distance_list = {}
    distance_count = 0
    distance = 0
    vlist_previous = []
    vlist = [v]
    nodecount = len(linklist)

    while distance_count < nodecount:
        vlist_next = []
        for v in vlist:
            distance_list[v] = distance
            distance_count += 1
            vlist_next.extend(linklist[v])
        distance += 1
        vlist_to_del = vlist_previous
        vlist_previous = vlist
        vlist = list(set(vlist_next) - set(vlist_to_del))

    max_distance = -1
    max_v = None
    for v, distance in distance_list.items():
        if distance > max_distance:
            max_distance = distance
            max_v = v

    return (max_distance, max_v)


def calc_tree_diameter(linklist, v=1):
    _, u = calc_longest_distance(linklist, v)
    distance, _ = calc_longest_distance(linklist, u)
    return distance


class UnionFind:

    def __init__(self, n):
        self.parent = [i for i in range(n)]

    def root(self, i):
        if self.parent[i] == i:
            return i
        self.parent[i] = self.root(self.parent[i])
        return self.parent[i]

    def unite(self, i, j):
        rooti = self.root(i)
        rootj = self.root(j)
        if rooti == rootj:
            return
        if rooti < rootj:
            self.parent[rootj] = rooti
        else:
            self.parent[rooti] = rootj

    def same(self, i, j):
        return self.root(i) == self.root(j)


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


def main():
    n = intin()
    alist = intina()

    alist.sort()

    if alist[0] >= 0:
        ans = -alist[0]
        for a in alist[1:]:
            ans += a
        print(ans)
        x = alist[0]
        for a in alist[1:(n-1)]:
            print('%d %d' % (x, a))
            x = x - a
        print('%d %d' % (alist[-1], x))

    elif alist[-1] <= 0:
        ans = alist[-1]
        for a in alist[:(n-1)]:
            ans += (-a)
        print(ans)
        x = alist[-1]
        for a in alist[:(n-1)]:
            print('%d %d' % (x, a))
            x = x - a

    else:
        ans = 0
        for a in alist:
            ans += abs(a)
        print(ans)
        x = alist[0]
        for a in alist[:(n-1)]:
            if a < 0:
                continue
            print('%d %d' % (x, a))
            x = x - a
        alist[0] = x
        x = alist[-1]
        for a in alist[:(n-1)]:
            if a >= 0:
                break
            print('%d %d' % (x, a))
            x = x - a


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-


def main():
    N = int(input())
    A = sorted(list(map(int, input().split())))
    if A[0] >= 0:
        printAllPlus(A)
    elif A[-1] <= 0:
        printAllMinus(A)
    else:
        printMixed(A)


def printMixed(nums):
    i = -1
    for k, n in enumerate(nums):
        if n >= 0:
            i = k
            break
    plus = nums[i:]
    minus = nums[:i]
    print(sum(plus) - sum(minus))
    while len(plus) > 1:
        p = plus.pop()
        m = minus.pop()
        print(m, p)
        minus.append(m - p)
    p0 = plus.pop()
    for m in minus:
        print(p0, m)
        p0 -= m


def printAllPlus(nums):
    ans = sum(nums) - 2 * nums[0]
    print(ans)
    tmp = nums[0]
    for n in nums[1:-1]:
        print(tmp, n)
        tmp -= n
    print(nums[-1], tmp)


def printAllMinus(nums):
    nums.reverse()
    ans = -sum(nums) + 2 * nums[0]
    print(ans)
    tmp = nums[0]
    for n in nums[1:]:
        print(tmp, n)
        tmp -= n


if __name__ == "__main__":
    main()

Submission status: Accepted

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

pos = []
neg = []
zeros = 0
for a in A:
    if a > 0:
        pos.append(a)
    elif a < 0:
        neg.append(a)
    else:
        zeros += 1

pos.sort()
neg.sort()

ope = []

if len(pos) == len(neg) == 0:
    print(0)
    for i in range(N-1):
        print(0,0)
    exit()

if len(neg) == 0:
    if zeros:
        ope.append((0,pos[-1]))
        neg.append(-pos[-1])
        zeros -= 1
        pos.pop()
    else:
        ope.append((pos[0],pos[-1]))
        neg.append(pos[0] - pos[-1])
        pos = pos[1:-1]

elif len(pos) == 0:
    if zeros:
        ope.append((0,neg[0]))
        pos.append(-neg[0])
        zeros -= 1
        neg = neg[1:]
    else:
        ope.append((neg[-1],neg[0]))
        pos.append(neg[-1] - neg[0])
        neg = neg[1:-1]

for p in pos[:-1]:
    ope.append((neg[0], p))
    neg[0] -= p

for n in neg[1:]:
    ope.append((pos[-1], n))
    pos[-1] -= n

ope.append((pos[-1], neg[0]))
ans = pos[-1] - neg[0]
for z in range(zeros):
    ope.append((ans, 0))

print(ans)
for x,y in ope:
    print(x,y)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
ind=0
for iii in range(len(a)):
  if a[iii]>0:
    ind=iii
    break
num=0
lans=[]
mi=min(a)
ma=max(a)
ima=a.index(ma)
imi=a.index(mi)
if n==2:
  print(ma-mi)
  print(str(ma),str(mi))
else:
  if ma<=0:
    num=a[-1]
    for iii in range(len(a)-1):
      lans.append(str(num)+" "+str(a[iii]))
      num-=a[iii]
  else:
    if mi>=0:
      num=mi
      for iii in range(len(a)-2):
        lans.append(str(num)+" "+str(a[-iii-1]))
        num-=a[-iii-1]
      lans.append(str(a[1])+" "+str(num))
      num=a[1]-num
    else:
      num=mi
      for iii in range(len(a)-ind-1):
        lans.append(str(num)+" "+str(a[-iii-1]))
        num-=a[-iii-1]
      for iii in range(ind):
        if iii==0:
          lans.append(str(a[ind])+" "+str(num))
          num=a[ind]-num
        else:
          lans.append(str(num)+" "+str(a[iii]))
          num-=a[iii]
  print(num)
  for iii in range(len(lans)):
    print(lans[iii])

Submission status: Accepted

Solution code:
#!/usr/bin/python3

def main():
  n = int(input())
  a = list(map(int, input().split(' ')))

  max_a = max(a)
  min_a = min(a)

  if max_a >= 0 and min_a <= 0:
    result, process = has_pos_and_neg(a)
    print(result)
    for line in process:
      print(line)

  elif min_a > 0:
    a.remove(max_a)
    a.remove(min_a)
    a.append(min_a - max_a)

    result, process = has_pos_and_neg(a)
    print(result)
    print('{} {}'.format(min_a, max_a))
    for line in process:
      print(line)

  elif max_a < 0:
    a.remove(max_a)
    a.remove(min_a)
    a.append(max_a - min_a)

    result, process = has_pos_and_neg(a)
    print(result)
    print('{} {}'.format(max_a, min_a))
    for line in process:
      print(line)


def has_pos_and_neg(a):
  if len(a) == 1:
    return a[0], []

  max_a = max(a)
  min_a = min(a)

  a.remove(max_a)
  a.remove(min_a)

  process = []

  for elem in a:
    if elem <= 0:
      process.append('{} {}'.format(max_a, elem))
      max_a -= elem
    else:
      process.append('{} {}'.format(min_a, elem))
      min_a -= elem

  process.append('{} {}'.format(max_a, min_a))
  result = max_a - min_a

  return result, process

if __name__ == '__main__':
  main()

Submission status: Accepted

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

A.sort()
MAX = A.pop(-1)
ans = MAX
MIN = A.pop(0)
MIN2 = MIN
MAX2 = MAX

if MIN2 <= 0:
    if N == 2:
        ans -= MIN2
    else:
        for a in A:
            if a > 0:
                MIN2 -= a
            else:
                
                MAX2 -= a
        ans = MAX2 - MIN2
       
        
else:
    if N == 2:
        ans -= MIN2
        
    else:
        b = A.pop(-1)
        
        MIN2 -= b
        for a in A:
            if a > 0:
                
                MIN2 -= a
            else:
                
                MAX2 -= a
        ans = MAX2 - MIN2

print(ans)

if MIN <= 0:
    if N == 2:
        ans -= MIN
        print("{0} {1}".format(MAX, MIN))
    else:
        
        for a in A:
            if a > 0:
                print("{0} {1}".format(MIN, a))
                MIN -= a
            else:
                print("{0} {1}".format(MAX, a))
                MAX -= a
        print("{0} {1}".format(MAX, MIN))
        
else:
    if N == 2:
        ans -= MIN
        print("{0} {1}".format(MAX, MIN))
    else:
      
        print("{0} {1}".format(MIN, b))
        MIN -= b
        for a in A:
            if a > 0:
                print("{0} {1}".format(MIN, a))
                MIN -= a
            else:
                print("{0} {1}".format(MAX, a))
                MAX -= a
        print("{0} {1}".format(MAX, MIN))

Submission status: Accepted

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

minus_flag = 1
max_value = a[N - 1]
min_value = a[0]
ans = []

while a[minus_flag] <=  0 and minus_flag < N - 1:
    ans.append(str(max_value) + " " + str(a[minus_flag]))
    max_value = max_value - a[minus_flag]
    minus_flag += 1

plus_flag = minus_flag

while  plus_flag < N - 1:
    ans.append(str(min_value) + " " + str(a[plus_flag]))
    min_value = min_value - a[plus_flag]
    plus_flag += 1

print(max_value - min_value)
for i in range(len(ans)):
    print(ans[i])
print(str(max_value)  + " " + str(min_value))

Submission status: Accepted

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

A.sort()

nminus = len([i for i in A if i < 0])
nplus = N - nminus



if nminus == N:
    M = 2*A[N-1] - np.sum(A)
    print(M)

    caled = A[N-1]
    for i in range(nminus-1):
        print(caled,A[i])
        caled -= A[i]
elif nplus == N:
    M = np.sum(A) - 2*A[0]
    print(M)

    caled = A[0]
    for i in range(N-2):
        print(caled, A[i+1])
        caled -= A[i+1]
    print(A[N-1],caled)
else:
    M = 0
    for i in range(N-1):
        M += abs(A[i])
    M += A[N-1]
    print(M)

    caled = A[0]
    for i in range(nplus-1):
        print(caled,A[nminus+i])
        caled -= A[nminus+i]
    caled_2 = A[N-1]
    for i in range(nminus-1):
        print(caled_2,A[i+1])
        caled_2 -= A[i+1]
    print(caled_2,caled)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
A = sorted(A)
max_ans = 0
ans_op = []
if A[0] < 0 and A[-1] < 0:
    al = A.pop(-1)
    ar = A.pop(-1)
    tmp = al - ar
    ans_op.append([al, ar])
    A.append(tmp)
    N -= 1
elif A[0] > 0 and A[-1] > 0:
    al = A.pop(0)
    ar = A.pop(0)
    tmp = al - ar
    ans_op.append([al, ar])
    A.insert(0, tmp)
    N -= 1
tmp = A.pop(-1)
if N >= 2:
    tmpl = A.pop(0)
else:
    tmpl = 0
    
for i in range(N-2):
    if A[-1] <= 0:
        ar = A.pop(-1)
        ans_op.append([tmp, ar])
        tmp = tmp - ar
    else:
        ans_op.append([tmpl, tmp])
        tmpl = tmpl - tmp
        tmp = A.pop(-1)
        # A.insert(0, tmp)
ans_op.append([tmp, tmpl])
print(tmp-tmpl)
for op in ans_op:
    print(op[0], op[1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function

import os
import sys
from bisect import bisect
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip


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

    a.sort()

    o = []

    d = bisect(a, 0)
    if d == 0:
        o.append('%d %d' % (a[0], a[1]))
        a[0] -= a[1]
        del a[1]
        n -= 1
        d = 1

    s = a[d - 1]

    for i in range(d, n - 1):
        o.append('%d %d' % (s, a[i]))
        s -= a[i]

    if d != n:
        o.append('%d %d' % (a[-1], s))
        s = abs(s) + a[-1]

    if s < 0:
        d -= 1
        o.append('%d %d' % (a[d], a[d - 1]))
        s = a[d] - a[d - 1]

    for i in range(0, d - 1):
        o.append('%d %d' % (s, a[i]))
        s += abs(a[i])

    print(s)
    print('\n'.join(o))


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
MOD = 1000000007
def POW(x, y): return pow(x, y, MOD)
def INV(x, m=MOD): return pow(x, m - 2, m)
def DIV(x, y, m=MOD): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())


N=II()
INL=LI()

INL.sort()

ma = INL[-1]
mi = INL[0]

INL = INL[1:-1]

resl = []
if INL:
    if mi > 0:
        for i in INL:
            resl.append((mi,i))
            mi -= i
    else:
        for i in INL:
            if i < 0:
                resl.append((ma,i))
                ma -= i
            else:
                resl.append((mi,i))
                mi -= i

print(ma - mi)
for li in resl:
    print(li[0], li[1])
print(ma, mi)

Submission status: Accepted

Solution code:
n=int(input())
l=sorted(list(map(int,input().split())))
if l[0]>=0:
  c=l[0]
  l1=[]
  for i in range(1,n-1):
    l1.append([c,l[i]])
    c-=l[i]
  score=l[-1]-c
  print(score)
  for i in l1:
    print(i[0],i[1])
  print(l[-1],c)
elif l[-1]<0:
  c=l[-1]
  l1=[]
  for i in range(0,n-1):
    l1.append([c,l[i]])
    c-=l[i]
  print(c)
  for i in l1:
    print(i[0],i[1])
else:
  l1=[]
  l2=[]
  l3=[]
  for i in l:
    if i<0:
      l1.append(i)
    else:
      l2.append(i)
  c=l1[0]
  for i in range(len(l2)-1):
    l3.append([c,l2[i]])
    c-=l2[i]
  s1=l2[len(l2)-1]
  for i in range(1,len(l1)):
    l3.append([s1,l1[i]])
    s1-=l1[i]
  score=s1-c
  print(score)
  for i in l3:
    print(i[0],i[1])
  print(s1,c)

Submission status: Accepted

Solution code:
n = int(input())
num = [int(i) for i in input().split()]
plus = []
minus = []
sumlist = []
for i in range(n):
    if(num[i] >= 0):
        plus.append(num[i])
    else:
        minus.append(num[i])

ans = []
if(len(plus) >= len(minus)): #正の個数の方が多い
    last = min(num)
    if(last >= 0):
        plus.remove(min(plus))
    else:
        minus.remove(min(minus))
    while(len(minus) > 0):
        sumlist.append(plus[0] - minus[0])
        ans.append([plus.pop(0), minus.pop(0)])
    for i in range(len(plus)):
        sumlist.append(plus[i])
    for i in range(len(sumlist)-1):
        tmp = last
        last -= sumlist[0]
        ans.append([tmp, sumlist.pop(0)])
    ans.append([sumlist[0], last])
    score = sumlist[0] - last
    print(score)
    for i in range(len(ans)):
        print(str(ans[i][0]) + " " + str(ans[i][1]))
else: #負の個数の方が多い
    last = max(num)
    if(last >= 0):
        plus.remove(max(plus))
    else:
        minus.remove(max(minus))
    while(len(plus) > 0):
        sumlist.append(minus[0] - plus[0])
        ans.append([minus.pop(0), plus.pop(0)])
    for i in range(len(minus)):
        sumlist.append(minus[i])
    for i in range(len(sumlist)-1):
        tmp = last
        last -= sumlist[0]
        ans.append([tmp, sumlist.pop(0)])
    ans.append([last, sumlist[0]])
    score = last - sumlist[0]
    print(score)
    for i in range(len(ans)):
        print(str(ans[i][0]) + " " + str(ans[i][1]))

Submission status: Accepted

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

if A[0] >=0:
    print(sum(A)-A[0]*2)
    a = A[0]
    for i in range(n-2):
        print(a,A[i+1])
        a = a - A[i+1]
    print(A[-1],a)
           
elif A[-1] <=0:
    print(-sum(A)+2*A[-1])
    a = A[-1]
    for i in range(n-1):
        print(a,A[i])
        a = a - A[i]
else:
    for i in range(n):
        if A[i]>= 0:
            change_point = i
            break   
    print(sum(A)-2*sum(A[0:i]))
    a = A[0]
    for i in range(n - change_point-1):
        print(a,A[-(i+1)])
        a = a - A[-(i+1)]
    print(A[change_point],a)
    a = A[change_point]-a
    for i in range(change_point-1):
        print(a,A[i+1]) 
        a = a - A[i+1]

Submission status: Accepted

Solution code:
from bisect import bisect_left
from collections import deque

N = int(input())
A = [int(s) for s in input().split()]
A.sort()
if len(A) == 2:
    print(A[1] - A[0])
    print(A[1], A[0])
    exit()

i = bisect_left(A, 0)
left = deque(A[:i])
right = deque(A[i:])
ans = []
if not len(left):
    r0 = right.popleft()
    r1 = right.pop()
    ans.append((r0, r1))
    left.append(r0 - r1)
if not len(right):
    l0 = left.popleft()
    l1 = left.pop()
    ans.append((l1, l0))
    right.append((l1 - l0))

while len(left) > 1:
    l = left.popleft()
    r = right[0]
    ans.append((r, l))
    right[0] = r - l

while len(right) > 1:
    r = right.pop()
    l = left[0]
    ans.append((l, r))
    left[0] = l - r

ans.append((right[0], left[0]))
print(right[0] - left[0])
for x, y in ans:
    print(x, y)

Submission status: Accepted

Solution code:
import heapq

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


heap = []
max_val = -10001
for i in a:
    if i > max_val:
        max_val = i
    heapq.heappush(heap,i)
log = []

min_val = heapq.heappop(heap)
for _ in range(N-2):
    tg = heapq.heappop(heap)
    if tg < 0:
        log.append([max_val, tg])
        max_val -= tg
    else:
        log.append([min_val, tg])
        min_val -= tg
    
print(max_val - min_val)
log.append([max_val,min_val])
for l in log:
    print(l[0],l[1])

Submission status: Accepted

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

N = int(input())
A = [int(i) for i in input().split()]

A.sort()
if N == 2:
    print(A[1]-A[0])
    print(A[1],A[0])
    exit()

A.reverse()
max_num = A[0]
min_num = A[-1]
exchanges = [() for i in range(N-1)]
for i in range(1,N-1):
    if A[i] < 0:
        exchanges[i-1] = (max_num,A[i])
        max_num = max_num - A[i]
    else:
        exchanges[i-1] = (min_num,A[i])
        min_num = min_num - A[i]

exchanges[-1] = (max_num,min_num)
ans = max_num-min_num
print(ans)
for i in range(N-1):
    a,b = exchanges[i]
    print(a,b)

Submission status: Accepted

Solution code:
#  --*-coding:utf-8-*--

def f(N, A):
    ps = sorted(filter(lambda x: x>= 0, A))
    ns = sorted(filter(lambda x: x<0, A))

    if len(ps) == 0:
        ps.append(ns.pop())
    elif len(ns) == 0:
        ns.append(ps.pop(0))

    m = 0
    ops = []

    if len(ps) == 1:
        m = ps[0]

        for x in ns:
            ops.append(str(m) + ' ' + str(x))
            m -= x

    elif len(ns) == 1:
        m = ns[0]

        for x in ps[:-1]:
            ops.append(str(m) + ' ' + str(x))
            m -= x

        ops.append(str(ps[-1]) + ' ' + str(m))
        m = ps[-1] - m

    else:
        p0 = ps.pop()
        n0 = ns.pop()
        
        for x in ns:
            ops.append(str(p0) + ' ' + str(x))
            p0 -= x

        for x in ps:
            ops.append(str(n0) + ' ' + str(x))
            n0 -= x

        ops.append(str(p0) + ' ' + str(n0))
        m = p0 - n0
        
    print(m)
    for op in ops:
        print(op)
    


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

    f(N, A)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

pos = []
neg = []
zero = []
for i in range(n):
    if a[i] < 0:
        neg += [i]
    elif a[i] == 0:
        zero += [i]
    else:
        pos += [i]

if zero != [] or (pos != [] and neg != []):
    best = 0
    for i in range(n):
        best += abs(a[i])
    print(best)
else:
    best = 0
    for i in range(n):
        best += abs(a[i])
    if pos == []:
        best -= abs(max(a)) * 2
    else:
        best -= abs(min(a)) * 2
    print(best)

if len(pos) < len(neg):
    pos += zero
    pos.sort()
else:
    neg += zero
    neg.sort()

np = len(pos)
nn = len(neg)
if np == 0 or nn == 0:
    if np == 0: #negative
        index = a.index(max(a))
        x = a[index]
        for i in range(n):
            if i == index:
                continue
            y = a[i]
            print(x, y)
            x -= y
    else: #positive
        index = a.index(min(a))
        x = a[index]
        flag = 0
        if index == 0:
            flag = 1
            
        for i in range(n):
            if i == index or i == flag:
                continue
            y = a[i]
            print(x, y)
            x -= y
        x, y = a[flag], x
        print(x, y)
else:
    x = a[neg[0]]
    for k in range(np-1):
        y = a[pos[k]]
        print(x, y)
        x -= y
        
    y = x
    x = a[pos[np-1]]
    print(x, y)
    x -= y
    for k in range(1, nn):
        y = a[neg[k]]
        print(x, y)
        x -= y

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

from collections import defaultdict

N = int(input())
X = list(map(int, input().rstrip().split(' ')))
X = sorted(X)

count_minus = sum([1 if x < 0 else 0 for x in X])

if N == 2:
    print(X[1] - X[0])
    print(X[1], X[0])
else:
    ope = []
    min_value = X[0]
    max_value = X[-1]
    start = 1
    end = N-1

    for i in range(start, end):
        if X[i] < 0:
            ope.append([max_value, X[i]])
            max_value -= X[i]
        else:
            ope.append([min_value, X[i]])
            min_value -= X[i]
    ope.append([max_value, min_value])
    
    print(max_value - min_value)
    for i in range(len(ope)):
        a, b = ope[i]
        print(a, b)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


def neg_pos(neg: list, pos: list):
    cur = neg[0]
    path = []
    for posi in pos[1:]:
        path.append((cur, posi))
        cur -= posi

    neg[0] = cur
    cur = pos[0]

    for negi in neg:
        path.append((cur, negi))
        cur -= negi

    print(cur)
    for pathi in path:
        print(*pathi)

    return


def neg_only(neg: list):
    cur = neg[0]
    path = []
    for negi in neg[1:]:
        path.append((cur, negi))
        cur -= negi

    print(cur)
    for pathi in path:
        print(*pathi)

    return

def pos_only(pos: list):
    cur = pos[0]
    path = []
    for posi in pos[1:-1]:
        path.append((cur, posi))
        cur -= posi

    path.append((pos[-1], cur))
    cur = pos[-1] - cur

    print(cur)
    for pathi in path:
        print(*pathi)

    return


n = ni()
a = list(li())

neg = []
pos = []

for ai in a:
    if ai < 0:
        neg.append(ai)
    else:
        pos.append(ai)

neg.sort(reverse=True)
pos.sort()


if len(neg) == 0:
    pos_only(pos)

elif len(pos) == 0:
    neg_only(neg)

else:
    neg_pos(neg, pos)

Submission status: Accepted

Solution code:
import bisect

N = int(input())
A = [int(_) for _ in input().split()]
plusflag = minusflag = False

for i in A:
    if not plusflag and i > 0:
        plusflag = True
    elif not minusflag and i < 0:
        minusflag = True
    
    if plusflag and minusflag:
        break

if not plusflag and not minusflag:
    print(0)
    for i in range(N-1):
        print(0, 0)
elif not plusflag and minusflag:
    A = sorted(A)[::-1]
    print(A[0]-sum(A[1:]))
    tmp = A[0]
    for i in range(N-1):
        x = tmp
        y = A[i+1]
        print(x, y)
        tmp -= y
elif plusflag and not minusflag:
    A = sorted(A)
    print(-A[0]+sum(A[1:]))
    tmp = A[0]
    for i in range(N-2):
        x = tmp
        y = A[i+1]
        print(x, y)
        tmp -= y
    print(A[-1], tmp)
else:
    A = sorted(A)
    zeroindex = bisect.bisect_left(A, 0)
    print(-sum(A[:zeroindex])+sum(A[zeroindex:]))
    if zeroindex != N-1:
        print(A[zeroindex-1], A[zeroindex])
        tmp = A[zeroindex-1] - A[zeroindex]
        for i in range(zeroindex+1, N-1):
            x = tmp
            y = A[i]
            print(x, y)
            tmp -= y
        print(A[-1], tmp)
        tmp = A[-1] - tmp
        for i in range(zeroindex-1):
            x = tmp
            y = A[i]
            print(x, y)
            tmp -= y
    else:
        tmp = A[-1]
        for i in range(N-1):
            x = tmp
            y = A[i]
            print(x, y)
            tmp -= y

Submission status: Accepted

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

i_plus = 0
# 最後のプラスになるタイミングを持っておく
plusflg = True
for i,A in enumerate(As):
    if A < 0:
        i_plus = i
        plusflg = False
        break

if plusflg:
    i_plus = N-1

ans = sum(As)
for i,A in enumerate(As[::-1]):
    if i == N-1:
        continue
    elif i == 0 or A < 0:
        ans -= 2*A
print(ans)

now = As[-1]
for i,A in enumerate(As[:-1]):
    if i+1 < i_plus:
        print(now,A)
        now -= A
    elif i+1 == i_plus:
        print(A, now)
        now = (A-now)
    else:
        print(max(A,now),min(A,now))        
        now = max(A,now)-min(A,now)

Submission status: Accepted

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

a_max = a.pop(a.index(max(a)))
a_min = a.pop(a.index(min(a)))
for v in a:
    if v >= 0:
        p.append(v)
    else:
        c.append(v)
        
s = a_min
if n == 2:
    print(a_max - a_min)
    print(a_max, a_min)
    
else:
    t = [a_min]
    if p != []:
        for v in p:
            s -= v
            t.append(s)
    ans = a_max - s
    t.append(ans)
    if c != []:
        for v in c:
            ans -= v
            t.append(ans)
    print(ans)
    tmp = len(p)
    if p != []:
        for i in range(0, tmp):
            print(t[i], p[i])
    print(a_max, t[tmp])
    if c != []:
        for i in range(0, len(c)):
            print(t[tmp+i+1], c[i])