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: Time Limit Exceeded

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]

def main():
    n = int(input())
    a = sorted(list(map(int, input().split())))
    a_m = [aa for aa in a if aa < 0]
    a_p = [aa for aa in a if aa >= 0]
    sousa = []
    flag = 1
    if len(a_m) == 0:
        while len(a_m) == 0:
            if len(a_p) == 2:
                sousa += [[a_p[1], a_p[0]]]
                a_m += [a_p.pop(-1) - a_p.pop(-1)]
                flag = 0
            else:
                tmp = 1
                for i in range(len(a_p) - 1):
                    if a_p[0] - a_p[i + 1] < 0:
                        sousa += [[a_p[i], a_p[i + 1]]]
                        a_m += [a_p.pop(0) - a_p.pop(i)]
                        tmp = 0
                        break
                if tmp:
                    sousa += [[a_p[i], a_p[i + 1]]]
                    a_p = [a_p.pop(0) - a_p.pop(0)] + a_p
    elif len(a_p) == 0:
        while len(a_p) == 0:
            if len(a_m) == 2:
                sousa += [[a_m[1], a_p[0]]]
                a_p += [a_m.pop(-1) - a_m.pop(-1)]
                flag = 0
            else:
                tmp = 1
                for i in range(len(a_m) - 1):
                    if a_m[-1] - a_m[i] > 0:
                        sousa += [[a_m[i + 1], a_m[i]]]
                        a_p += [a_m.pop(-1) - a_m.pop(i)]
                        tmp = 0
                        break
                if tmp:
                    sousa += [[a_m[i + 1], a_m[i]]]
                    a_p += [a_m.pop(-1) - a_m.pop(-1)]
    if flag:
        while len(a_p) > 1:
            sousa += [[a_m[0], a_p[0]]]
            a_m += [a_m.pop(0) - a_p.pop(0)]
        while len(a_m) > 0:
            sousa += [[a_p[0], a_m[0]]]
            a_p += [a_p.pop(0) - a_m.pop(0)]
        print(a_p[0])
    else:
        if len(a_p) > len(a_m):
            print(a_p[0])
        else:
            print(a_m[0])
    for i in sousa:
        print(*i)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

xy = []

while N >= 2:
    if A[-2] > 0:
        y = A.pop()
        x = A[0]

        xy.append([x,y])

        A[0] = x-y

    else:
        while N >= 2:
            x = A.pop()
            y = A.pop(0)

            xy.append([x,y])

            A.append(x-y)
            N -= 1
        break
    
    N -= 1

print(A[0])
for x, y in xy:
    print(x,y)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import numpy as np
N = int(input())
values = []
A = list(map(int, input().split()))
perms = list(itertools.permutations(A))
perms = list(set(perms))
for i, perm in enumerate(perms):
    temp = perm[0]
    for n in range(1, N):
        temp = perm[n] - temp
    values.append(temp)
print(max(values))

perm = perms[np.argmax(values)]
temp = perm[0]
for n in range(1, N):
    print(perm[n], temp)
    temp = perm[n] - temp

Submission status: Time Limit Exceeded

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

xy = []

while N >= 2:
    if A[-2] > 0:
        y = A.pop()
        x = A[0]

        xy.append([x,y])

        A[0] = x-y

    else:
        x = A.pop()
        y = A.pop(0)

        xy.append([x,y])

        A.append(x-y)
    
    N -= 1

print(A[0])
for x, y in xy:
    print(x,y)

Submission status: Time Limit Exceeded

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

a.sort()
xy = [[] for i in range(N-1)]
cnt = 0
while len(a) > 2:
    if a[len(a)-1] > 0 and a[len(a)-2] > 0:
        n = a[0] - a[len(a)-1]
        xy[cnt] = [a[0], a[len(a)-1]]
        a = a[1:len(a) - 1]
        a.insert(0, n)
    else:
        n = a[len(a)-1] - a[0]
        xy[cnt] = [a[len(a)-1], a[0]]
        a = a[1:len(a) - 1]
        a.append(n)
    cnt += 1

m = a[1] - a[0]
xy[cnt] = [a[1], a[0]]
print(m)
for _xy in xy:
    print(str(_xy[0]) + " " + str(_xy[1]))

Submission status: Time Limit Exceeded

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

xy = []

