Official Analysis (C++)

Explanation

Sorting the entire array with just one operation seems a little intimidating.

The way to simplify this is to look at adjacent pairs of elements instead. If for each pair of elements $a$ and $b$ we made it so that $|a-x| \le |b-x|$, then this would imply the entire array being sorted!

There's still a little casework after noticing this, though:

1. If $a < b$, we know $x \le \left\lfloor\frac{a+b}{2}\right\rfloor$. Intuitively, this means that we can't put $x$ past the middle of $a$ and $b$, as that would make $x$ closer to $b$ than it is to $a$.
2. If $a > b$, we similarly have $x \ge \left\lceil\frac{a+b}{2}\right\rceil$.
3. Otherwise, both are equal and it doesn't matter what value of $x$ we choose.

All these pairs limit $x$ to a (possibly empty) range of numbers. We keep track of this range as we go along the array and output any element in it at the end.

Implementation

Time Complexity: $\mathcal{O}(n)$

Copy
#include <algorithm>
#include <cstdint>
#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::vector;

/**

Copy
import java.io.*;
import java.util.*;

public class AbsoluteSorting {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
		int testNum = Integer.parseInt(read.readLine());
		for (int t = 0; t < testNum; t++) {
			int len = Integer.parseInt(read.readLine());
			int[] arr = Arrays.stream(read.readLine().split(" "))

Copy
def ceildiv(a, b):
	return -(a // -b)


for _ in range(int(input())):
	len_ = int(input())
	arr = [int(i) for i in input().split()]
	assert len(arr) == len_

	at_least = -float("inf")