結果

問題 No.2927 Reverse Polish Equation
コンテスト
ユーザー srjywrdnprkt
提出日時 2024-10-15 14:09:10
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 464 ms / 2,000 ms
コード長 1,618 bytes
コンパイル時間 8,356 ms
コンパイル使用メモリ 391,508 KB
最終ジャッジ日時 2025-02-24 19:47:09
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 43
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>

using namespace std;
using ll = long long;
using namespace boost::multiprecision; 
using ull = cpp_int;

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

    /*
       clamp関数は広義単調
       f(x)>=Yを満たす最小のxが答えになりうる。
    */

    ll N, Y;
    ull a, b;
    cin >> N >> Y;
    vector<string> s(N);
    for (int i=0; i<N; i++) cin >> s[i];

    auto f=[&](ull x)->ull{
        vector<ull> v;
        for (int i=0; i<N; i++){
            if (s[i] == "+"){
                a = v.back();
                v.pop_back();
                b = v.back();
                v.pop_back();
                v.push_back(a+b);
            }
            else if (s[i] == "min"){
                a = v.back();
                v.pop_back();
                b = v.back();
                v.pop_back();
                v.push_back(min(a,b));
            }
            else if (s[i] == "max"){
                a = v.back();
                v.pop_back();
                b = v.back();
                v.pop_back();
                v.push_back(max(a,b));
            }
            else if (s[i] == "X") v.push_back(x);
            else v.push_back((ull)stoll(s[i]));
        }
        assert(v.size() == 1);
        return v[0];
    };

    if (f(0) >= Y){
        cout << (f(0) == Y ? 0 : -1) << endl;
        return 0;
    }

    ull l=0, r=(ll)1e14, c;
    while(r-l>1){
        c = (l+r)/2;
        if (f(c) >= Y) r=c;
        else l=c;
    }

    cout << (f(r) == Y ? (ll)r : -1) << endl;

    return 0;
}
0