BOJ. Two Liquid (2470)

BOJ 2470: Two Liquids · 한국어 · 日本語

Given N distinct solutions, choose two different entries whose sum is closest to zero. Sort the values, then place one pointer at each end. At every step, the two pointed-to entries are a valid candidate; remember the pair whenever its absolute sum is smaller than the best seen. If the sum is negative, move the left pointer right to increase it. If it is positive, move the right pointer left to decrease it. Stop immediately when the sum is zero, since no absolute sum can be smaller.

This also handles arrays whose values all have the same sign: the pointers still examine pairs, and the movement rule progresses until all viable improvements have been considered. The indices always satisfy left < right, so the selected entries are distinct. Widen values to long before adding, and compare absolute magnitudes without narrowing or subtracting potentially large values. Sorting costs O(N log N) and the scan costs O(N), for O(N log N) time overall and O(N) space for the sorted copy.

Java

import java.io.BufferedInputStream;
import java.io.IOException;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException {
        FastScanner input = new FastScanner();
        int n = input.nextInt();
        int[] values = new int[n];
        for (int i = 0; i < n; i++) {
            values[i] = input.nextInt();
        }
        Arrays.sort(values);

        int left = 0;
        int right = n - 1;
        int bestLeft = left;
        int bestRight = right;
        long bestAbs = Long.MAX_VALUE;

        while (left < right) {
            long sum = (long) values[left] + values[right];
            long absSum = Math.abs(sum);
            if (absSum < bestAbs) {
                bestAbs = absSum;
                bestLeft = left;
                bestRight = right;
            }

            if (sum == 0) {
                break;
            } else if (sum < 0) {
                left++;
            } else {
                right--;
            }
        }

        System.out.println(values[bestLeft] + " " + values[bestRight]);
    }

    private static class FastScanner {
        private final BufferedInputStream input = new BufferedInputStream(System.in);

        int nextInt() throws IOException {
            int c;
            do {
                c = input.read();
            } while (c <= ' ' && c != -1);

            int value = 0;
            int sign = 1;
            if (c == '-') {
                sign = -1;
                c = input.read();
            }
            while (c > ' ') {
                value = value * 10 + c - '0';
                c = input.read();
            }
            return sign * value;
        }
    }
}

JavaScript

const fs = require('fs');
const input = fs.readFileSync(0, 'utf8').trim().split(/\s+/).map(BigInt);
const n = Number(input[0]);
const values = input.slice(1, n + 1).sort((a, b) => (a < b ? -1 : a > b ? 1 : 0));

let left = 0;
let right = n - 1;
let bestLeft = left;
let bestRight = right;
let bestAbs = null;

while (left < right) {
    const sum = values[left] + values[right];
    const absSum = sum < 0n ? -sum : sum;
    if (bestAbs === null || absSum < bestAbs) {
        bestAbs = absSum;
        bestLeft = left;
        bestRight = right;
    }

    if (sum === 0n) {
        break;
    } else if (sum < 0n) {
        left++;
    } else {
        right--;
    }
}

console.log(`${values[bestLeft]} ${values[bestRight]}`);

BigInt keeps both addition and absolute-value comparison exact. The selected indices remain ordered, so the output values are in sorted order and come from two distinct input entries.