while N >= 2:
    if A[-2] > 0:
        y = A.pop()
        x = A.pop(0)

        xy.append([x,y])

        A = [x-y] + A

    else:
        x = A.pop()
        y = A.pop(0)

        xy.append([x,y])

        A.append(x-y)
    
    N -= 1

print(A[0])
for x, y in xy:
    print(x,y)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
#print(N, A)
x = []
y = []
for i in range(N -1):
    amin = min(A)
    A.remove(min(A))
    amax = max(A)
    A.remove(max(A))
    #print(A, amin, amax)
    if i != N - 2:
        amin2 = abs(min(A))
        amax2 = abs(max(A))
        #print(amax2, amin2)
        if i == N - 3:
            if A[0] < 0:
                A.append(amax - amin)
                x.append(amax)
                y.append(amin)
            else:
                A.append(amin - amax)
                x.append(amin)
                y.append(amax)
        else:
            if amax2 > amin2:
                A.append(amin - amax)
                x.append(amin)
                y.append(amax)
            else:
                A.append(amax - amin)
                x.append(amax)
                y.append(amin)
    else:
        A.append(amax - amin)
        x.append(amax)
        y.append(amin)

    #print("A", A)

print(A[0])
#print(x, y)
for i in range(N - 1):
    print(x[i], y[i])

Submission status: Time Limit Exceeded

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

a.sort()
xy = []
while len(a) > 2:
    if a[len(a)-1] > 0 and a[len(a)-2] > 0:
        n = a[0] - a[len(a)-1]
        xy.append([a[0], a[len(a)-1]])
        a = a[1:len(a) - 1]
        a.insert(0, n)
    else:
        n = a[len(a)-1] - a[0]
        xy.append([a[len(a)-1], a[0]])
        a = a[1:len(a) - 1]
        a.append(n)

m = a[1] - a[0]
xy.append([a[1], a[0]])
print(m)
for _xy in xy:
    print(str(_xy[0]) + " " + str(_xy[1]))

Submission status: Time Limit Exceeded

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

mi = True
pl = True
for i in range(n):
    if a[i] <= 0:
        pl = False
    if a[i] >= 0:
        mi = False

a_abs = []
for i in range(n):
    a_abs.append(abs(a[i]))
m = 0
if mi == pl == False:
    m=sum(a_abs)
else:
    m=sum(a_abs)-2*min(a_abs)
print(m)

while len(a)>1:
    x, y = max(a), min(a)
    a.remove(x)
    a.remove(y)
    if len(a)==0:
        print(x,y)
        break
    elif min(a) > 0:
        print(y,x)
        a.append(y-x)
    else:
        print(x,y)
        a.append(x-y)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import numpy as np
N = int(input())
values = []
A = list(map(int, input().split()))
perms = list(itertools.permutations(A))
for i, perm in enumerate(perms):
    temp = perm[0]
    for n in range(1, N):
        temp = perm[n] - temp
    values.append(temp)
print(max(values))

perm = perms[np.argmax(values)]
temp = perm[0]
for n in range(1, N):
    print(perm[n], temp)
    temp = perm[n] - temp

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
#print(N, A)
x = []
y = []
for i in range(N -1):
    amin = min(A)
    A.remove(min(A))
    amax = max(A)
    A.remove(max(A))
    #print(A, amin, amax)
    if i != N - 2:
        amin2 = abs(min(A))
        amax2 = abs(max(A))
        #print(amax2, amin2)
        if len(A) == 1:
            if A[0] < 0:
                A.append(amax - amin)
                x.append(amax)
                y.append(amin)
            else:
                A.append(amin - amax)
                x.append(amin)
                y.append(amax)
        else:
            if amax2 > amin2:
                A.append(amin - amax)
                x.append(amin)
                y.append(amax)
            else:
                A.append(amax - amin)
                x.append(amax)
                y.append(amin)
    else:
        A.append(amax - amin)
        x.append(amax)
        y.append(amin)

    #print("A", A)

print(A[0])
#print(x, y)
for i in range(N - 1):
    print(x[i], y[i])

Submission status: Time Limit Exceeded

Solution code:
n = input()
n = int(n)
num = []*n
numint = []
num = input().split(' ')
for i in range(len(num)):
    numint.append(int(num[i]))
i = 0
x, y = int, int
word = []

