B. Thousand Sunny's Network Setup
D. Pirates Island: Painting the Grand Line
E. Straw Hat's Blue-Red Permutation
Now consider separately two red numbers $$$a_{i}$$$ and $$$a_{j}$$$ such that $$$a_{i}>a_{j}$$$ . If $$$x$$$ is produced by increasing $$$a_{i}$$$ and $$$y$$$ is produced by increasing $$$a_{j}$$$ , and in the same time $$$x<y$$$ then $$$y>x⩾a_{i}>a_{j}$$$ , and the following is also true: $$$x>a_{j}$$$ and $$$y>a_{i}$$$ . So we just showed that if an answer exists, it also exists if greater numbers are produced by greater values from the input. The same holds for the blue numbers.
Let us sort all elements ai by the key $$$(c_{i},a_{i})$$$ , where $$$c_{i}$$$ the color of $$$i-th$$$ element (and blue comes before red). It remains to check that for any $$$t$$$ from $$$1$$$ to $$$n$$$ we can get the number $$$t$$$ from the $$$t$$$ -th element of the obtained sorted array. To do this, we iterate through it and check that either $$$c_{t}='B'$$$ and $$$a_{t}⩾t$$$ so it can be reduced to $$$t$$$, or, symmetrically, $$$c_{t}='R'$$$ and $$$a_{t}⩽t$$$. <\spoiler>
Once we have this list of target positions, we simulate sorting it into the correct order using adjacent swaps (similar to bubble sort). At each step, we compare adjacent elements, and if they are in the wrong order, we swap them. We continue this process until the list is sorted, recording each swap. Finally, we output the number of swaps and the swap operations themselves. This approach guarantees the desired configuration while ensuring the solution is efficient enough given the problem constraints.
from collections import defaultdict
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
hash_map = defaultdict(list)
for i in range(n):
hash_map[a[i]].append(i)
for i in range(n):
temp = hash_map[b[i]].pop()
b[i] = temp
swaps = []
swap_count = 0
while True:
swapped = False
for i in range(n - 1):
if b[i] > b[i + 1]:
b[i], b[i + 1] = b[i + 1], b[i]
swaps.append((i + 1, i + 2))
swap_count += 1
swapped = True
if not swapped:
break
print(swap_count)
for swap in swaps:
print(swap[0], swap[1])
