#1191023 (C++17) No.3754 Mischievous Resident (Hard)

• 問題: No.3754 Mischievous Resident (Hard)
• ユーザー: marc2825
• 提出日時: 2026-10-02 17:19:28
• 言語: C++17 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 46 ms / 2,000 ms
• コード長: 3,917 bytes
• コンパイル時間: 1,173 ms
• コンパイル使用メモリ: 222,704 KB
• 実行使用メモリ: 9,904 KB
• 最終ジャッジ日時: 2026-10-02 21:07:14
• 合計ジャッジ時間: 8,207 ms
• ジャッジサーバーID （参考情報）: judge1_1 / judge4_0

ファイルパターン	結果
sample	AC * 1
other	AC * 48

ソースコード

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

using int64 = long long;

// min { k >= 0 : total <= gap * 2^k }
// total > 0, gap > 0
int doublingCount(int64 total, int64 gap) {
    unsigned long long x =
        static_cast<unsigned long long>((total - 1) / gap);

    if (x == 0) {
        return 0;
    }

    return 64 - __builtin_clzll(x);
}

// 逆操作で、左側が先に初期位置へ到達する場合。
// left > 0, right > 0, gap > 0
int firstLeftCost(int64 left, int64 right, int64 gap) {
    const int64 total = left + gap + right;
    const int64 A = (left + gap - 1) / gap;
    const int64 B = (right + gap - 1) / gap;

    int best = INT_MAX;
    int t = 0;

    for (int64 p = 1; p * gap < total; p *= 2, ++t) {
        const int64 low = max(0LL, p - A);
        const int64 high = min({
            p - 1,
            B - 1,
            2 * p - 1 - A
        });

        if (low > high) {
            continue;
        }

        // b は大きいほど、その後の間隔が広くなる。
        const int64 width = left + (high + 1) * gap;
        const int cost = t + 1 + doublingCount(total, width);

        best = min(best, cost);
    }

    return best;
}

int convergingCost(int64 left, int64 right, int64 gap) {
    return min(
        firstLeftCost(left, right, gap),
        firstLeftCost(right, left, gap)
    );
}

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

    int Q;
    cin >> Q;

    while (Q--) {
        int64 N;
        int M;
        cin >> N >> M;

        vector<pair<int64, int64>> elevators(M);

        for (auto& elevator : elevators) {
            cin >> elevator.first;
        }

        for (auto& elevator : elevators) {
            cin >> elevator.second;
        }

        // 初期位置の昇順、同じなら目標位置の昇順。
        sort(elevators.begin(), elevators.end());

        bool possible = true;

        for (int i = 1; i < M; ++i) {
            const auto [prevS, prevG] = elevators[i - 1];
            const auto [s, g] = elevators[i];

            if (prevG > g) {
                possible = false;
                break;
            }

            if (prevG == g && (prevS != prevG || s != g)) {
                possible = false;
                break;
            }
        }

        if (!possible) {
            cout << -1 << '\n';
            continue;
        }

        int64 answer = 0;

        for (int i = 0; i < M; ++i) {
            const auto [s, g] = elevators[i];

            if (s == g) {
                continue;
            }

            if (s < g) {
                // 右向きの直後が左向きなら、ペアとして処理。
                if (i + 1 < M &&
                    elevators[i + 1].first > elevators[i + 1].second) {
                    const auto [nextS, nextG] = elevators[i + 1];

                    answer += convergingCost(
                        g - s,
                        nextS - nextG,
                        nextG - g
                    );

                    ++i;
                } else if (i + 1 == M) {
                    // 右側に他のエレベーターがない。
                    ++answer;
                } else {
                    const int64 nextG = elevators[i + 1].second;

                    answer += doublingCount(
                        nextG - s,
                        nextG - g
                    );
                }
            } else {
                // 左隣が右向きの場合は、すでにペア処理済み。
                if (i == 0) {
                    ++answer;
                } else {
                    const int64 prevG = elevators[i - 1].second;

                    answer += doublingCount(
                        s - prevG,
                        g - prevG
                    );
                }
            }
        }

        cout << answer << '\n';
    }

    return 0;
}