numint = sorted(numint)
x = numint[0]
y = numint[1]
word.append(str(x) + " " + str(y))
numint.append(x - y)
numint.pop(0)
numint.pop(0)
while len(numint) > 1:
    numint = sorted(numint)
    x = numint[0]
    y = numint[1]
    if x < y:
        a, b = x, y
        x, y = b,a
        word.append(str(x) + " " + str(y))
        numint.append(x - y)
        numint.pop(0)
        numint.pop(0)
print(numint[0])
for i in range(len(word)):
    print(word[i])

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]

def main():
    n = int(input())
    a = sorted(list(map(int, input().split())))
    a_m = [aa for aa in a if aa < 0]
    a_p = [aa for aa in a if aa >= 0]
    sousa = []

    while len(a_m) + len(a_p) > 1:
        if len(a_m) == 0:
            if len(a_p) == 2:
                sousa += [[a_p[1], a_p[0]]]
                a_p += [a_p.pop(-1) - a_p.pop(-1)]
            else:
                tmp = 1
                for i in range(len(a_p) - 1):
                    if a_p[0] - a_p[i + 1] < 0:
                        sousa += [[a_p[i], a_p[i + 1]]]
                        a_m += [a_p.pop(0) - a_p.pop(i)]
                        tmp = 0
                        break
                if tmp:
                    sousa += [[a_p[i], a_p[i + 1]]]
                    a_p = [a_p.pop(0) - a_p.pop(0)] + a_p
        elif len(a_p) == 0:
            if len(a_m) == 2:
                sousa += [[a_m[1], a_p[0]]]
                a_m += [a_m.pop(-1) - a_m.pop(-1)]
            else:
                tmp = 1
                for i in range(len(a_m) - 1):
                    if a_m[-1] - a_m[i] > 0:
                        sousa += [[a_m[i + 1], a_m[i]]]
                        a_p += [a_m.pop(-1) - a_m.pop(i)]
                        tmp = 0
                        break
                if tmp:
                    sousa += [[a_m[i + 1], a_m[i]]]
                    a_p += [a_m.pop(-1) - a_m.pop(-1)]
        elif len(a_m) >= len(a_p):
            sousa += [[a_p[0], a_m[0]]]
            a_p += [a_p.pop(0) - a_m.pop(0)]
        elif len(a_m) < len(a_p):
            sousa += [[a_m[0], a_p[0]]]
            a_m += [a_m.pop(0) - a_p.pop(0)]

    if len(a_m) > len(a_p):
        print(a_m[0])
    else:
        print(a_p[0])
    for i in sousa:
        print(*i)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

debug = logging.getLogger(__name__).debug


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


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

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

            yield u, prev_dict, cost_dict

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

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


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


def _main():
    n, = input_ints()
    a = input_ints()
    ans_max = sum(map(abs, a))

    result = a_star(
        succ=lambda u: [
            ((u[i][0] - u[j][0], (u[i][0], u[j][0])),) + tuple(
                u[k]
                for k in range(len(u))
                if i != k and j != k
            )
            for i in range(len(u))
            for j in range(len(u))
            if i != j
        ],
        cost=lambda u, v: (
                sum(abs(a_) for a_, _ in u)
                - sum(abs(a_) for a_, _ in v)),
        heuristic=lambda u: 0,
        start=tuple((a_, None) for a_ in a),
    )
    for result in result:
        if len(result[0]) == 1:
            break
    _, prev_dict, *_ = result
    last = max(key for key in prev_dict if len(key) == 1)
    print(last[0][0])
    path = []
    while last in prev_dict:
        path.append(last[0][1])
        last = prev_dict[last]
    for p in path[::-1]:
        print(*p)


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

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


if __name__ == '__main__':
    _main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]

