As the first problem in the contest, I read this problem first. The problem looked quite interesting, so I spent a bit of time on it before reading the other problems. I ended up immediately guessing the correct greedy, and submitted code that got 83 points, which very quickly became 100 points. I solved this before even attempting to think about the other problems.

The most restrictive element in $$$P$$$ is the one with the largest $$$P[i]$$$. It needs to be either the element with the largest $$$A[i]$$$ or largest $$$B[i]$$$. On the other hand, the least restrictive elements in $$$A$$$ and $$$B$$$ are the ones with the largest $$$A[i]$$$ and $$$B[i]$$$ respectively, since they can have any $$$P[i]$$$ and still fulfill the condition. Since both of these indices give the same use, we should focus on $$$P[i] - i$$$ to determine which one gets the largest $$$P[i]$$$. Clearly, to minimise $$$P[i] - i$$$, we should choose the larger of the 2. Now, notice that we have 1 less element to deal with and a similar problem left on our hands. We can repeat this process again with the new largest $$$A[i]$$$ and $$$B[i]$$$.

This motivates the full greedy solution: Assign the values of $$$P$$$ to the indices in decreasing order of $$$P[i]$$$. While there are still unchosen elements, let $$$x$$$ be the index with the largest $$$A[x]$$$ amongst all unchosen indices, and let $$$y$$$ be the index with the largest $$$B[y]$$$ amongst all unchosen indices. If $$$x = y$$$, assign the currently largest unused value of $$$P[i]$$$ to $$$x$$$. Otherwise, pick the larger of the 2 and assign the largest unused $$$P[i]$$$ to it.

Let's look at the sample testcase for an example. We have $$$A = [3, 0, 4, 1, 2]$$$, $$$B = [0, 3, 2, 4, 1]$$$. As our algorithm goes, we first find the element that we will assign $$$P[i] = 4$$$ to. $$$x = 2$$$ and $$$y = 3$$$, since $$$A[2] = 4$$$ and $$$B[3] = 4$$$. $$$y$$$ is bigger, so we set $$$P[y] = 4$$$ (i.e. $$$P[3] = 4$$$).

On the next run, we are assigning $$$P[i] = 3$$$. Now, $$$x = 2$$$ and $$$y = 1$$$, since $$$A[0] = 4$$$ and $$$B[1] = 3$$$. Now $$$x$$$ is bigger, so we set $$$P[2] = 3$$$.

By continuing the process, every element will get assigned a value.

This algorithm can be proven to work using a simple exchange argument. At any step in the algorithm, since there are only 2 valid choices for the index that takes on $$$P[i]$$$ ($$$x$$$ and $$$y$$$), if the algorithm chose one of them and it was unoptimal, the other one must be used in an optimal solution. However the rest of the algorithm continues as usual and in the end, swapping the values of $$$P[x]$$$ and $$$P[y]$$$ that we had would not make the result any worse. More formal writing is left as an exercise to the reader.

To implement this, we sort the indices by $$$A[i]$$$ and $$$B[i]$$$ in 2 separate arrays, and maintain 2 pointers pointing to the largest element with an undetermined $$$P[i]$$$. We also keep an array representing whether each index has its $$$P[i]$$$ determined yet.

Note that the sorting here needs to be done using counting sort, since permutations can be sorted in $$$O(N)$$$ and the problem setter successfully set tight enough limits ($$$N$$$ up to 5 million), to the point where std::sort fails the time limit. The overall time complexity should be $$$O(N)$$$.