結果

問題 No.3754 Mischievous Resident (Hard)
コンテスト
ユーザー marc2825
提出日時 2026-08-07 11:05:53
言語 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  
実行時間 -
コード長 2,690 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 534 ms
コンパイル使用メモリ 103,136 KB
実行使用メモリ 12,928 KB
最終ジャッジ日時 2026-10-02 20:51:42
合計ジャッジ時間 9,002 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 1
other AC * 16 WA * 1 TLE * 1 -- * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const long long INF = 4e18; // 無限遠の壁

struct Elevator {
    long long s, g;
    int id;
};

void solve() {
    int n, m;
    cin >> n >> m;
    vector<long long> 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<Elevator> E(m);
    for (int i = 0; i < m; ++i) {
        E[i] = {S[i], G[i], i};
    }

    // Sの昇順、Sが同じ場合はGの昇順にソート
    sort(E.begin(), E.end(), [](const Elevator& a, const Elevator& b) {
        if (a.s != b.s) return a.s < b.s;
        return a.g < b.g;
    });

    // 到達不可能性のチェック
    bool possible = true;
    for (int i = 0; i < m - 1; ++i) {
        if (E[i].s < E[i+1].s && E[i].g >= E[i+1].g) possible = false;
        if (E[i].s == E[i+1].s && E[i].g > E[i+1].g) possible = false;
        if (E[i].s != E[i+1].s && E[i].g == E[i+1].g) possible = false;
    }

    if (!possible) {
        cout << -1 << "\n";
        return;
    }

    // シミュレーション用関数
    auto simulate = [&](bool right_first) -> long long {
        long long cost = 0;
        vector<long long> X(m);
        for (int i = 0; i < m; ++i) X[i] = E[i].s;

        auto move_right = [&]() {
            for (int i = m - 1; i >= 0; --i) {
                if (X[i] < E[i].g) {
                    long long w = (i + 1 < m) ? X[i + 1] : INF;
                    while (X[i] < E[i].g) {
                        long long F = (X[i] + w) / 2; // 切り捨て
                        if (F >= E[i].g) { X[i] = E[i].g; cost++; break; }
                        X[i] = F; cost++;
                    }
                }
            }
        };

        auto move_left = [&]() {
            for (int i = 0; i < m; ++i) {
                if (X[i] > E[i].g) {
                    long long w = (i - 1 >= 0) ? X[i - 1] : -INF;
                    while (X[i] > E[i].g) {
                        long long F = (X[i] + w + 1) / 2; // 切り上げ
                        if (F <= E[i].g) { X[i] = E[i].g; cost++; break; }
                        X[i] = F; cost++;
                    }
                }
            }
        };

        if (right_first) {
            move_right();
            move_left();
        } else {
            move_left();
            move_right();
        }
        return cost;
    };

    long long cost1 = simulate(true);
    long long cost2 = simulate(false);

    cout << min(cost1, cost2) << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int q;
    if (cin >> q) {
        while (q--) solve();
    }
    return 0;
}
0