Description

There are $N$ cars, numbered from $0$ to $N-1$, on a number line. You are given the lists of their positions $X[0], X[1], \ldots, X[N - 1]​$ and their fuel consumption rates per unit $C[0], C[1], \ldots, C[N - 1]​$, each sorted in increasing order. However, you do not know which car corresponds to which position or which fuel consumption rate. But you know that each car has exactly one position and exactly one fuel consumption rate.

Equivalently, 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]]$.

What is a permutation of length $N$? In this problem, a permutation $P$ of length $N$ is an array of length $N$ such that $0 \leq P[i] \leq N-1$ for all $0 \leq i \leq N-1$ and $P[i] \neq P[j]$ for all $0 \leq i < j \leq N-1$. 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)$, we define the total fuel cost to gather all cars at a point $y$ as $\text{cost}(P, Q, y) = \sum_{i=0}^{N-1} \lvert X[P[i]] -y \rvert \times C[Q[i]]$.

Given an integer point $p$, define the worst-case fuel cost at point $p$ to be 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 determine an integer point$p$ such that the worst-case fuel cost at point $p$, $\text{worst}(p)$ is minimized. If there are multiple points $p$ that achieve the same minimum value of $\text{worst}(p)$, you may report any one of them.

Implementation Details

You should implement the following procedure.

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 positions of the cars sorted in increasing order.
• $C$: an array of length $N$ describing the fuel consumption rates of the cars sorted in increasing order.
• This procedure is called exactly once for each test case.
• This procedure should return an integer $p$, for which the worst-case fuel cost of gathering all cars at $p$ is minimised among all integer points.

Constraints

• $1 \le N \le 10\;000\;000$.
• $-10^9 \le X[i] \le 10^9$, for all $0 \leq i \leq N - 1$.
• $\color{red}{0 \le C[i] \le 100}$, for all $0 \leq i \leq N - 1$.
• $X[i] \leq X[j]$, for all $0 \leq i < j \leq N - 1$.
• $C[i] \leq C[j]$, for all $0 \leq i < j \leq N - 1$.

Subtasks

1. (10 points) $N \le 1000, \lvert X[i] \rvert \le 10^3$.
2. (23 points) $N \le 100\;000$.
3. (17 points) $N \le 1\;000\;000$.
4. (31 points) $C[i] \le 1$, for all $0 \leq i \leq N - 1$.
5. (19 points) No additional constraints.

Example

Consider the following call:

car_gathering(3, [-1, 2, 3], [1, 1, 2])

Suppose $p = 1$. Then one can prove that the assignments $P = [0,1,2]$ and $Q = [2,1,0]$ yield the worst-case fuel cost.That is, $\text{worst}(p) = \text{cost}(P, Q, p) = (\lvert -1 - 1 \rvert \times 2) + (\lvert 2​​-1 \rvert \times 1​) + (\lvert 3-1 \rvert \times 1) = 7$. Note that there could be other assignments of $P$ and $Q$ that yield the worst-case fuel cost,such as $P = [2,1,0]$ and $Q = [2,1,0]$.

One can also prove that the integer point $p = 1$ is the point with the minimum possible $\text{worst}(p)$. Therefore, this call should return 1.

Sample Grader

Input format:

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

Output format:

An integer representing the return value of car_gathering.