def main():
    n = int(input())
    a = list(map(int, input().split()))
    a_m = [aa for aa in a if aa < 0]
    a_p = [aa for aa in a if aa >= 0]
    sousa = []

    while len(a_m) + len(a_p) > 1:
        if len(a_m) == 0:
            a_p.sort()
            if len(a_p) == 2:
                sousa += [[a_p[1], a_p[0]]]
                a_p += [a_p.pop(-1) - a_p.pop(-1)]
            else:
                tmp = 1
                for i in range(len(a_p) - 1):
                    if a_p[0] - a_p[i + 1] < 0:
                        sousa += [[a_p[i], a_p[i + 1]]]
                        a_m += [a_p.pop(0) - a_p.pop(i)]
                        tmp = 0
                        break
                if tmp:
                    sousa += [[a_p[i], a_p[i + 1]]]
                    a_p += [a_p.pop(0) - a_p.pop(0)]
        elif len(a_p) == 0:
            a_m.sort()
            if len(a_m) == 2:
                sousa += [[a_m[1], a_p[0]]]
                a_m += [a_m.pop(-1) - a_m.pop(-1)]
            else:
                tmp = 1
                for i in range(len(a_m) - 1):
                    if a_m[-1] - a_m[i] > 0:
                        sousa += [[a_m[i + 1], a_m[i]]]
                        a_p += [a_m.pop(-1) - a_m.pop(i)]
                        tmp = 0
                        break
                if tmp:
                    sousa += [[a_m[i + 1], a_m[i]]]
                    a_p += [a_m.pop(-1) - a_m.pop(-1)]
        elif len(a_m) >= len(a_p):
            sousa += [[a_p[0], a_m[0]]]
            a_p += [a_p.pop(0) - a_m.pop(0)]
        elif len(a_m) < len(a_p):
            sousa += [[a_m[0], a_p[0]]]
            a_m += [a_m.pop(0) - a_p.pop(0)]

    if len(a_m) > len(a_p):
        print(a_m[0])
    else:
        print(a_p[0])
    for i in sousa:
        print(*i)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
_ = input()
lis = list(map(int, input().split()))
hist = []

while len(lis) > 2:
    minRes = lis[1] - lis[0]
    minRes_A = lis[1]
    minRes_B = lis[0]

    for i in range(len(lis)):
        for j in range(i):
            if minRes > lis[i] - lis[j]:
                minRes = lis[i] - lis[j]
                minRes_A = lis[i]
                minRes_B = lis[j]

    lis.remove(minRes_A)
    lis.remove(minRes_B)
    lis = lis + [minRes]
    hist = hist + [(minRes_A, minRes_B)]

hist = hist + [(max(lis),min(lis))]

print(max(lis) - min(lis))
for (a,b) in hist:
    print("{} {}".format(a,b))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))
A.sort()
L=[]
for i in range(N):
    if len(A)>=3:
        a=A.pop(0)
        b=A.pop(-1)
        if (b-a)-A[0] >= A[-1]-(a-b):
            A.append(b-a)
            L.append([b,a])
        else:
            A.insert(0,a-b)
            L.append([a,b])
    elif len(A)==2:
        a = A.pop(0)
        b = A.pop(-1)
        A.append(b-a)
        L.append([b,a])
        break
    else:
        break
print(A[0])
for j in L:
    print(j[0],j[1],sep=' ')

Submission status: Time Limit Exceeded

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

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

debug = logging.getLogger(__name__).debug


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


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

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

            yield u, prev_dict, cost_dict

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

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


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


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

    result = a_star(
        succ=lambda u: [
            ((u[i][0] - u[j][0], (u[i][0], u[j][0])),) + tuple(
                u[k]
                for k in range(len(u))
                if i != k and j != k
            )
            for i in range(len(u))
            for j in range(len(u))
            if i != j
        ],
        cost=lambda u, v: sum(abs(a_) for a_, _ in u) - sum(abs(a_) for a_, _ in v),
        heuristic=lambda u: 0,
        start=tuple((a_, None) for a_ in a),
    )
    for result in result:
        pass
    _, prev_dict, *_ = result
    last = max(key for key in prev_dict if len(key) == 1)
    print(last[0][0])
    path = []
    while last in prev_dict:
        path.append(last[0][1])
        last = prev_dict[last]
    for p in path[::-1]:
        print(*p)


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

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


if __name__ == '__main__':
    _main()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
li = list(map(int,input().split()))
li.sort()
ans=[]
dekai=0
tiisai=0
for i in range(n):
    if li[i]<=0:
        tiisai+=1
    else:
        dekai=n-i
        break
while len(li)>1:
    if dekai>tiisai:
        x=li.pop(0)
        y=li.pop()
        dekai-=1
        if x==y:
            dekai-=1
            tiisai+=1
    else:
        x=li.pop()
        y=li.pop(0)
        tiisai-=1
        if x==y:
            dekai-=1
            tiisai+=1
    ans.append([x,y])
    n=x-y
    for i in range(len(li)):
        if li[i]>=n:
            li.insert(i,n)
            break
    else:
        li.append(n)
