結果
問題 | No.3064 Speedrun (Easy) |
ユーザー |
👑 ![]() |
提出日時 | 2025-03-21 21:22:54 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 29,661 bytes |
コンパイル時間 | 2,522 ms |
コンパイル使用メモリ | 219,844 KB |
実行使用メモリ | 7,324 KB |
最終ジャッジ日時 | 2025-03-21 21:22:57 |
合計ジャッジ時間 | 3,344 ms |
ジャッジサーバーID (参考情報) |
judge6 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 11 |
ソースコード
#ifdef __INCLUDED /********* M O D **********/ // #include <atcoder/modint> // https://atcoder.github.io/ac-library/production/document_ja/ // using namespace atcoder; // using mint = modint998244353; // modint1000000007; // istream& operator >>(istream& stream, mint& e) {ll n; stream >> n; e = n; return stream; } // ostream& operator <<(ostream& stream, const mint& e) { stream << e.val(); return stream; } // using vm = vector<mint>; // using vvm = vector<vm>; /***************************************/ constexpr bool DEBUG = true; // MARK: MAIN int main() { cin.tie(nullptr); cout << fixed << setprecision(10); vd A(4), P(4); ll T; cin >> A >> P >> T; double val = 0; rep(i, 4) { val += A[i] * P[i]; } PrintYesNo(val <= T); } #else #define __INCLUDED #ifdef __LOCAL #include <mytemplate.hpp> // プリコンパイル済みヘッダ ~/local/include/mytemplate.hpp.gch #else #include <algorithm> #include <array> #include <bitset> #include <cassert> #include <chrono> #include <climits> #include <cmath> #include <deque> #include <functional> #include <iomanip> #include <iostream> #include <iterator> #include <list> #include <map> #include <memory> #include <numeric> #include <optional> #include <queue> #include <random> #include <set> #include <stack> #include <string> #include <unordered_map> #include <unordered_set> #include <utility> #include <vector> #endif using namespace std; // #pragma GCC target "no-avx" // gcc12.2のバグ回避用。boost使用時はコメントアウトの事 // #include <boost/multiprecision/cpp_int.hpp> // using bint = boost::multiprecision::cpp_int; using ll = long long; using vl = vector<ll>; using vvl = vector<vl>; using vb = vector<bool>; using vvb = vector<vb>; using vd = vector<double>; using vvd = vector<vd>; using vc = vector<char>; using vvc = vector<vc>; using pll = pair<ll, ll>; template <class T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>; constexpr ll INF = LONG_LONG_MAX / 2 - 10000LL; // 4,611,686,018,427,377,903 ~= 4.6e+18, 19桁 const double PI = acos(-1); // MARK: MACRO #define REP1(i, n) REP3(i, 0, n, 1) #define REP2(i, s, n) REP3(i, s, n, 1) #define REP3(i, s, n, d) for (ll i = (ll)(s); i < (ll)(n); i += (d)) #define REP_OVERLOAD(e1, e2, e3, e4, NAME, ...) NAME #define rep(...) REP_OVERLOAD(__VA_ARGS__, REP3, REP2, REP1)(__VA_ARGS__) #define DEP1(i, n) DEP3(i, n, -1, 1) #define DEP2(i, n, s) DEP3(i, n, s, 1) #define DEP3(i, n, s, d) for (ll i = (ll)(n); (ll)(s) < i; i -= (d)) #define DEP_OVERLOAD(e1, e2, e3, e4, NAME, ...) NAME #define dep(...) DEP_OVERLOAD(__VA_ARGS__, DEP3, DEP2, DEP1)(__VA_ARGS__) #define fore(e, a) for (auto&& e : (a)) #define len(a) (ll)(a).size() #define all(a) (a).begin(), (a).end() #define rall(a) (a).rbegin(), (a).rend() #define pb push_back #define eb emplace_back #define fi first #define se second #define th third #define fo fourth // MARK: INT128 using int128 = __int128_t; // 128bit整数を入力. LONG_LONG_MAX超過/LONG_LONG_MIN未満もOK. istream& operator>>(istream& stream, int128& val) { string s; stream >> s; assert(s.size() > 0); val = 0; bool is_minus = false; for (int i = 0; i < (int)s.size(); i++) { if (i == 0 && s[i] == '-') { assert(s.size() > 1); is_minus = true; } else { assert('0' <= s[i] && s[i] <= '9'); val *= 10; val += s[i] - '0'; } } if (is_minus) val *= -1; return stream; } // 128bit整数を出力. ostream& operator<<(ostream& stream, const int128& val_) { auto val(val_); if (val == 0) return stream << 0; if (val < 0) { stream << '-'; val *= -1; } string s; while (val > 0) { s += (val % 10) + '0'; val /= 10; } reverse(s.begin(), s.end()); return stream << s; } // MARK: PAIR /* 単項演算子(+ -) */ template <class T, class U> pair<T, U> operator+(pair<T, U> a) { return a; } template <class T, class U> pair<T, U> operator-(pair<T, U> a) { return a * (-1); } /* 複合代入演算子 (pair) */ template <class T, class U> pair<T, U>& operator+=(pair<T, U>& a, const pair<T, U> b) { a.first += b.first; a.second += b.second; return a; } template <class T, class U> pair<T, U>& operator-=(pair<T, U>& a, const pair<T, U> b) { a.first -= b.first; a.second -= b.second; return a; } template <class T, class U> pair<T, U>& operator*=(pair<T, U>& a, const pair<T, U> b) { a.first *= b.first; a.second *= b.second; return a; } template <class T, class U> pair<T, U>& operator/=(pair<T, U>& a, const pair<T, U> b) { a.first /= b.first; a.second /= b.second; return a; } template <class T, class U> pair<T, U>& operator%=(pair<T, U>& a, const pair<T, U> b) { a.first %= b.first; a.second %= b.second; return a; } template <class T, class U, class V> pair<T, U>& operator+=(pair<T, U>& a, const V b) { a.first += b; a.second += b; return a; } template <class T, class U, class V> pair<T, U>& operator-=(pair<T, U>& a, const V b) { a.first -= b; a.second -= b; return a; } template <class T, class U, class V> pair<T, U>& operator*=(pair<T, U>& a, const V b) { a.first *= b; a.second *= b; return a; } template <class T, class U, class V> pair<T, U>& operator/=(pair<T, U>& a, const V b) { a.first /= b; a.second /= b; return a; } template <class T, class U, class V> pair<T, U>& operator%=(pair<T, U>& a, const V b) { a.first %= b; a.second %= b; return a; } /* 算術演算子 (pair) */ template <class T, class U, class V> pair<T, U> operator+(pair<T, U> a, const V& b) { return a += b; } template <class T, class U, class V> pair<T, U> operator-(pair<T, U> a, const V& b) { return a -= b; } template <class T, class U, class V> pair<T, U> operator*(pair<T, U> a, const V& b) { return a *= b; } template <class T, class U, class V> pair<T, U> operator/(pair<T, U> a, const V& b) { return a /= b; } template <class T, class U, class V> pair<T, U> operator%(pair<T, U> a, const V& b) { return a %= b; } // 入出力 template <class T, class U> istream& operator>>(istream& stream, pair<T, U>& a) { stream >> a.first >> a.second; return stream; } template <class T, class U> ostream& operator<<(ostream& stream, const pair<T, U>& a) { stream << a.first << " " << a.second; return stream; } // MARK: VECTOR /* 単項演算子(+ -) */ template <class T> vector<T> operator+(vector<T> a) { return a; } template <class T> vector<T> operator-(vector<T> a) { return a * (-1); } /* 複合代入演算子 (vector) */ template <class T> vector<T>& operator+=(vector<T>& a, const vector<T> b) { assert(a.size() == b.size()); for (int i = 0; i < (int)a.size(); i++) a[i] += b[i]; return a; } template <class T> vector<T>& operator-=(vector<T>& a, const vector<T> b) { assert(a.size() == b.size()); for (int i = 0; i < (int)a.size(); i++) a[i] -= b[i]; return a; } template <class T> vector<T>& operator*=(vector<T>& a, const vector<T> b) { assert(a.size() == b.size()); for (int i = 0; i < (int)a.size(); i++) a[i] *= b[i]; return a; } template <class T> vector<T>& operator/=(vector<T>& a, const vector<T> b) { assert(a.size() == b.size()); for (int i = 0; i < (int)a.size(); i++) a[i] /= b[i]; return a; } template <class T> vector<T>& operator%=(vector<T>& a, const vector<T> b) { assert(a.size() == b.size()); for (int i = 0; i < (int)a.size(); i++) a[i] %= b[i]; return a; } template <class T, class U> vector<T>& operator+=(vector<T>& a, const U b) { for (auto&& e : a) e += b; return a; } template <class T, class U> vector<T>& operator-=(vector<T>& a, const U b) { for (auto&& e : a) e -= b; return a; } template <class T, class U> vector<T>& operator*=(vector<T>& a, const U b) { for (auto&& e : a) e *= b; return a; } template <class T, class U> vector<T>& operator/=(vector<T>& a, const U b) { for (auto&& e : a) e /= b; return a; } template <class T, class U> vector<T>& operator%=(vector<T>& a, const U b) { for (auto&& e : a) e %= b; return a; } /* 算術演算子 (vector) */ template <class T, class U> vector<T> operator+(vector<T> a, const U& b) { return a += b; } template <class T, class U> vector<T> operator-(vector<T> a, const U& b) { return a -= b; } template <class T, class U> vector<T> operator*(vector<T> a, const U& b) { return a *= b; } template <class T, class U> vector<T> operator/(vector<T> a, const U& b) { return a /= b; } template <class T, class U> vector<T> operator%(vector<T> a, const U& b) { return a %= b; } /* 入出力 (vector) */ // ベクトルを入力 template <class T> istream& operator>>(istream& stream, vector<T>& a) { for (auto&& e : a) stream >> e; return stream; } // ベクトルを空白区切りで出力 template <class T> ostream& operator<<(ostream& stream, const vector<T>& v) { if (v.size()) { stream << v[0]; for (int i = 1; i < (int)v.size(); i++) cout << " " << v[i]; } return stream; } // 2次元ベクトルを空白/改行区切りで出力 template <class T> ostream& operator<<(ostream& stream, const vector<vector<T>>& vv) { if (vv.size()) { stream << vv[0]; for (int i = 1; i < (int)vv.size(); i++) cout << '\n' << vv[i]; } return stream; } /* 計算 (vector) */ // 合計。v.size() == 0 のとき T() を返す template <class T> T Sum(const vector<T>& v) { return reduce(v.begin(), v.end()); } template <class T> T Max(const vector<T>& v) { assert(v.size()); return *max_element(v.begin(), v.end()); } template <class T> T Min(const vector<T>& v) { assert(v.size()); return *min_element(v.begin(), v.end()); } // 最大要素を指す最初の位置を返す(0-origin), O(N). template <class T> ll Argmax(const vector<T>& v) { assert(v.size()); return max_element(v.begin(), v.end()) - v.begin(); } // 最小要素を指す最初の位置を返す(0-origin), O(N). template <class T> ll Argmin(const vector<T>& v) { assert(v.size()); return min_element(v.begin(), v.end()) - v.begin(); } // 要素`a`がベクトル`v`に1つ以上含まれるかどうか template <class T, class U> bool Contains(const vector<T>& v, const U& a) { return find(v.begin(), v.end(), a) != v.end(); } // ソートされたユニーク値のベクトルにinplaceで書き換える, O(NlogN). template <class T> void Unique(vector<T>& v) { sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); } // 要素`a`をベクトル`v`から削除。要素の有無を`bool`で返す, O(N). template <class T, class U> bool Erase(vector<T>& v, const U& a) { auto iter = find(v.begin(), v.end(), a); if (iter == v.end()) return false; v.erase(iter); return true; } /* 生成 (vector) */ template <class T, class U> vector<T> make_vector(int n, U v) { return vector<T>(n, v); } template <class T, class... Args> auto make_vector(int n, Args... args) { auto val = make_vector<T>(args...); return make_vector<decltype(val)>(n, move(val)); } // MARK: SET // 一要素を入力 template <class T> istream& operator>>(istream& stream, set<T>& st) { T e; stream >> e; st.insert(e); return stream; } // 空白区切りで出力 template <class T> ostream& operator<<(ostream& stream, const set<T>& st) { if (st.size()) { auto it = st.begin(); stream << *it++; for (; it != st.end(); it++) cout << " " << *it; } return stream; } template <class T> T Max(const set<T>& st) { assert(st.size()); return *prev(st.end()); } template <class T> T Min(const set<T>& st) { assert(st.size()); return *st.begin(); } // MARK: MULTISET // 一要素を入力 template <class T> istream& operator>>(istream& stream, multiset<T>& st) { T e; stream >> e; st.insert(e); return stream; } // 空白区切りで出力 template <class T> ostream& operator<<(ostream& stream, const multiset<T>& st) { if (st.size()) { auto it = st.begin(); stream << *it++; for (; it != st.end(); it++) cout << " " << *it; } return stream; } template <class T> T Max(const multiset<T>& st) { assert(st.size()); return *prev(st.end()); } template <class T> T Min(const multiset<T>& st) { assert(st.size()); return *st.begin(); } // 要素xを1つ削除. 消せたらtrueを返す. template <class T> bool EraseOne(multiset<T>& st, const T& x) { auto it = st.find(x); if (it != st.end()) { st.erase(it); return true; } else return false; } // MARK: CHAR // 大文字かどうか bool IsUpper(const char& c) { return isupper(c) > 0; } // 小文字かどうか bool IsLower(const char& c) { return islower(c) > 0; } // 大文字へ変換 char ToUpper(const char& c) { string s{c}, t; t.resize(s.size()); std::transform(s.begin(), s.end(), t.begin(), ::toupper); return t[0]; } // 小文字へ変換 char ToLower(const char& c) { string s{c}, t; t.resize(s.size()); std::transform(s.begin(), s.end(), t.begin(), ::tolower); return t[0]; } // MARK: STRING // 大文字へ変換 string ToUpper(const string& s) { string t; t.resize(s.size()); std::transform(s.begin(), s.end(), t.begin(), ::toupper); return t; } // 小文字へ変換 string ToLower(const string& s) { string t; t.resize(s.size()); std::transform(s.begin(), s.end(), t.begin(), ::tolower); return t; } // 回文判定, O(N). 空文字の返り値はTrue. bool IsPalindrome(const string& S) { ll N = S.size(); for (ll i = 0; 2 * i < N; i++) if (S[i] != S[N - i - 1]) return false; return true; } // MARK: TRIO template <class T1, class T2, class T3> struct trio { T1 first; T2 second; T3 third; trio() { first = T1(); second = T2(); third = T3(); } trio(const T1& x) : first(x), second(x), third(x) {} trio(const T1& x, const T2& y, const T3& z) : first(x), second(y), third(z) {} trio(const trio& t) { first = t.first; second = t.second; third = t.third; } trio<T1, T2, T3>& operator=(const trio& t) { if (this != &t) { first = t.first; second = t.second; third = t.third; } return *this; } // 比較演算子 (trio) bool operator<(const trio& t) const { return tie(first, second, third) < tie(t.first, t.second, t.third); } bool operator==(const trio& t) const { return tie(first, second, third) == tie(t.first, t.second, t.third); } bool operator!=(const trio& t) const { return !(*this == t); } bool operator>(const trio& t) const { return t < *this; } bool operator<=(const trio& t) const { return !(*this > t); } bool operator>=(const trio& t) const { return !(*this < t); } // 単項演算子(+ -) (trio) trio<T1, T2, T3> operator+() const { return *this; } trio<T1, T2, T3> operator-() const { return (*this) * (-1); } // 複合代入演算子 trio& operator+=(const trio& t) { first += t.first; second += t.second; third += t.third; return *this; } trio& operator-=(const trio& t) { first -= t.first; second -= t.second; third -= t.third; return *this; } trio& operator*=(const trio& t) { first *= t.first; second *= t.second; third *= t.third; return *this; } trio& operator/=(const trio& t) { first /= t.first; second /= t.second; third /= t.third; return *this; } trio& operator%=(const trio& t) { first %= t.first; second %= t.second; third %= t.third; return *this; } // 算術演算子 friend trio operator+(const trio& lhs, const trio& rhs) { return trio(lhs) += rhs; } friend trio operator-(const trio& lhs, const trio& rhs) { return trio(lhs) -= rhs; } friend trio operator*(const trio& lhs, const trio& rhs) { return trio(lhs) *= rhs; } friend trio operator/(const trio& lhs, const trio& rhs) { return trio(lhs) /= rhs; } friend trio operator%(const trio& lhs, const trio& rhs) { return trio(lhs) %= rhs; } // 入出力 (trio) friend istream& operator>>(istream& stream, trio<T1, T2, T3>& t) { return stream >> t.first >> t.second >> t.third; } friend ostream& operator<<(ostream& stream, const trio<T1, T2, T3>& t) { return stream << t.first << " " << t.second << " " << t.third; } }; using tll = trio<ll, ll, ll>; // MARK: QUARTET template <class T1, class T2, class T3, class T4> struct quartet { T1 first; T2 second; T3 third; T4 fourth; // コンストラクタ・代入演算子 quartet() { first = T1(); second = T2(); third = T3(); fourth = T4(); } quartet(const T1& x) : first(x), second(x), third(x), fourth(x) {} quartet(const T1& x, const T2& y, const T3& z, const T4& w) : first(x), second(y), third(z), fourth(w) {} quartet(const quartet& t) { first = t.first; second = t.second; third = t.third; fourth = t.fourth; } quartet<T1, T2, T3, T4>& operator=(const quartet& t) { if (this != &t) { first = t.first; second = t.second; third = t.third; fourth = t.fourth; } return *this; } // 比較演算子 (quartet) bool operator<(const quartet& t) const { return tie(first, second, third, fourth) < tie(t.first, t.second, t.third, t.fourth); } bool operator==(const quartet& t) const { return tie(first, second, third, fourth) == tie(t.first, t.second, t.third, t.fourth); } bool operator!=(const quartet& t) const { return !(*this == t); } bool operator>(const quartet& t) const { return t < *this; } bool operator<=(const quartet& t) const { return !(*this > t); } bool operator>=(const quartet& t) const { return !(*this < t); } // 単項演算子(+ -) (quartet) quartet<T1, T2, T3, T4> operator+() const { return *this; } quartet<T1, T2, T3, T4> operator-() const { return (*this) * (-1); } // 複合代入演算子 quartet& operator+=(const quartet& t) { first += t.first; second += t.second; third += t.third; fourth += t.fourth; return *this; } quartet& operator-=(const quartet& t) { first -= t.first; second -= t.second; third -= t.third; fourth -= t.fourth; return *this; } quartet& operator*=(const quartet& t) { first *= t.first; second *= t.second; third *= t.third; fourth *= t.fourth; return *this; } quartet& operator/=(const quartet& t) { first /= t.first; second /= t.second; third /= t.third; fourth /= t.fourth; return *this; } quartet& operator%=(const quartet& t) { first %= t.first; second %= t.second; third %= t.third; fourth %= t.fourth; return *this; } // 算術演算子 friend quartet operator+(const quartet& lhs, const quartet& rhs) { return quartet(lhs) += rhs; } friend quartet operator-(const quartet& lhs, const quartet& rhs) { return quartet(lhs) -= rhs; } friend quartet operator*(const quartet& lhs, const quartet& rhs) { return quartet(lhs) *= rhs; } friend quartet operator/(const quartet& lhs, const quartet& rhs) { return quartet(lhs) /= rhs; } friend quartet operator%(const quartet& lhs, const quartet& rhs) { return quartet(lhs) %= rhs; } // 入出力 (quartet) friend istream& operator>>(istream& stream, quartet<T1, T2, T3, T4>& t) { return stream >> t.first >> t.second >> t.third >> t.fourth; } friend ostream& operator<<(ostream& stream, const quartet<T1, T2, T3, T4>& t) { return stream << t.first << " " << t.second << " " << t.third << " " << t.fourth; } }; using qll = quartet<ll, ll, ll, ll>; // MARK: RANDOM struct Random { mt19937_64 rnd; // 引数なし: seedはランダム Random() { random_device seed_gen; rnd.seed(seed_gen()); } // 引数: seed Random(ll seed) { rnd.seed(seed); } // [a, b]からランダムに整数を返す ll randint(ll a, ll b) { assert(a <= b); uniform_int_distribution<ll> dist(a, b); return dist(rnd); } // [a, b)からランダムに整数を返す ll randrange(ll a, ll b) { return randint(a, b - 1); } // [a, b]からランダムに浮動小数点数を返す double randreal(double a, double b) { assert(a <= b); uniform_real_distribution<double> dist(a, b); return dist(rnd); } // [a, b]からランダムに文字を返す char randchar(char a, char b) { assert(a <= b); uniform_int_distribution<ll> dist(a, b); return dist(rnd); } // vectorからランダムに1要素を返す template <class T> T sample(const vector<T>& vec) { ll i = randrange(0, vec.size()); return vec[i]; } // `vec`をinplaceで並び替える template <class T> void shuffle(vector<T>& vec) { std::shuffle(vec.begin(), vec.end(), rnd); } }; // MARK: TIMER struct Timer { ll time_limit_ms; chrono::high_resolution_clock::time_point start_time; Timer() {} // 引数: タイムリミット(ミリ秒) Timer(ll time_limit_ms) { assert(time_limit_ms > 0); this->time_limit_ms = time_limit_ms; this->start_time = chrono::high_resolution_clock::now(); } ll get_elapsed_ms() const { auto now = chrono::high_resolution_clock::now(); return ll(chrono::duration_cast<chrono::milliseconds>(now - this->start_time).count()); } // タイムリミットに到達したかどうか bool is_time_up() const { ll elapsed_ms = get_elapsed_ms(); return elapsed_ms >= this->time_limit_ms; } // 経過時間の割合を[0.0, 1.0]で返す double get_elapsed_ratio() const { ll elapsed_ms = get_elapsed_ms(); double ratio = 1.0 * elapsed_ms / this->time_limit_ms; return min(1.0, ratio); } }; // MARK: PRINT template <class T> void print(const T& e) { cout << e << '\n'; } template <class H, class... T> void print(const H& h, const T&... t) { cout << h << ' '; print(t...); } template <class... T> void End(const T&... t) { print(t...); exit(0); } template <class T> void print_err(const T& e) { cerr << e << '\n'; } template <class H, class... T> void print_err(const H& h, const T&... t) { cerr << h << ' '; print_err(t...); } // MARK: DEBUG #ifdef __LOCAL #define debug(...) \ if (DEBUG) do { \ cerr << '[' << #__VA_ARGS__ << "] "; \ debug_(__VA_ARGS__); \ } while (0) #else #define debug(...) #endif void dbg_(const long long& e) { if (e == INF) cerr << "INF"; else if (e == -INF) cerr << "-INF"; else cerr << e; } template <class T> void dbg_(const T& e) { cerr << e; } template <class T, class U> void dbg_(const pair<T, U>& p) { cerr << '('; dbg_(p.first); cerr << ' '; dbg_(p.second); cerr << ')'; } template <class T1, class T2, class T3> void dbg_(const trio<T1, T2, T3>& t) { cerr << '('; dbg_(t.first); cerr << ' '; dbg_(t.second); cerr << ' '; dbg_(t.third); cerr << ')'; } template <class T1, class T2, class T3, class T4> void dbg_(const quartet<T1, T2, T3, T4>& t) { cerr << '('; dbg_(t.first); cerr << ' '; dbg_(t.second); cerr << ' '; dbg_(t.third); cerr << ' '; dbg_(t.fourth); cerr << ')'; } template <class T> void debug_(const T& e) { dbg_(e); cerr << '\n'; } template <class T> void debug_(const vector<T>& v) { if (v.size()) { auto it = v.begin(); dbg_(*it++); for (; it != v.end(); ++it) { cerr << ' '; dbg_(*it); } } cerr << '\n'; } template <class T> void debug_(const vector<vector<T>>& vv) { cerr << '\n'; ll cnt = 0; for (auto&& v : vv) { cerr << cnt++ << ": "; debug_(v); } } template <class T, class U> void debug_(const map<T, U>& mp) { if (mp.size()) { auto it = mp.begin(); dbg_(*it++); for (; it != mp.end(); ++it) { cerr << ' '; dbg_(*it); } } cerr << '\n'; } template <class T, class U> void debug_(const vector<map<T, U>>& vm) { cerr << '\n'; ll cnt = 0; for (auto&& mp : vm) { cerr << cnt++ << ": "; debug_(mp); } } template <class T> void debug_(const set<T>& st) { if (st.size()) { auto it = st.begin(); dbg_(*it++); for (; it != st.end(); ++it) { cerr << ' '; dbg_(*it); } } cerr << '\n'; } template <class T> void debug_(const multiset<T>& st) { if (st.size()) { auto it = st.begin(); dbg_(*it++); for (; it != st.end(); ++it) { cerr << ' '; dbg_(*it); } } cerr << '\n'; } template <class T> void debug_(const vector<set<T>>& vs) { cerr << '\n'; ll cnt = 0; for (auto&& st : vs) { cerr << cnt++ << ": "; debug_(st); } } template <class T> void debug_(const vector<multiset<T>>& vs) { cerr << '\n'; ll cnt = 0; for (auto&& st : vs) { cerr << cnt++ << ": "; debug_(st); } } template <class H, class... T> void debug_(const H& h, const T&... t) { dbg_(h); cerr << ", "; debug_(t...); } // MARK: OTHERS // a > b なら a に b を代入. template <class T, class U> bool chmin(T& a, U b) { if (a > b) { a = b; return true; } return false; } // a < b なら a に b を代入. template <class T, class U> bool chmax(T& a, U b) { if (a < b) { a = b; return true; } return false; } // a % mを返す. aは負もOK. template <class T, class U> T Mod(const T& a, const U& m) { assert(m > 0); return (a % m + m) % m; } // 天井関数. xは負もOK template <class T, class U> T Ceil(const T& x, const U& y) { assert(y > 0); return x < 0 ? x / y : (x + y - 1) / y; } // 床関数. xは負もOK template <class T, class U> T Floor(const T& x, const U& y) { assert(y > 0); return -(Ceil(-x, y)); } // 符号関数. 返り値: -1, 0, +1のいずれか template <class T> ll Sign(const T& x) { return (x > T(0)) - (x < T(0)); } // x * x <= nを満たす最大の整数`x`を返す ll Isqrt(ll n) { assert(n >= 0); ll x = round(sqrt(n)); while (x * x > n) --x; return x; } // nCr. n=60, r=30までOK. ll Comb(ll n, ll r) { if (r < 0 || n < r) return 0; r = min(r, n - r); ll ret = 1; for (ll i = 0; i < r; i++) { ret *= n - i; ret /= i + 1; } return ret; } // x^n. mintもOK. template <class T> T Pow(T x, ll n) { assert(n >= 0); T ret = 1; while (1) { if (n % 2) ret *= x; n /= 2; if (!n) return ret; x = x * x; } } // (x^n) % mod. template <class T> T Pow(T x, ll n, T mod) { assert(n >= 0 && mod > 0); T ret = 1; while (1) { if (n % 2) ret = (ret * x) % mod; n /= 2; if (!n) return ret; x = (x * x) % mod; } } // 等差級数. mintもOK. template <class T> T Aseries(T a, T d, ll n) { assert(n >= 0); return a * n + n * (n - 1) / 2 * d; } // 等比級数. mintもOK. template <class T> T Gseries(T a, T r, ll n) { assert(n >= 0); if (r == 1) return a * n; else return a * (1 - Pow(r, n)) / (1 - r); } // `b`の`i`番目(0 origin)のビットが1かどうか bool Bit(ll b, int i) { assert(0 <= i && i < 64); return (b >> i) & 1; } // `b`の立っているビット数 ll Popcount(ll b) { return __builtin_popcountll(b); } // [0, n)番目のビットが立った64bit整数を返す. ll Mask(ll n) { assert(0 <= n && n < 63); return (1LL << n) - 1LL; } // [m, n)番目のビットが立った64bit整数を返す. ll Mask(ll n, ll m) { assert(n >= m); return Mask(n) ^ Mask(m); } // [l1, r1)と[l2, r2)の積区間を返す. 例: [3, 6) x [5, 7) = [5, 6) pll GetOverlap(ll l1, ll r1, ll l2, ll r2) { return {max(l1, l2), min(r1, r2)}; } // [l1, r1)と[l2, r2)で重なりがあるかを返す. 引数が片方でも空区間ならfalse; bool IsOverlap(ll l1, ll r1, ll l2, ll r2) { return max(l1, l2) < min(r1, r2); } // b=trueなら"Yes\n", falseなら"No\n"を出力 void PrintYesNo(bool b) { b ? print("Yes") : print("No"); } #include __FILE__ #endif