If someone would claim that the number of draws that happened between the three players are $$$d_{1, 2}$$$, $$$d_{1, 3}$$$ and $$$d_{2, 3}$$$, can you check in $$$O(1)$$$ whether this can be true?

The constraints are very small. The number of draws between any two players is at most $$$30$$$.

Hint 3: Try all the possibilities for $$$d_{1, 2}$$$, $$$d_{1, 3}$$$ and $$$d_{2, 3}$$$ and find the one with the biggest sum out of all possibilities that could've been the result of game that ended with scores $$$p_1$$$, $$$p_2$$$ and $$$p_3$$$.

After each round, sum of players' scores increases by 2, so if the sum $$$p_1 + p_2 + p_3$$$ is odd, answer is $$$-1$$$.

Now, as the hints suggest, you can try all possible combinations of $$$d_{1, 2}$$$, $$$d_{1, 3}$$$ and $$$d_{2, 3}$$$ with three for-loops and check for each combination whether it could result in scores $$$p_1$$$, $$$p_2$$$ and $$$p_3$$$. Specifically, it must hold that $$$p_1 - d_{1, 2} - d_{1, 3} \equiv 0 \mod 2$$$, $$$d_{1, 2} + d_{1, 3} \leq p_1$$$ and the same two conditions for $$$p_2$$$ and $$$p_3$$$ analogously. Now you can find the biggest value of $$$d_{1, 2}$$$ + $$$d_{1, 3}$$$ + $$$d_{2, 3}$$$ over all valid choices and print it as the answer.

The time complexity is $$$O(t \cdot \max(p) ^3)$$$.

Implementation in Python: 261998440

We will say that the array is $$$k$$$-lonely if $$$a_i|a_{i+1}| \ldots |a_{i+k−1}=a_j|a_{j+1}| \ldots |a_{j+k−1}$$$ is true for any two positive integers $$$1 \leq i,j \leq n−k+1$$$. Let $$$A$$$ be the maximum value an element in array $$$a$$$ can have.

how to check if the array is $$$k$$$-lonely in $$$O(n \log A)$$$?

if the array is $$$k$$$-lonely, the array is also $$$k+1$$$-lonely

binary search the answer :)

If the array is $$$k$$$-lonely, then since $$$a_i | \ldots | a_{i+k} = (a_i | \ldots | a_{i+k-1}) | (a_{i+1} | \ldots | a_{i+k}) = (a_j | \ldots | a_{j+k-1}) | (a_{j+1} | \ldots | a_{j+k}) = a_j | \ldots | a_{j+k}$$$, the array is also $$$k+1$$$-lonely.

You can check whether an array is $$$k$$$-lonely in $$$O(n \log A)$$$ by calculating the OR of every segment of length $$$k$$$. You can do this by iterating $$$i$$$ from $$$1$$$ to $$$n-k+1$$$ and mantaining an array $$$t$$$ of size $$$\log n$$$ where $$$t[j]$$$ will be equal to the number of elements from $$$a_i, ..., a_{i+k-1}$$$ that have the bit $$$2^j$$$ set. For $$$i = 1$$$ we can calculate this array in $$$O (k \log A)$$$ and then when moving $$$i$$$ to the right, we can update the array in $$$O (\log A)$$$ complexity and we can also calculate the OR of all elements in the segment, using the array $$$t$$$, in $$$O (\log A)$$$.

Once you have a checking function that runs in $$$O (n \log A)$$$, you can binary search the answer in $$$O(n \log A \log n)$$$ time, which is fast enough to pass.

Implementation in C++: 261999140

$$$n$$$ is even. What is the obvious upper bound on the number of the local maximums?

Right, it is $$${n \over 2} - 1$$$. We can actually achieve this value for any permutation.

Consider $$$p_1 = n$$$. Can you find $$$q$$$ such that all other odd positions will be local maximums?

We can easily prove that the sequence can have at most $$${n \over 2} - 1$$$ local maximums, because the corner elements can't be the local maximums and no two consecutive elements can be local maximums. Let's see how we can achieve this upper bound.