print(li[0])
for i in range(len(ans)):
    print(ans[i][0],ans[i][1])

Submission status: Time Limit Exceeded

Solution code:
#

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

def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    index = bisect.bisect_left(A, 0)
    minus = A[:index]
    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(0)
            val2 = minus.pop()
            new_val = val1 - val2
            plus.append(new_val)
            progres.append((val1, val2))
            # 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(0)
            new_val = val2 - val1
            progres.append((val2, val1))

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

            index = bisect.bisect_left(plus, new_val)
            plus.insert(index, new_val)
            # print('{} {}'.format(val1, val2))

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
inpt = input()
A = [int(a) for a in inpt.split()]
outputs = []
for i in range(N-1):
    negative = 0
    positive = 0
    for a in A:
        if a > 0:
            positive += 1
        elif a <= 0:
            negative += 1
    maxA = max(A)
    minA = min(A)
    if positive > negative:
        A.append(min(A)-max(A))
        outputs.append(str(minA)+" "+str(maxA))
    else:
        A.append(max(A)-min(A))
        outputs.append(str(maxA)+" "+str(minA))
    A.remove(maxA)
    A.remove(minA)

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
INPUT = list(map(int, input().split()))
POSs = []
NEGs = []
for e in INPUT:
    if e > 0:
        POSs.append(e)
    else:
        NEGs.append(e)

res = []
while len(POSs) + len(NEGs) > 2:
    if len(NEGs) == 0:
        pos_min = min(POSs)
        pos_max = max(POSs)
        POSs.remove(pos_min)
        POSs.remove(pos_max)
        res.append([pos_min, pos_max])
        new_val = pos_min - pos_max
    elif len(POSs) == 0:
        neg_min = min(NEGs)
        neg_max = max(NEGs)
        NEGs.remove(neg_min)
        NEGs.remove(neg_max)
        res.append([neg_max, neg_min])
        new_val = neg_max - neg_min
    elif len(POSs) > 1:
        pos_min = min(POSs)
        POSs.remove(pos_min)
        neg = NEGs.pop()
        res.append([neg, pos_min])
        new_val = neg - pos_min
    else:
        pos = POSs.pop()
        neg = NEGs.pop()
        res.append([pos, neg])
        new_val = pos - neg

    if new_val < 0:
        NEGs.append(new_val)
    else:
        POSs.append(new_val)

last_pair = POSs + NEGs
M = max(last_pair)
m = min(last_pair)
res.append([M, m])
print(M - m)
for el in res:
    print(el[0], el[1])

Submission status: Time Limit Exceeded

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

p = [i for i in a if i >= 0]
n = [i for i in a if i < 0]

process = []
if len(p) > 0 and len(n) > 0:
    p_seed = p.pop(0)
    n_seed = n.pop(0)
    while len(n) > 0:
        sub = n.pop(0)
        process.append((p_seed, sub))
        p_seed -= sub
    while len(p) > 0:
        sub = p.pop(0)
        process.append((n_seed, sub))
        n_seed -= sub
    process.append((p_seed, n_seed))
elif len(p) > 0:
    p.sort(reverse=True)
    p_seed = p.pop(0)
    n_seed = p.pop(-1)
    while len(p) > 0:
        sub = p.pop(0)
        process.append((n_seed, sub))
        n_seed -= sub
    process.append((p_seed, n_seed))
else:
    n.sort(reverse=True)
    p_seed = n.pop(0)
    n_seed = n.pop(-1)
    while len(n) > 0:
        sub = n.pop(0)
        process.append((n_seed, sub))
        p_seed -= sub
    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: Time Limit Exceeded

Solution code:
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 <= N-3:
            x = A.pop(0)
            y = A.pop(-1)
            print(x, y)
            A.insert(0, x - y)
        else:
            x = A.pop(1)
            y = A.pop(0)
            print(x, y)
