P16707 [SEATST 2026] Vehicle Gathering / Car Gathering

There are $N$ cars on a number line, indexed from $0$ to $N - 1$. You are given their position list $X[0], X[1], \ldots, X[N - 1]$ and their fuel consumption rate-per-unit list $C[0], C[1], \ldots, C[N - 1]$. Both lists are already sorted in nondecreasing order. However, you do not know which car corresponds to which position or which fuel consumption rate. But you do know that each car has exactly one position and exactly one fuel consumption rate. That is, there exist two permutations $P$ and $Q$ of length $N$ such that the $i$-th car is located at position $X[P[i]]$ and has fuel consumption rate $C[Q[i]]$. ::::info[What is a permutation of length $N$?]{open} In this problem, a permutation $P$ of length $N$ is an array of length $N$ such that for all $0 \le i \le N - 1$, we have $0 \le P[i] \le N - 1$, and for all $0 \le i < j \le N - 1$, we have $P[i] \ne P[j]$. For example, $[2, 1, 0]$ is a permutation of length $3$, but $[1, 2, 3]$ and $[2, 0, 2]$ are not permutations of length $3$. :::: Given a particular assignment $(P, Q)$, define the total fuel cost to gather all cars at point $y$ as $\text{cost}(P, Q, y) = \sum_{i=0}^{N-1} |X[P[i]] - y| \times C[Q[i]]$. Given an **integer** point $p$, define the **worst-case fuel cost** at point $p$ as the maximum total fuel cost over all possible assignments $(P, Q)$. That is, define $\text{worst}(p) = \max \limits_{P, Q} \text{cost}(P, Q, p)$. Your task is to find an integer point $p$ such that the worst-case fuel cost $\text{worst}(p)$ is minimized. If there are multiple points $p$ that achieve the same minimum value of $\text{worst}(p)$, you may return any one of them. ### Implementation Details You need to implement the following function. ```cpp int car_gathering(int N, std::vector X, std::vector C) ``` - $N$: the number of cars. - $X$: an array of length $N$ describing the car positions, sorted in order. - $C$: an array of length $N$ describing the fuel consumption rates, sorted in order. - For each testdata, this function is called exactly once. - This function should return an integer $p$ such that, among all integer points, gathering all cars at point $p$ minimizes the worst-case fuel cost.

``` N X[0] X[1] ... X[N - 1] C[0] C[1] ... C[N - 1] ```

A single integer, representing the return value of `car_gathering`.

### Sample Consider the following function call: ```cpp car_gathering(3, [-1, 2, 3], [1, 1, 2]) ``` Suppose $p = 1$. It can be proven that the assignments $P = [0, 1, 2]$ and $Q = [2, 1, 0]$ produce the **worst-case fuel cost**. That is, $\text{worst}(p) = \text{cost}(P, Q, p) = (|-1 - 1| \times 2) + (|2 - 1| \times 1) + (|3 - 1| \times 1) = 7$. Note that there may be other assignments of $P$ and $Q$ that also produce the **worst-case fuel cost**, for example $P = [2, 1, 0]$ and $Q = [2, 1, 0]$. It can also be proven that the integer point $p = 1$ is the point that makes $\text{worst}(p)$ minimal. Therefore, this function call should return $1$. ### Constraints - $1 \le N \le 10\ 000\ 000$. - For all $0 \le i \le N - 1$, $-10^9 \le X[i] \le 10^9$. - For all $0 \le i \le N - 1$, $0 \le C[i] \le 100$. - For all $0 \le i < j \le N - 1$, $X[i] \le X[j]$. - For all $0 \le i < j \le N - 1$, $C[i] \le C[j]$. ### Subtasks 1. ($10$ points) $N \le 1000$, $|X[i]| \le 10^3$. 2. ($23$ points) $N \le 100\ 000$. 3. ($17$ points) $N \le 1\ 000\ 000$. 4. ($31$ points) For all $0 \le i \le N - 1$, $C[i] \le 1$. 5. ($19$ points) No additional constraints. Translated by ChatGPT 5