fork download 
  1. #include <bits/stdc++.h>
  2. #define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; ++i)
  3. #define fi first
  4. #define se second
  5. #define el "\n"
  6. #define pb push_back
  7. #define sz(a) (int)(a).size()
  8. #define FILL(a,x) memset(a,x,sizeof(a))
  9.  
  10. using namespace std;
  11. typedef long long ll;
  12.  
  13. ll floor_div_pos(ll x, ll y) {
  14. if (x >= 0) return x / y;
  15. return - ((-x + y - 1) / y);
  16. }
  17.  
  18. ll count_le(const vector<ll> &a, const vector<ll> &b, ll x) {
  19. int n = sz(a), m = sz(b);
  20. ll res = 0;
  21. FOR(i,0,n-1) {
  22. ll ai = a[i];
  23. if (ai == 0) {
  24. if (x >= 0) res += (ll)m;
  25. } else if (ai > 0) {
  26. ll bound = floor_div_pos(x, ai);
  27. int idx = upper_bound(b.begin(), b.end(), bound) - b.begin();
  28. res += (ll)idx;
  29. } else {
  30. ll bound = -floor_div_pos(x, -ai); // ceil(x/ai) with ai < 0
  31. int idx = lower_bound(b.begin(), b.end(), bound) - b.begin();
  32. res += (ll)(m - idx);
  33. }
  34. }
  35. return res;
  36. }
  37.  
  38. int main() {
  39. ios::sync_with_stdio(false);
  40. cin.tie(nullptr);
  41. cout.tie(nullptr);
  42.  
  43. ll k;
  44. if (!(cin >> k)) return 0;
  45.  
  46. int n, m;
  47. cin >> n;
  48. vector<ll> a(n);
  49. FOR(i,0,n-1) cin >> a[i];
  50. cin >> m;
  51. vector<ll> b(m);
  52. FOR(i,0,m-1) cin >> b[i];
  53.  
  54. if (n > m) {
  55.     swap(n, m);
  56.     a.swap(b);
  57. }
  58.  
  59. sort(b.begin(), b.end());
  60.  
  61. ll minA = a[0], maxA = a[0];
  62. FOR(i,1,n-1) {
  63.     if (a[i] < minA) minA = a[i];
  64.     if (a[i] > maxA) maxA = a[i];
  65. }
  66. ll minB = b[0], maxB = b[0];
  67. FOR(i,1,m-1) {
  68.     if (b[i] < minB) minB = b[i];
  69.     if (b[i] > maxB) maxB = b[i];
  70. }
  71.  
  72. ll mn = min(min(minA * minB, minA * maxB), min(maxA * minB, maxA * maxB));
  73. ll mx = max(max(minA * minB, minA * maxB), max(maxA * minB, maxA * maxB));
  74.  
  75. ll lo = mn, hi = mx;
  76. while (lo < hi) {
  77.     ll mid = lo + (hi - lo) / 2;
  78.     if (count_le(a, b, mid) >= k) hi = mid;
  79.     else lo = mid + 1;
  80. }
  81.  
  82. cout << lo;
  83. return 0;
  84.  
  85. }
  86.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/4f87WH
language:
C++14 (clang 8.0)
created:
6 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!