Problem Description

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.

int car_gathering(int N, std::vector<int> X, std::vector<int> 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.

Input Format

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

Output Format

A single integer, representing the return value of car_gathering.

Hint

Sample

Consider the following function call:

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