Untitled
unknown
plain_text
2 years ago
7.1 kB
6
Indexable
#include <bits/stdc++.h> #define all(x) x.begin(), x.end() #define r_all(x) x.rbegin(), x.rend() #define sz(x)(ll) x.size() #define g_max(x, y) x = max(x, y) #define g_min(x, y) x = min(x, y) #define rsz(a, n) a.resize(n) #define ass(a, n) a.assign(n, 0) #define YES() cout << "YES\n" #define Yes cout << "Yes\n" #define NO() cout << "NO\n" #define No() cout << "No\n" #define endl "\n" #define print(a) for (auto &x: a) cout << x << " "; cout << endl #define print_pair(a) #define FOR(i, fr, to) for (long long i = fr; i <= to; i++) #define RFOR(i, fr, to) for (long long i = fr; i >= to; i--) #define pb push_back #define eb emplace_back #define is insert #define F first #define S second using namespace std; using ll = long long; using ld = long double; using vll = vector<ll>; using vvll = vector<vll>; using vc = vector<char>; using vvc = vector<vc>; using pll = pair<ll, ll>; using vpll = vector<pll>; using vvpll = vector<vpll>; using stkll = stack<ll>; using qll = queue<ll>; using dqll = deque<ll>; using sll = set<ll>; using msll = multiset<ll>; using mll = map<ll, ll>; using vsll = vector<sll>; using sc = set<char>; using pcll = pair<char, ll>; ll dr[] = {0, 1, 0, -1}, dc[] = {-1, 0, 1, 0}; const ll INF = 1e18; ll MOD = 998244353; ll mod_add(ll u, ll v, ll mod = MOD) { u %= mod, v %= mod; return (u + v) % mod; } ll mod_sub(ll u, ll v, ll mod = MOD) { u %= mod, v %= mod; return (u - v + mod) % mod; } ll mod_mul(ll u, ll v, ll mod = MOD) { u %= mod, v %= mod; return (u * v) % mod; } ll mod_pow(ll u, ll p, ll mod = MOD) { u %= mod; if (p == 0) { return 1; } ll v = mod_pow(u, p / 2, mod) % mod; v = (v * v) % mod; return (p % 2 == 0) ? v : (u * v) % mod; } ll mod_inv(ll u, ll mod = MOD) { u %= mod; ll g = __gcd(u, mod); if (g != 1) { return -1; } return mod_pow(u, mod - 2, mod); } ll mod_div(ll u, ll v, ll mod = MOD) { u %= mod, v %= mod; return mod_mul(u, mod_inv(v), mod); } template<class T> vector<T> operator+(vector<T> a, vector<T> b) { a.insert(a.end(), b.begin(), b.end()); return a; } pll operator+(pll a, pll b) { pll ans = {a.first + b.first, a.second + b.second}; return ans; } template<class A, class B> ostream &operator<<(ostream &os, const pair<A, B> &p) { os << p.first << " " << p.second; return os; } template<class A, class B> istream &operator>>(istream &is, pair<A, B> &p) { is >> p.first >> p.second; return is; } template<class T> ostream &operator<<(ostream &os, const vector<T> &vec) { for (auto &x: vec) { os << x << " "; } return os; } template<class T> istream &operator>>(istream &is, vector<T> &vec) { for (auto &x: vec) { is >> x; } return is; } template<class T> ostream &operator<<(ostream &os, const set<T> &vec) { for (auto &x: vec) { os << x << " "; } return os; } template<class A, class B> ostream &operator<<(ostream &os, const map<A, B> d) { for (auto &x: d) { os << "(" << x.first << " " << x.second << ") "; } return os; } template<class A> void read_arr(A a[], ll from, ll to) { for (ll i = from; i <= to; i++) { cin >> a[i]; } } template<class A> void print_arr(A a[], ll from, ll to) { for (ll i = from; i <= to; i++) { cout << a[i] << " "; } cout << "\n"; } template<class A> void print_arr(A a[], ll n) { print_arr(a, 0, n - 1); } template<class A> void set_arr(A a[], A val, ll from, ll to) { for (ll i = from; i <= to; i++) { a[i] = val; } } template<class A> void set_arr(A a[], A val, ll n) { set_arr(a, val, 0, n - 1); } const ll N = 2e5 + 10; ll n, k, q; ll a[N]; string s, s1, s2, s3; struct Dsu { ll par[N]; ll n; void init(ll _n) { n = _n; } void build() { FOR(i, 0, n) { par[i] = -1; } } ll get(ll x) { return par[x] < 0 ? x : par[x] = get(par[x]); } ll same_set(ll a, ll b) { return get(a) == get(b); } ll size(ll x) { return -par[get(x)]; } ll unite(ll x, ll y) { x = get(x), y = get(y); if (x == y) { return false; } if (par[x] > par[y]) { swap(x, y); } par[x] += par[y], par[y] = x; return 1; } }; struct E { ll u, v, w; bool operator<(const E &o) const { return w < o.w; } }; void init() { } struct B { double a, b, t; }; struct comp { bool operator()(const B &o1, const B &o2) const { return o1.t + o1.a / o1.b > o2.t + o2.a / o2.b; } }; vector<B> vec; double m; ll valid(double x) { priority_queue<B, vector<B>, comp> pq; for (auto &p: vec) { B tmp{p.a, p.b, p.t}; pq.push(tmp); } double cur = 0; while (cur < x) { B u = pq.top(); pq.pop(); B nxt = pq.top(); double nxt_t = min(x, nxt.a / nxt.b + nxt.t); u.a = (m - u.b) * (nxt_t - cur) + u.a; u.t = cur; cout << make_pair(u.a, u.b) << " " << u.t << "\n"; if (abs(u.a) <= 1e-7) { return false; } cur = nxt_t; pq.push(u); } return true; } double get_ans() { double left = 0, right = 0; double eps = 1e-5; for (auto &u: vec) { g_max(right, u.a / u.b); } if (n == 1) { return (m >= vec[0].b) ? -1 : vec[0].a / (vec[0].b - m); } // while (left + eps < right) { // double mid = (left + right) / 2; //// cout << make_pair(left, right) << '\n'; // if (valid(mid)) { // left = mid + eps; // } else { // right = mid; // } // } cout << valid(0.6) << "\n"; return left - eps; } void single(ll t_id = 0) { cin >> n >> m; vec.clear(); FOR(i, 1, n) { B u {}; cin >> u.b >> u.a; vec.push_back(u); } cout << get_ans() << "\n"; } void multiple() { ll t; cin >> t; for (ll i = 0; i < t; i++) { single(i); } } //#endif #if 0 void multiple() { while (cin >> n >> m) { if (n == 0 && m == 0) { break; } single(); } #endif int main(int argc, char *argv[]) { // ios_base::sync_with_stdio(false); // cin.tie(nullptr); init(); // freopen("feast.in", "r", stdin); // freopen("feast.out", "w", stdout); freopen("../input.txt", "r", stdin); multiple(); // single(); return 0; };
Editor is loading...