Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

Find k-th fraction

Revision en6, by coolboy19521, 2025-07-02 19:12:34

n<=1e5, q<=n^2, k<=n^2, qn<=1e5

a and b are integer arrays of length n. q queries are asked and you need to find k-th largest fraction among ai/bj (0<=i,j<n). You can do it offline.

(Note: binary searching on ai/bj as a float/double/long double does not work due to precision. I could not find any judge to submit the solution sorry.)

Edit: you need to output the nominator and denominator as the solution for each query.

Edit: ai,bi<=1e6 Edit: Apparently solutions binary searching float/double/long double work. Sorry for confusion.

Tags fractions, binary search

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en7 English coolboy19521 2025-07-02 19:12:48 2 Tiny change: ',bi<=1e6\nEdit: Ap' -> ',bi<=1e6\n\nEdit: Ap'
en6 English coolboy19521 2025-07-02 19:12:34 97
en5 English coolboy19521 2025-07-02 11:15:01 2 Tiny change: 'h query.\nEdit: ai' -> 'h query.\n\nEdit: ai'
en4 English coolboy19521 2025-07-02 11:14:43 18 Tiny change: 'ach query.' -> 'ach query.\nEdit: ai,bi<=1e6'
en3 English coolboy19521 2025-07-01 23:25:18 2 Tiny change: 'ching on a/b as a floa' -> 'ching on ai/bj as a floa'
en2 English coolboy19521 2025-07-01 23:21:09 90
en1 English coolboy19521 2025-07-01 23:18:25 356 Initial revision (published)