結果

問題 No.180 美しいWhitespace (2)
コンテスト
ユーザー bolero
提出日時 2025-12-11 19:28:33
言語 C++23
(gcc 13.3.0 + boost 1.89.0)
結果
WA  
実行時間 -
コード長 2,508 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 6,453 ms
コンパイル使用メモリ 335,344 KB
実行使用メモリ 7,852 KB
最終ジャッジ日時 2025-12-11 19:28:41
合計ジャッジ時間 7,259 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 12 WA * 19
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
#define rep(i, n) for (long long i = 0; i < (long long)(n); i++)
#define FOR(i, s, e) for (long long i = (long long)(s); i <= (long long)(e); i++)
#define printYesNo(is_ok) puts(is_ok ? "Yes" : "No");
#define SORT(v) sort(v.begin(), v.end());
#define RSORT(v) sort(v.rbegin(), v.rend());
#define REVERSE(v) reverse(v.begin(), v.end());

long long op(long long a, long long b)
{
    return a + b;
}

long long e()
{
    return 0;
}

template <bool minimize, typename T>
pair<long long, T> fibonacci_search(long long x_low, long long x_high, function<T(long long)> f)
{
    assert(x_low < x_high);
    long long offset = x_low - 1;

    T INF = minimize ? numeric_limits<T>::max() : numeric_limits<T>::lowest();
    auto comp = [](T a, T b) -> bool
    { return minimize ? a >= b : a <= b; };

    vector<long long> fib = {1, 1};
    while (fib.back() <= x_high - offset)
    {
        fib.push_back(fib[fib.size() - 1] + fib[fib.size() - 2]);
    }

    unordered_map<long long, T> fx_cache;
    auto eval = [&](long long idx) -> T
    {
        long long x = idx + offset;
        if (x_low <= x && x <= x_high)
        {
            if (!fx_cache.contains(x))
            {
                fx_cache[x] = f(x);
            }
            return fx_cache[x];
        }

        return INF;
    };

    long long l_idx = 0, r_idx = fib.back();
    while (2 <= fib.size())
    {
        long long step_len = fib[fib.size() - 2];

        long long mid_l_idx = r_idx - step_len, mid_r_idx = l_idx + step_len;

        T fl = eval(mid_l_idx), fr = eval(mid_r_idx);

        if (comp(fl, fr))
        {
            l_idx = mid_l_idx;
        }
        else
        {
            r_idx = mid_r_idx;
        }

        fib.pop_back();
    }

    return {l_idx + offset, eval(l_idx)};
}

int main()
{
    int N;
    cin >> N;

    vector<pair<long long, long long>> ab(N);
    rep(i, N)
    {
        cin >> ab[i].first >> ab[i].second;
    }

    auto f = [&](long long x) -> long long
    {
        long long mx = 0, mn = INT32_MAX;
        for (auto [a, b] : ab)
        {
            mx = max(mx, a + b * x);
            mn = min(mn, a + b * x);
        }

        return mx - mn;
    };

    if (count(ab.begin(), ab.end(), pair<long long, long long>{0, 0}) == N)
    {
        cout << 1 << endl;
    }
    else
    {
        auto [x, fx] = fibonacci_search<true, long long>(1, 1000000000, f);
        cout << x << endl;
    }

    return 0;
};
0