P16703 [SEATST 2026] Two Exams

There are $N$ students in the class. Each student is assigned an ID from $0$ to $N - 1$ based on the current class ranking. That is, student $i$ (for all $0 \le i \le N - 1$) currently has class rank $i$. Here, rank $0$ is the best, and rank $N - 1$ is the worst. The class has recently finished Chinese and Math exams. Student $i$ (for all $0 \le i \le N - 1$) has rank $A[i]$ in the Chinese exam and rank $B[i]$ in the Math exam. Both $A$ and $B$ are permutations of length $N$. :::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$. ::: The teacher wants to re-rank all students. The new ranking can be represented by a permutation $P$. For each student $i$, their new class rank must satisfy **at least** one of the following conditions: - For all $j$ such that $P[j] < P[i]$, student $j$ has a better Chinese score than student $i$ (i.e., $A[j] < A[i]$), or - For all $j$ such that $P[j] < P[i]$, student $j$ has a better Math score than student $i$ (i.e., $B[j] < B[i]$). :::warning[Warning]{open} This condition only applies to those $j$ with $P[j] < P[i]$. There are no restrictions for those $j$ with $P[j] \ge P[i]$. For each student $i$, when checking whether the condition is satisfied, you **must first choose one subject**, and then compare student $i$ with all the corresponding students $j$ using that subject. For the same $i$, all different $j$ must be better than student $i$ in the same subject. You cannot switch subjects halfway through when evaluating the condition for student $i$. ::: The **dissatisfaction** of the new class ranking is defined as the maximum amount of rank drop among all students. In other words, dissatisfaction is the maximum value of $P[i] - i$ (for all $0 \le i \le N - 1$). :::warning[Warning]{open} Dissatisfaction is the maximum of $P[i] - i$. The value of $i - P[i]$ does not affect the calculation of dissatisfaction. ::: Among all possible new rankings, find the **minimum possible dissatisfaction**. ### Implementation Details You need to implement the following function: ```cpp int minimum_dissatisfaction(int N, std::vector A, std::vector B) ``` - $N$: the number of students. - $A$: an array of length $N$, representing the ranks in the Chinese exam. - $B$: an array of length $N$, representing the ranks in the Math exam. - This function should return the minimum dissatisfaction of the new class ranking. - This function is called exactly once for each testdata.

``` N A[0] A[1] ... A[N - 1] B[0] B[1] ... B[N - 1] ```

A single integer, which is the return value of `minimum_dissatisfaction`.

### Sample Consider the following function call: ```cpp minimum_dissatisfaction(5, [3, 0, 4, 1, 2], [0, 3, 2, 4, 1]) ``` In this example, one way to assign the new ranking is $P = [0, 2, 3, 4, 1]$. Consider student $1$, with $P[1] = 2$. All students $j$ such that $P[j] < P[1]$ have a better Math rank than student $1$, so this student satisfies the class ranking condition. Next, consider student $2$, with $P[2] = 3$. All students $j$ such that $P[j] < P[2]$ have a better Chinese rank than student $2$, so this student also satisfies the class ranking condition. It can be verified that all other students also satisfy the class ranking condition. The dissatisfaction of this new ranking is $1$. There is no other new ranking with lower dissatisfaction, so the function should return $1$. ### Constraints - $1 \le N \le 5\ 000\ 000$. - For all $0 \le i \le N - 1$, $0 \le A[i], B[i] \le N - 1$. - For all $0 \le i < j \le N - 1$, $A[i] \ne A[j]$. - For all $0 \le i < j \le N - 1$, $B[i] \ne B[j]$. ### Subtasks 1. ($3$ points) $N \le 8$. 2. ($4$ points) $N \le 20$. 3. ($13$ points) $N \le 500$. 4. ($12$ points) $N \le 3000$, and for all $0 \le i \le N - 1$, $A[i] + B[i] = N - 1$. 5. ($19$ points) $N \le 3000$. 6. ($15$ points) $N \le 100\ 000$, and for all $0 \le i \le N - 1$, $A[i] + B[i] = N - 1$. 7. ($17$ points) $N \le 100\ 000$. 8. ($17$ points) no additional constraints. **Note**: For subtask $8$, the judging program alone is guaranteed to take $1500$ milliseconds out of the $3000$ milliseconds time limit. Translated by ChatGPT 5