結果
問題 | No.2927 Reverse Polish Equation |
ユーザー |
![]() |
提出日時 | 2024-10-12 16:43:55 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 256 ms / 2,000 ms |
コード長 | 1,935 bytes |
コンパイル時間 | 7,329 ms |
コンパイル使用メモリ | 336,908 KB |
実行使用メモリ | 11,568 KB |
最終ジャッジ日時 | 2024-10-16 00:27:05 |
合計ジャッジ時間 | 11,294 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 43 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using namespace atcoder; #define all(x) (x).begin(), (x).end() #define rep(i, n) for (int i = 0; i < (int)(n); i++) #define rrep(i, n) for(int i = (int)(n - 1); i >= 0; i--) template <typename T> bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;} template <typename T> bool chmin(T &a,const T &b){if(a>b){a=b;return true;}return false;} using ll = long long; #define int ll using vi = vector<int>; using vvi = vector<vector<int>>; using vb = vector<bool>; using vvb = vector<vector<bool>>; using vs = vector<string>; using pii = pair<int, int>; // using mint = modint!!!number!!!; signed main(){ int q, y; cin >> q >> y; vs s(q); rep(i, q) cin >> s.at(i); int ok = 1e13, ng = -1; while(ok - ng > 1){ int mid = (ok + ng) / 2; vi a; int n = 0; rep(i, q){ if(s.at(i) == "X"){ a.push_back(mid); n++; } else if(s.at(i) == "+"){ a.at(n - 2) += a.at(n - 1); a.erase(a.begin() + n - 1); n--; } else if(s.at(i) == "min"){ chmin(a.at(n - 2), a.at(n - 1)); a.erase(a.begin() + n - 1); n--; } else if(s.at(i) == "max"){ chmax(a.at(n - 2), a.at(n - 1)); a.erase(a.begin() + n - 1); n--; } else{ a.push_back(stoll(s.at(i))); n++; } } (a.at(0) >= y ? ok : ng) = mid; } int mid = ok, n = 0; vi a; rep(i, q){ if(s.at(i) == "X"){ a.push_back(mid); n++; } else if(s.at(i) == "+"){ a.at(n - 2) += a.at(n - 1); a.erase(a.begin() + n - 1); n--; } else if(s.at(i) == "min"){ chmin(a.at(n - 2), a.at(n - 1)); a.erase(a.begin() + n - 1); n--; } else if(s.at(i) == "max"){ chmax(a.at(n - 2), a.at(n - 1)); a.erase(a.begin() + n - 1); n--; } else{ a.push_back(stoll(s.at(i))); n++; } } cout << (a.at(0) == y ? ok : -1) << endl; }