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: Wrong Answer

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

import os
import sys
from __builtin__ import xrange as range
from cStringIO import StringIO
from future_builtins import ascii, filter, hex, map, oct, zip
from io import IOBase

import __pypy__

import random


class TreapMultiSet(object):
    root = 0
    size = 0

    def __init__(self, data=None):
        if data:
            data = sorted(data)
            self.root = treap_builder(data)
            self.size = len(data)

    def add(self, key):
        self.root = treap_insert(self.root, key)
        self.size += 1

    def remove(self, key):
        self.root = treap_erase(self.root, key)
        self.size -= 1

    def discard(self, key):
        try:
            self.remove(key)
        except KeyError:
            pass

    def ceiling(self, key):
        x = treap_ceiling(self.root, key)
        return treap_keys[x] if x else None

    def higher(self, key):
        x = treap_higher(self.root, key)
        return treap_keys[x] if x else None

    def floor(self, key):
        x = treap_floor(self.root, key)
        return treap_keys[x] if x else None

    def lower(self, key):
        x = treap_lower(self.root, key)
        return treap_keys[x] if x else None

    def max(self):
        return treap_keys[treap_max(self.root)]

    def min(self):
        return treap_keys[treap_min(self.root)]

    def __len__(self):
        return self.size

    def __nonzero__(self):
        return bool(self.root)

    __bool__ = __nonzero__

    def __contains__(self, key):
        return self.floor(key) == key

    def __repr__(self):
        return 'TreapMultiSet({})'.format(list(self))

    def __iter__(self):
        if not self.root:
            return iter([])
        out = []
        stack = [self.root]
        while stack:
            node = stack.pop()
            if node > 0:
                if right_child[node]:
                    stack.append(right_child[node])
                stack.append(~node)
                if left_child[node]:
                    stack.append(left_child[node])
            else:
                out.append(treap_keys[~node])
        return iter(out)


class TreapSet(TreapMultiSet):
    def add(self, key):
        self.root, duplicate = treap_insert_unique(self.root, key)
        if not duplicate:
            self.size += 1

    def __repr__(self):
        return 'TreapSet({})'.format(list(self))


class TreapHashSet(TreapMultiSet):
    def __init__(self, data=None):
        if data:
            self.keys = set(data)
            super(TreapHashSet, self).__init__(self.keys)
        else:
            self.keys = set()

    def add(self, key):
        if key not in self.keys:
            self.keys.add(key)
            super(TreapHashSet, self).add(key)

    def remove(self, key):
        self.keys.remove(key)
        super(TreapHashSet, self).remove(key)

    def discard(self, key):
        if key in self.keys:
            self.remove(key)

    def __contains__(self, key):
        return key in self.keys

    def __repr__(self):
        return 'TreapHashSet({})'.format(list(self))


class TreapHashMap(TreapMultiSet):
    def __init__(self, data=None):
        if data:
            self.map = dict(data)
            super(TreapHashMap, self).__init__(self.map.keys())
        else:
            self.map = dict()

    def __setitem__(self, key, value):
        if key not in self.map:
            super(TreapHashMap, self).add(key)
        self.map[key] = value

    def __getitem__(self, key):
        return self.map[key]

    def add(self, key):
        raise TypeError("add on TreapHashMap")

    def get(self, key, default=None):
        return self.map.get(key, default=default)

    def remove(self, key):
        self.map.pop(key)
        super(TreapHashMap, self).remove(key)

    def discard(self, key):
        if key in self.map:
            self.remove(key)

    def __contains__(self, key):
        return key in self.map

    def __repr__(self):
        return 'TreapHashMap({})'.format(list(self))


left_child = [0]
right_child = [0]
treap_keys = [0]
treap_prior = [0.0]


def treap_builder(sorted_data):
    """Build a treap in O(n) time using sorted data"""

    def build(begin, end):
        if begin == end:
            return 0
        mid = (begin + end) // 2
        root = treap_create_node(sorted_data[mid])
        left_child[root] = build(begin, mid)
        right_child[root] = build(mid + 1, end)

        # sift down the priorities
        ind = root
        while True:
            lc = left_child[ind]
            rc = right_child[ind]

            if lc and treap_prior[lc] > treap_prior[ind]:
                if rc and treap_prior[rc] > treap_prior[rc]:
                    treap_prior[ind], treap_prior[rc] = treap_prior[rc], treap_prior[ind]
                    ind = rc
                else:
                    treap_prior[ind], treap_prior[lc] = treap_prior[lc], treap_prior[ind]
                    ind = lc
            elif rc and treap_prior[rc] > treap_prior[ind]:
                treap_prior[ind], treap_prior[rc] = treap_prior[rc], treap_prior[ind]
                ind = rc
            else:
                break
        return root

    return build(0, len(sorted_data))


