PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Cakewalk
PREREQUISITES:
Sorting
PROBLEM:
You’re given an array X. An array Y was created from it as follows:
- Choose a pivot index i_0, and let P = X_{i_0}.
- Sort the elements of X by their distance from P, breaking ties by choosing the smaller element. This is the array Y.
You’re given the arrays X and Y. Find any valid choice of pivot index i_0, or say that none exist.
EXPLANATION:
Suppose we fix i_0.
Clearly, the closest element to X_{i_0}, is X_{i_0} itself.
So, if a valid pivot element exists, it has to be equal to the first element of Y.
The array elements are distinct, so this also immediately tells us the pivot index in X (which is whichever index contains the element equal to Y_1).
Let i_0 be the pivot index found this way.
Now that i_0 is known, we can simply construct the expected array Y by performing the given process, and check if it equals the array we’re given.
TIME COMPLEXITY:
\mathcal{O}(N\log N) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
x = list(map(int, input().split()))
y = list(map(int, input().split()))
p = y[0]
order = list(range(n))
order.sort(key = lambda i: (abs(x[i] - p), x[i]))
good = True
for i in range(n): good &= y[i] == x[order[i]]
print(order[0]+1 if good else -1)