結果

問題 No.3754 Mischievous Resident (Hard)
コンテスト
ユーザー marc2825
提出日時 2026-09-12 15:41:36
言語 C++17
(gcc 15.3.0 + boost 1.92.0 + ACL)
コンパイル:
g++-15 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
WA  
実行時間 -
コード長 3,046 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,252 ms
コンパイル使用メモリ 226,588 KB
実行使用メモリ 14,448 KB
最終ジャッジ日時 2026-10-02 21:06:36
合計ジャッジ時間 9,106 ms
ジャッジサーバーID
（参考情報） 		judge4_0 / judge2_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 32 WA * 16
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

// File: main.cpp
#include <bits/stdc++.h>
using namespace std;

using int64 = long long;

int64 need_moves(int64 base, int64 amount) {
    if (amount <= 0) return 0;

    int64 cnt = 0;
    __int128 sum = 0;
    __int128 add = base;

    while (sum < amount) {
        sum += add;
        add *= 2;
        ++cnt;
    }

    return cnt;
}

int64 gap_cost(int64 d, int64 l, int64 r) {
    int64 total = need_moves(d, l + r);
    int64 left = need_moves(d + r, l);
    int64 right = need_moves(d + l, r);

    return max(total, left + right);
}

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

    int Q;
    cin >> Q;

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

        vector<int64> S(M), G(M);
        for (int i = 0; i < M; ++i) cin >> S[i];
        for (int i = 0; i < M; ++i) cin >> G[i];

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

        for (int i = 0; i < M; ++i) {
            elevators.emplace_back(S[i], G[i]);
        }

        sort(elevators.begin(), elevators.end());

        bool ok = true;

        vector<int64> A;  // reverse start positions: G
        vector<int64> B;  // reverse goal positions: S

        A.reserve(M);
        B.reserve(M);

        bool has_prev_group = false;
        int64 prev_max_g = -1;

        int idx = 0;

        while (idx < M) {
            int64 s = elevators[idx].first;
            vector<int64> kept_g;

            while (idx < M && elevators[idx].first == s) {
                int64 g = elevators[idx].second;
                int cnt = 0;

                while (idx < M && elevators[idx].first == s && elevators[idx].second == g) {
                    ++cnt;
                    ++idx;
                }

                if (cnt >= 2 && g != s) {
                    ok = false;
                }

                kept_g.push_back(g);
            }

            if (has_prev_group && prev_max_g >= kept_g.front()) {
                ok = false;
            }

            for (int64 g : kept_g) {
                A.push_back(g);
                B.push_back(s);
            }

            prev_max_g = kept_g.back();
            has_prev_group = true;
        }

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

        int m = (int)A.size();

        if (m == 1) {
            cout << (A[0] == B[0] ? 0 : 1) << '\n';
            continue;
        }

        int64 ans = 0;

        for (int i = 0; i + 1 < m; ++i) {
            int64 d = A[i + 1] - A[i];

            if (d <= 0) {
                ok = false;
                break;
            }

            int64 l = max<int64>(0, A[i] - B[i]);
            int64 r = max<int64>(0, B[i + 1] - A[i + 1]);

            ans += gap_cost(d, l, r);
        }

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

        if (B[0] > A[0]) {
            ++ans;
        }

        if (B[m - 1] < A[m - 1]) {
            ++ans;
        }

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

    return 0;
}
0