Untitled
unknown
plain_text
a year ago
1.6 kB
13
Indexable
#include <iostream> #include <vector> #include <algorithm> #include "assert.h" using namespace std; #define vi vector <int> #define ll long long #define pii pair<int, int> const double eps = 1e-13; int n, q; vi a, b; ll gcd(ll a, ll b) { if (!b) return a; return gcd(b, a % b); } ll cnt(double t) { int j = -1; ll res = 0; for (int i = 0; i < n; i++) { while (j + 1 < n && a[j + 1] <= b[i] * t) j++; res += j + 1; } return res; } pii restore(double t) { int j = -1; double val = 1e18; pii opt = {-1, -1}; for (int i = 0; i < n; i++) { while (j + 1 < n && a[j + 1] <= b[i] * t) j++; if (j < n && abs(1.0 * a[j] / b[i] - t) < val) { val = abs(1.0 * a[j] / b[i] - t); opt = {a[j], b[i]}; } if (j - 1 >= 0 && abs(1.0 * a[j - 1] / b[i] - t) < val) { val = abs(1.0 * a[j - 1] / b[i] - t); opt = {a[j - 1], b[i]}; } } return opt; } int main() { cin >> n >> q; a.resize(n); b.resize(n); for (int i = 0; i < n; i++) cin >> a[i]; for (int i = 0; i < n; i++) cin >> b[i]; sort(a.begin(), a.end()); sort(b.begin(), b.end()); while (q--) { ll k; cin >> k; double L = 0, R = 1e6; int it = 300; while (it--) { double M = (L + R) / 2; if (cnt(M) < k) L = M; else R = M; } auto ans = restore(R); int g = gcd(ans.first, ans.second); cout << ans.first / g << " " << ans.second / g << endl; } return 0; }
Editor is loading...
Leave a Comment