elif A[-1] <= 0:
    M = sum(A[:-1]) * (-1) + A[-1]
    print(M)
    for i in range(N-1):
        if i <= N-3:
            x = A.pop(-1)
            y = A.pop(0)
            print(x, y)
            A.insert(N-i-2,x-y)
        else:
            #print(A)
            x = A.pop(1)
            y = A.pop(0)
            print(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 <= N - 3:
                x = A.pop(0)
                y = A.pop(-1)
                print(x, y)
                A.insert(0, x - y)
            else:
                x = A.pop(1)
                y = A.pop(0)
                print(x, y)
    else:
        for i in range(N - 1):
            if i <= N - 3 and A[1] < 0:
                x = A.pop(-1)
                y = A.pop(0)
                print(x, y)
                A.insert(N - i - 2, x - y)
            elif i <= N-3 :
                x = A.pop(0)
                y = A.pop(-1)
                print(x,y)
                A.insert(0, x - y)
            else:
                # print(A)
                x = A.pop(1)
                y = A.pop(0)
                print(x, y)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))
A.sort()
L=[]
for i in range(N):
    if len(A)>=3:
        a=A.pop(0)
        b=A.pop(-1)
        if (b-a)-A[0] >= A[-1]-(a-b):
            A.append(b-a)
            A.sort()
            L.append([b,a])
        else:
            A.append(a-b)
            A.sort()
            L.append([a,b])
    elif len(A)==2:
        a = A.pop(0)
        b = A.pop(-1)
        A.append(b-a)
        L.append([b,a])
        break
    else:
        break
print(A[0])
for j in L:
    print(j[0],j[1],sep=' ')

Submission status: Time Limit Exceeded

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(1)
    tmp = al - ar
    ans_op.append([al, ar])
    A.insert(0, tmp)
    N -= 1
for i in range(N-1):
    if A[-2] <= 0:
        al = A.pop(-1)
        ar = A.pop(-1)
        tmp = al - ar
        ans_op.append([al, ar])
        A.append(tmp)
    else:
        al = A.pop(0)
        ar = A.pop(-1)
        tmp = al - ar
        ans_op.append([al, ar])
        A.insert(0, tmp)

print(A[0])
for op in ans_op:
    print(op[0], op[1])

Submission status: Time Limit Exceeded

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

for i in range(N-1):
    if (N-i) % 2 == 0:
        ans += [A[-1],A[0]]
        n = A[-1] - A[0]
        j = 0
        while n > A[j]:
            j += 1
            if j == (N-i)-1:    break
        A = A[1:j] + [n] + A[j:(N-i)-1]

    else:
        ans += [A[0],A[-1]]
        n = A[0] - A[-1]
        j = (N-i)-1
        while n < A[j]:
            j -= 1
            if j == 0:    break
        A = A[1:j] + [n] + A[j:(N-i)-1]

print(A[0])          
for i in range(N-1):
    print(ans[2*i],ans[2*i+1])

Submission status: Time Limit Exceeded

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:
    tmp = A[-1] - A[-2]
    ans_op.append([A[-1], A[-2]])
    A = A[:-2]
    A.append(tmp)
elif A[0] > 0 and A[-1] > 0:
    tmp = A[0] - A[1]
    ans_op.append([A[0], A[1]])
    A = A[2:]
    A.insert(tmp, 0)
while len(A) != 1:
    if A[-2] <= 0:
        tmp = A[-1] - A[-2]
        ans_op.append([A[-1], A[-2]])
        A = A[:-2]
        A.append(tmp)
    else:
        tmp = A[0] - A[-1]
        ans_op.append([A[0], A[-1]])
        A = A[1:-1]
        A.insert(0, tmp)

print(A[0])
for op in ans_op:
    print(op[0], op[1])

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
li = list(map(int,input().split()))
ans=[]
dekai=0
tiiisai=0
for i in range(n):
    if li[i]<0:
        tiiisai+=1
    else:
        dekai+=1
while len(li)>1:
    if dekai>tiiisai:
        x=li.pop(li.index(min(li)))
        y=li.pop(li.index(max(li)))
        dekai-=1
        if x==y:
            dekai-=1
            tiiisai+=1
    else:
        x=li.pop(li.index(max(li)))
        y=li.pop(li.index(min(li)))
        tiiisai-=1
        if x==y:
            dekai-=1
            tiiisai+=1
    ans.append([x,y])
    li.append(x-y)
print(li[0])
for i in range(len(ans)):
    print(ans[i][0],ans[i][1])