Let's consider the case when $$$n$$$ is at odd position in the original array first. We will construct a permutation $$$q$$$ such that the resulting array $$$a$$$ will have local maximums at all the odd positions except the first one. We can do this by placing the numbers $$${n \over 2} + 1, {n \over 2} + 2, \ldots n$$$ at the odd indexes in $$$q$$$, giving the bigger numbers to the indexes with smaller $$$p_i$$$, and placing the numbers $$$1, 2, \ldots, {n \over 2}$$$ at the even indexes in $$$p$$$, giving the smaller numbers to the indexes with bigger $$$p_i$$$. Then since $$$n$$$ belongs to an odd index, the $$$a_i$$$ for each odd $$$i$$$ will be at least $$$n + 1$$$ while the $$$a_i$$$ for each even $$$i$$$ will be at most $$$n$$$. So every element of $$$a$$$ at odd position, except for the corner, will be a local maximum. This means we will have $$${n \over 2} - 1$$$ local maximums, which is optimal, as we noitced above.

We can get the solution for the case when $$$n$$$ is at even position analogously. For example, by reversing the permutation $$$p$$$, calculating the right permutation $$$q$$$, reversing them again and printing this $$$q$$$ as the answer.

Time complexity: $$$O(n \log n)$$$ because of sorting. Actually, since you are sorting a permutation, you can do it in just $$$O(n)$$$ but it's not necessary.

Implementation in C++: 261999352

Let $$$m$$$ be value we want to find. What values can $$$m$$$ take?

Look at the maximum value in array $$$a$$$.

Can you find the maximum value in array?

Think about the segment containing the maximum value.

Can you finish the problem in $$$n$$$ queries?

Let's denote maximum value in array $$$a$$$ as $$$mx$$$. Since the element with maximum value will belong to some segment, then if $$$m$$$ exists, $$$m$$$ will be divisible by $$$mx$$$. Obviously, $$$m$$$ can't be greater than $$$n \cdot mx$$$, so now the candidates for value of $$$m$$$ are $$$mx, 2 \cdot mx, 3 \cdot mx, \dots, n \cdot mx$$$.

To find the value of $$$mx$$$ we can query $$$?$$$ $$$1$$$ $$$n \cdot i$$$ for each $$$1\leq i \leq n$$$ and $$$mx$$$ will be equal to such $$$i$$$, querying which will give $$$n$$$ as the answer.

We can check each of $$$n$$$ possible values in $$$k$$$ queries, but that wouldn't fit in query limit.

Actually, since the length of each segment in partition will be greater than or equal to $$$\frac{m}{mx}$$$, and there are exactly $$$k$$$ segments, we can get a simple inequality $$$k \cdot \frac{m}{mx} \leq n$$$ (since sum of lengths of segments is exactly $$$n$$$), which means $$$m$$$ can not be greater than $$$mx \cdot \lfloor{n/k}\rfloor$$$, so it is enough to check first $$$\lfloor{n/k}\rfloor$$$ candidates for $$$m$$$ in $$$k$$$ queries each. Total number of queries used would be $$$n + k \cdot \lfloor{n/k}\rfloor$$$ which doesn't exceed $$$2n$$$.

Implementation in C++: 261999488

Forget about graphs and data structures, there exists a simple $$$O(n)$$$ solution.

Find the number of pairs with $$$l = r$$$ for which you can sort the permutation.

Okay now that you have the special case handled, let's proceed to the general case. Find the minimum and maximum number that need to be swapped. Write down the inequalities that $$$l$$$ and $$$r$$$ have to satisfy so that we can swap these two elements with some other elements. This is the obvious necessary condition, right?

Right, so if $$$l \neq r$$$ and additionally, $$$l$$$ and $$$r$$$ satisfy the inequalities mentioned above, is it enough?

Yes, it is enough. But you can try to find the proof too :)

Let's consider the pairs $$$l, r$$$ that have $$$l = r$$$ first. Then you can swap each $$$x$$$ with at most one other element, $$$l - x$$$. So if $$$i \neq p_i$$$ for some $$$i$$$, then we need to be able to swap the element $$$i$$$ with the element $$$p_i$$$, so it must hold that $$$l = i + p_i$$$. This is obviously also a sufficient condition, so it's enough to just find all $$$i + p_i$$$ for $$$i \neq p_i$$$, if there exist more then one different value, there's no good pair with $$$l = r$$$, if there's exactly one different value, there's exactly one good pair with $$$l = r$$$ and otherwise there are $$$2 n$$$ such pairs.

Now let's count the pairs with $$$l \neq r$$$. If the array is sorted already, all pairs of $$$l, r$$$ are good. From now, consider only the case when the array isn't sorted yet.