def treap_create_node(key):
    treap_keys.append(key)
    treap_prior.append(random.random())
    left_child.append(0)
    right_child.append(0)
    return len(treap_keys) - 1


def treap_split(root, key):
    left_pos = right_pos = 0
    while root:
        if key < treap_keys[root]:
            left_child[right_pos] = right_pos = root
            root = left_child[root]
        else:
            right_child[left_pos] = left_pos = root
            root = right_child[root]
    left, right = right_child[0], left_child[0]
    right_child[left_pos] = left_child[right_pos] = right_child[0] = left_child[0] = 0
    return left, right


def treap_merge(left, right):
    where, pos = left_child, 0
    while left and right:
        if treap_prior[left] > treap_prior[right]:
            where[pos] = pos = left
            where = right_child
            left = right_child[left]
        else:
            where[pos] = pos = right
            where = left_child
            right = left_child[right]
    where[pos] = left or right
    node = left_child[0]
    left_child[0] = 0
    return node


def treap_insert(root, key):
    if not root:
        return treap_create_node(key)
    left, right = treap_split(root, key)
    return treap_merge(treap_merge(left, treap_create_node(key)), right)


def treap_insert_unique(root, key):
    if not root:
        return treap_create_node(key), False
    left, right = treap_split(root, key)
    if left and treap_keys[left] == key:
        return treap_merge(left, right), True
    return treap_merge(treap_merge(left, treap_create_node(key)), right), False


def treap_erase(root, key):
    if not root:
        raise KeyError(key)
    if treap_keys[root] == key:
        return treap_merge(left_child[root], right_child[root])
    node = root
    while root and treap_keys[root] != key:
        parent = root
        root = left_child[root] if key < treap_keys[root] else right_child[root]
    if not root:
        raise KeyError(key)
    if root == left_child[parent]:
        left_child[parent] = treap_merge(left_child[root], right_child[root])
    else:
        right_child[parent] = treap_merge(left_child[root], right_child[root])

    return node


def treap_ceiling(root, key):
    while root and treap_keys[root] < key:
        root = right_child[root]
    if not root:
        return 0
    min_node = root
    min_key = treap_keys[root]
    while root:
        if treap_keys[root] < key:
            root = right_child[root]
        else:
            if treap_keys[root] < min_key:
                min_key = treap_keys[root]
                min_node = root
            root = left_child[root]
    return min_node


def treap_higher(root, key):
    while root and treap_keys[root] <= key:
        root = right_child[root]
    if not root:
        return 0
    min_node = root
    min_key = treap_keys[root]
    while root:
        if treap_keys[root] <= key:
            root = right_child[root]
        else:
            if treap_keys[root] < min_key:
                min_key = treap_keys[root]
                min_node = root
            root = left_child[root]
    return min_node


def treap_floor(root, key):
    while root and treap_keys[root] > key:
        root = left_child[root]
    if not root:
        return 0
    max_node = root
    max_key = treap_keys[root]
    while root:
        if treap_keys[root] > key:
            root = left_child[root]
        else:
            if treap_keys[root] > max_key:
                max_key = treap_keys[root]
                max_node = root
            root = right_child[root]
    return max_node


def treap_lower(root, key):
    while root and treap_keys[root] >= key:
        root = left_child[root]
    if not root:
        return 0
    max_node = root
    max_key = treap_keys[root]
    while root:
        if treap_keys[root] >= key:
            root = left_child[root]
        else:
            if treap_keys[root] > max_key:
                max_key = treap_keys[root]
                max_node = root
            root = right_child[root]
    return max_node


def treap_min(root):
    if not root:
        raise ValueError('min on empty treap')
    while left_child[root]:
        root = left_child[root]
    return root


def treap_max(root):
    if not root:
        raise ValueError('max on empty treap')
    while right_child[root]:
        root = right_child[root]
    return root


def main():
    n = int(input())
    t = TreapMultiSet([int(x) for x in input().split()])
    A, B = [], []
    while len(t) > 2:
        a, b = t.min(), t.max()
        t.remove(a), t.remove(b)
        A.append(a), B.append(b)
        t.add(a - b)
    a, b = t.min(), t.max()
    print(b - a)
    A.append(b), B.append(a)
    for a, b in zip(A, B):
        print(a, b)


