Overview

Find the minimum number of adjacent cell swaps to move two people to their target positions.
The key point is to consider two cases based on whether “the left-right relationship of the two people is the same at the start and end, or reversed.”

Analysis

First, sort the initial positions and target positions in ascending order.

• Initial positions: \(u=\min(A,B),\ v=\max(A,B)\)
• Target positions: \(r=\min(C,D),\ s=\max(C,D)\)

Also, determine whether the left-right relationship of Takahashi and Aoki changes.

• In the initial state, if \(A<B\), then Takahashi is on the left
• In the target state, if \(C<D\), then Takahashi is on the left

Therefore, if

\[ (A<B) = (C<D) \]

then the left-right relationship remains the same.

---

There are broadly two types of operations:

1. Swap a person with an empty cell
   → That person moves one cell

2. Swap two adjacent people
   → The left-right relationship of the two people is reversed

What’s particularly important is that to change the left-right relationship of the two people, you must swap two adjacent people somewhere.

For example, in the case

\[ A=0,\ B=1,\ C=1,\ D=0 \]

simply adding distances gives \(1+1=2\), but in reality, the answer is \(1\) since you only need to swap the two adjacent people once.
Therefore, simply computing \(|A-C|+|B-D|\) will result in WA.

Also, since coordinates can be up to \(10^{18}\), simulating one step at a time is not feasible.

---

Case where the left-right relationship does not change

In this case, the person on the left should end up on the left, and the person on the right should end up on the right.

Therefore, the required number of moves is simply the total distance to move the occupied cells:

\[ |u-r|+|v-s| \]

Swapping between people is unnecessary since it would only change the left-right relationship.

---

Case where the left-right relationship changes

Somewhere, the two people must be swapped once while adjacent.

Assume that just before the swap, the two people are at cells \(x\) and \(x+1\).

In the initial state, the left person is at \(u\) and the right person is at \(v\).
The number of moves needed to reach the state just before the swap is:

\[ |u-x|+|v-(x+1)| \]

Then we swap the two people, which costs \(1\) additional move.

After the swap, the order of the left and right persons is reversed.
Since the final occupied cells are \(r,s\), the number of moves from after the swap to the target is:

\[ |x-r|+|x+1-s| \]

Therefore, the total cost when the swap position is \(x\) is:

\[ |u-x|+|v-(x+1)|+1+|x-r|+|x+1-s| \]

Simplifying this gives:

\[ 1+|x-u|+|x-(v-1)|+|x-r|+|x-(s-1)| \]

In other words, we need to minimize the sum of distances to the following four values:

\[ u,\ v-1,\ r,\ s-1 \]

Sort the four numbers in ascending order as:

\[ p_0 \leq p_1 \leq p_2 \leq p_3 \]

The sum of absolute values is minimized near the median, specifically in the range from \(p_1\) to \(p_2\).

The minimum value is:

\[ (p_3-p_0)+(p_2-p_1) \]

Finally, adding the \(1\) for swapping the two people:

\[ (p_3-p_0)+(p_2-p_1)+1 \]

is the answer.

Algorithm

1. Compute \(u=\min(A,B),\ v=\max(A,B)\)
2. Compute \(r=\min(C,D),\ s=\max(C,D)\)
3. Determine whether the left-right relationship is the same
   • It is the same if \((A<B)=(C<D)\)
4. If the same:
   • The answer is \(|u-r|+|v-s|\)
5. If different:
   • Create the array \([u,\ v-1,\ r,\ s-1]\)
   • Sort in ascending order
   • With \(p_0 \leq p_1 \leq p_2 \leq p_3\), the answer is

\[ (p_3-p_0)+(p_2-p_1)+1 \]

Complexity

• Time complexity: \(O(1)\)
• Space complexity: \(O(1)\)

Implementation Notes

Since coordinates and answers can be very large, use 64-bit integer types such as long long.

For determining the left-right relationship, since the constraints guarantee \(A \neq B,\ C \neq D\):

bool same_order = (A < B) == (C < D);

can be used for the check.

Source Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long A, B, C, D;
    cin >> A >> B >> C >> D;

    long long u = min(A, B), v = max(A, B);
    long long r = min(C, D), s = max(C, D);

    bool same_order = (A < B) == (C < D);

    long long ans;
    if (same_order) {
        ans = llabs(u - r) + llabs(v - s);
    } else {
        array<long long, 4> p = {u, v - 1, r, s - 1};
        sort(p.begin(), p.end());
        ans = (p[3] - p[0]) + (p[2] - p[1]) + 1;
    }

    cout << ans << '\n';
    return 0;
}

---

This editorial was generated by gpt-5.5-xhigh.