Let $$$L$$$ be the smallest value such that $$$p_L \neq L$$$ and $$$R$$$ the largest such value respectively. We obviously need to be able to swap $$$L$$$ and $$$R$$$ with some other values.

Note that $$$L \neq n$$$ and $$$R \neq 1$$$, otherwise the array would be sorted already. Now we can get the inequalities $$$l \leq L + n$$$ and $$$R + 1 \leq r$$$, those are the necessary conditions for being able to swap the numbers $$$L, R$$$ with at least one other element.

We can actually prove that these are the sufficient conditions too. If $$$l, r$$$ satisfy these conditions, then for any number $$$X$$$ in the range $$$[L, R-1]$$$, we can find an $$$x$$$ in the range $$$[l, r]$$$ such that $$$1 \leq x - X \leq n$$$ and then we can swap the numbers $$$X$$$ and $$$X + 1$$$, while not affecting any other element, by swapping $$$X$$$ and $$$x - X$$$ first and then swapping $$$X + 1$$$ and $$$x - X$$$. Thanks to this, we can sort the whole range of values between $$$L$$$ and $$$R$$$ — while the array isn't sorted, we will always find the smallest index $$$i$$$ that doesn't have the right value and keep swapping the value $$$p_i$$$ with the value $$$p_i - 1$$$, so eventually we will get $$$p_i = i$$$ and we can continue sorting on the right.

So it's enough to just count the number of pairs $$$l, r$$$ such that $$$l \neq r$$$, $$$l \leq L + n$$$ and $$$R + 1 \leq r$$$, add it to the answer and print it.

All of this can be done in time and memory complexity $$$O(n)$$$.

Implementation in C++: 261999566 (I used set and therefore the time complexity is $$$O(n \log n)$$$ because it was more comfortable)

What are the possible pairs of $$$\gcd$$$'s of the two arrays we can have after some swaps?

For every pair $$$(X, Y)$$$ such that $$$X$$$ divides $$$a_1$$$ and $$$Y$$$ divides $$$b_1$$$, let's calculate the total number of indices $$$i$$$ such that we can have $$$X | a_i$$$ and $$$Y | b_i$$$ (either with or without the swap), and the minimum cost of swaps to achieve this. This is all we need to solve the problem, right?

Write for each $$$i$$$ the conditions that the pair $$$(X, Y)$$$ has to satisfy in order to add $$$i$$$ to the result/make swap on the position $$$i$$$. Use something like SOS-DP to add up all the values efficiently.

Let $$$k$$$ be the maximum value of $$$a_i$$$, $$$b_i$$$ on input ($$$10^8$$$). Let $$$D(k)$$$ be the maximum number of divisors a number in range $$$[1, \ldots, k]$$$ can have and $$$P(k)$$$ the maximum number of prime divisors such number can have.

Let's think about how to solve one query (with $$$M$$$ coins) for now. Assume that in the optimal solution, we never swap $$$a_1$$$ and $$$b_1$$$. In the end, we will just run the same solution on input where $$$a_1$$$ and $$$b_1$$$ is swapped and $$$M$$$ is decreased by $$$c_1$$$, and then we will take the maximum of the two values these two runs will find.

So now, in the optimal solution, the gcd of $$$a$$$ is always a divisor of $$$a_1$$$, and the $$$\gcd$$$ of $$$b$$$ is a divisor of $$$b_1$$$. Let's start by factorizing the two numbers in $$$O(\sqrt k)$$$.

Now we will precalculate something in order to be efficiently able to determine for every $$$X$$$, a divisor of $$$a$$$, and $$$Y$$$, a divisor of $$$b_1$$$, whether we can have $$$\gcd(a_1, \ldots, a_n) = X$$$ and $$$gcd(b_1, ..., b_n) = Y$$$ simultaneously (and also the minimum cost of making it so). Then we can obviously answer the query by finding the best pair with sum at most $$$M$$$.

Let's create new two dimensional arrays $$$P$$$ and $$$S$$$ of size $$$D(a_1) \times D(b_1)$$$. We will use $$$P$$$ to be able to tell the number of indexes $$$i$$$ such that we have either $$$X | a_i$$$ and $$$Y | b_i$$$ or $$$X | b_i$$$ and $$$Y | a_i$$$. If this count won't be $$$n$$$, then obviously we can't have $$$X$$$ and $$$Y$$$ as $$$\gcd$$$'s of $$$a$$$ and $$$b$$$. Also, we will use $$$S$$$ to tell us the sum of costs of all swaps we need to perform to have $$$X | \gcd(a_1, \ldots, a_n)$$$ and $$$Y | \gcd(b_1, ..., b_n)$$$.