# region fastio

BUFSIZE = 8192


class FastI(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = StringIO()
        self.newlines = 0

    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("\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()


class FastO(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = __pypy__.builders.StringBuilder()
        self.write = lambda s: self._buffer.append(s)

    def flush(self):
        os.write(self._fd, self._buffer.build())
        self._buffer = __pypy__.builders.StringBuilder()


def print(*args, **kwargs):
    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()


sys.stdin, sys.stdout = FastI(sys.stdin), FastO(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

print(6)
print(-1, 1)
print(2, -4)

Submission status: Wrong Answer

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

saidainosuuji = A[-1]
A = A[:-1]

shuturyoku = []
# while len(A) > 1:
#     shuturyoku.append((A[0], A[-1]))
#     A[0] = A[0] - A[-1]
#     A = A[:-1]

last = len(A)-1
while last > 0:
    shuturyoku.append((A[0], A[last]))
    A[0] = A[0] - A[last]
    last -= 1

shuturyoku.append((saidainosuuji, A[0]))
print(saidainosuuji - A[0])
for sh in shuturyoku:
    print(sh[0], sh[1])

Submission status: Wrong Answer

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

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

queue = sorted(a)

x_list = list()
y_list = list()

while len(queue) != 1:
    if len(queue) > 2:
        head3 = queue[:3]
        head3.sort()
        x = head3[1]
        y = head3[0]
        y_list.append(x)
        x_list.append(y)
        queue = [y - x, head3[2]]
        queue.extend(queue[3:])
    else:
        queue.sort()
        x = queue[1]
        y = queue[0]
        x_list.append(x)
        y_list.append(y)
        queue = [x - y]

print(queue[0])
for x, y in zip(x_list, y_list):
    print(x, y)

Submission status: Wrong Answer

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)
    tmp = a[0]
    for i in range(1, n-1):
        print(tmp, a[i])
        tmp -= a[i]
    print(a[n-1], tmp)
elif a[-1] <= 0:
    m = -sum(a[:-1]) + a[-1]
    print(m)
    tmp = a[n-1]
    for i in range(0, n-1, -1):
        print(tmp, a[i])
        tmp -= a[i]
else:
    m = 0
    pos = []
    neg = []
    for ai in a:
        m += abs(ai)
        if ai >= 0:
            pos.append(ai)
        else:
            neg.append(ai)
    print(m)
    tmp = 0
    ni = 0
    pi = 0

    if len(pos) > 1:
        print(neg[ni], pos[pi])
        tmp = neg[ni] - pos[pi]
        ni += 1
        pi += 1

        while pi < len(pos) - 1:
            print(tmp, pos[pi])
            tmp = tmp - pos[pi]
            pi += 1
        print(pos[pi], tmp)
        tmp = pos[pi] - tmp
        while ni < len(neg):
            print(tmp, neg[ni])
            tmp -= neg[ni]
            ni += 1
    else:
        print(pos[pi] - neg[ni])
        tmp = pos[pi] - neg[ni]
        ni += 1
        while ni < len(neg):
            print(tmp, neg[ni])
            tmp -= neg[ni]
            ni += 1

Submission status: Wrong Answer

Solution code:
from collections import deque
N, *A = map(int, open(0).read().split())

A_MAX = max(A)
deq = deque(sorted(A)[:-1])

ans = []
while len(deq) > 1:
    x = deq.pop()
    y = deq.pop()
    if y >= 0:
        ans.append([x, y])
        if len(deq) > 0 and x - y > deq[-1]:
            deq.append(x - y)
        else:
            deq.appendleft(x - y)
    else:
        ans.append([y, x])
        if len(deq) > 0 and y - x > deq[-1]:
            deq.append(y - x)
        else:
            deq.appendleft(y - x)
    
if deq[0] <= 0:
    print(A_MAX - deq[0])
    ans.append([A_MAX, deq[0]])
else:
    print(deq[0] - A_MAX)
    ans.append([deq[0], A_MAX])
for i in range(N - 1):
    print(*ans[i])

Submission status: Wrong Answer

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

select = []

def maxi(ai):
    if len(ai) == 2:
        select.append("{} {}".format(ai[0], ai[1]))
        return ai[0] - ai[1]
    else:
        if abs(ai[0]) > abs(ai[len(ai)-1]):
            minin = mini(ai[1:])
            if minin < ai[0]:
                select.append("{} {}".format(ai[0], minin))
                return ai[0] - minin
            else:
                select.append("{} {}".format(minin, ai[0]))
                return minin - ai[0]
        else:
            maxin = maxi(ai[:len(ai)-1])
            if maxin > ai[len(ai)-1]:
                select.append("{} {}".format(maxin, ai[len(ai)-1]))
                return maxin - ai[len(ai)-1]
            else:
                select.append("{} {}".format(ai[len(ai)-1], maxin))
                return ai[len(ai)-1] - maxin             

def mini(ai):
    if len(ai) == 2:
        select.append("{} {}".format(ai[1], ai[0]))
        return ai[1] - ai[0]
    else:
        if abs(ai[0]) > abs(ai[len(ai)-1]):
            minin = mini(ai[1:])
            if minin < ai[0]:
                select.append("{} {}".format(minin, ai[0]))
                return minin - ai[0]
            else:
                select.append("{} {}".format(ai[0], minin))
                return ai[0] - minin                
        else:
            maxin = max(ai[:len(ai)-1])
            if maxin > ai[len(ai)-1]:
                select.append("{} {}".format(ai[len(ai)-1], maxin))
                return ai[len(ai)-1] - maxin
            else:
                select.append("{} {}".format(maxin, ai[len(ai)-1]))
                return maxin - ai[len(ai)-1]        

print(maxi(sorted(ai, reverse=True)))
for s in select:
    print(s)

Submission status: Wrong Answer

Solution code:
#C問題
N = int(input())
A = list(map(int,input().split()))
A.sort()
AMIN = A[0]
AMAX = A[-1]
anslist = []
if AMIN*AMAX < 0:
    for i in range(N-1):
        if i == 0:
            pass
        elif A[i] < 0:
            anslist.append([AMAX,A[i]])
            AMAX-=A[i]
        elif A[i] == 0:
            anslist.append([AMAX,A[i]])
        elif A[i] > 0:
            anslist.append([AMIN,A[i]])
            AMIN-=A[i]
    anslist.append([AMAX,AMIN])
    ans = (AMAX-AMIN)
elif AMIN*AMAX >= 0:
    if AMAX >= 0:
        for i in range(N-1):
            if i == 0:
                pass
            elif i == 1:
                anslist.append([A[0],A[1]])
                AMIN = A[0]-A[1]
            else:
                anslist.append([AMIN,A[i]])
                AMIN-=A[i]
        anslist.append([AMAX,AMIN])
        ans = (AMAX-AMIN)
    else:
        B = []
        for i in range(N):
            B.append(-A[N-i-1])
        BMIN = B[0]
        BMAX = B[-1]
        for i in range(N-1):
            if i == 0:
                pass
            elif i == 1:
                anslist.append([-B[0],-B[1]])
                BMIN = B[0]-B[1]
            else:
                anslist.append([-BMIN,-B[i]])
                BMIN-=B[i]
        anslist.append([-BMAX,-BMIN])
        ans = (BMAX-BMIN)
        
print(ans)
for cell in anslist:
    print(cell[0],cell[1])

Submission status: Wrong Answer

Solution code:
n = int(input())
A = sorted(list(map(int,input().split())))
p = 0
P = []
m = 0
M = []
from heapq import heappop,heappush
for a in A:
    if a>=0:
        p += 1
        P.append(a)
    else:
        m += 1
        M.append(a)
cnt = 0
res = []
while cnt != n-1:
    if M != [] and P != []:
        mm = heappop(M)
        pp = heappop(P)
    elif  M != []:
        mm = heappop(M)
        pp = heappop(M)
    elif  P != []:
        mm = heappop(P)
        pp = heappop(P)
    res.append((mm,pp))
    a = mm-pp
    heappush(M,a)
    cnt += 1
print(res[-1][1]-res[-1][0])
for i in range(n-2):
    print(res[i][0],res[i][1])
print(res[-1][1],res[-1][0])

Submission status: Wrong Answer

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


def answer(A, ans):
    A = sorted(A)
    ans.append([A[0], A[1]])
    A[1] = A[0]-A[1]
    return A[1:], ans


while True:
    if len(A) == 2:
        M = A[1]-A[0]
        ans.append([A[1], A[0]])
        break
    A, ans = answer(A, ans)

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