Now how to make two such arrays efficiently? It is obvious that if the pair of $$$\gcd$$$ s $$$(X, Y)$$$ is consistent with some indexes in the original array, then for every pair $$$(x, y)$$$ such that $$$x|X$$$ and $$$y|Y$$$, this pair of $$$\gcd$$$s is also consistent with those indexes (and maybe even more, also maybe some swaps just became unnecessary, but the point is, it doesn't get worse). So if we want to add some value to a pair, we also want to get it added to all its divisors. That's why, in order to calculate the arrays efficiently, we will first add some values on some positions and then do something like $$$2D$$$ prefix sums — for every cell $$$(x, y)$$$ we will sum the values for all pairs $$$(X, Y)$$$ such that $$$x | X$$$ and $$$y | Y$$$ and update its current value with it. Assuming this is going to happen in the end, let's look at every $$$i$$$ and consider what pairs are "good" for this index — with or without the swap:

a) If $$$X$$$ divides $$$a_i$$$ and $$$Y$$$ divides $$$b_i$$$: For this type of pairs, we don't need to make any swaps on this index. Let's add $$$1$$$ to $$$P[\gcd(a_1, a_i)][\gcd(b_1, b_i)]$$$ to indicate that for all $$$(X, Y)$$$ such that $$$X|a_i$$$ and $$$Y|b_i$$$, we don't have to perform any swaps at the position $$$i$$$, the index is good as it is.

b) $$$X$$$ divides $$$b_i$$$ and $$$Y$$$ divides $$$a_i$$$: In this case we will add $$$1$$$ to $$$P[\gcd(a_1, b_i)][\gcd(b_1, a_i])]$$$ and $$$c_i$$$ to $$$S[\gcd(a_1, b_i)][\gcd(b_1, a_i)]$$$ to indicate that if we pick $$$X$$$, $$$Y$$$ such that $$$X|b_i$$$ and $$$Y|a_i$$$, we can make index $$$i$$$ good if we swap $$$a_i$$$ and $$$b_i$$$.

c) $$$X$$$ and $$$Y$$$ both divide both $$$a_i$$$ and $$$b_i$$$: To avoid counting both of the previous cases and therefore overcounting, we will add $$$-1$$$ to $$$P[\gcd(a_1, a_i, b_i)][\gcd(b_1, a_i, b_i)]$$$ and $$$-c_i$$$ to $$$S[\gcd(a_1, a_i, b_i)][\gcd(b_1, a_i, b_i)]$$$ (we have to undo paying for the swap since in this case we actually don't have to pay for it, but it falls under the case b) too).

This step can be done in $$$O(n \log k)$$$.

Now let's fix the arrays $$$P$$$ and $$$S$$$ so they store the actual values, not just the values we need to add.

We will go through all primes $$$p$$$ dividing $$$a_1$$$ and update $$$P[X][Y]$$$ with $$$P[p \cdot X][Y]$$$ and $$$S[X][Y]$$$ with $$$S[p \cdot X][Y]$$$, similarly for all primes dividing $$$b_1$$$. If we make those updates in the right order, we achieve that $$$P[x][y]$$$ is the sum of all original values $$$P[X][Y]$$$ for all the pairs $$$(X, Y)$$$ such that $$$x|X$$$ and $$$y|Y$$$ like we wanted (and we can do the same for $$$S$$$).

By careful precalculation of divisors and their order while factorizing, we can do this step in $$$O(D(k)^2 P(k))$$$. Some efficient implementations with extra log might pass also, but you will have to be more careful.

For multiple queries, after precalculating the possible sums of $$$\gcd$$$ s and their costs, you can sort them and use binary search to answer the queries.

Time complexity: $$$O(n \log k + \sqrt k + D(k)^2 P(k) + D(k)^2 \log D(k) + q \log D(k))$$$ Memory complexity: $$$O(n + D(k)^2 + P(k))$$$

Implementation in C++: 261999743

Fun fact: While making the original proposal, I invented a version of this problem with lower constraints and thought it could be nice Div2C. Few days later, while I was on a walk, I realized this solution exists, so we decided to try to propose it as the hardest problem.