#include #include #include // Use __int128 for intermediate products if available and compiler supports it (like GCC/Clang) // Check common macros to detect compiler and version that support __int128 #if defined(__GNUC__) || defined(__clang__) #if defined(__x86_64__) || defined(_M_X64) // Check if target architecture is 64-bit, where __int128 is typically available #define USE_INT128 #endif #endif #ifdef USE_INT128 // If __int128 is available, use it for potentially larger intermediate products typedef __int128 int128; #endif // Define long long type for convenience typedef long long ll; using namespace std; // Structure to hold product value (A[w]*B[x] or C[y]*D[z]) and original indices struct PItem { ll val; // The product value int idx1, idx2; // Store original 0-based indices from the source arrays (e.g., w, x for P=A[w]*B[x]) }; // Comparison function for sorting PItems based on their product value bool comparePItem(const PItem& a, const PItem& b) { return a.val < b.val; } // Input arrays vector A, B, C, D; // Vectors to store all products P = A[w]*B[x] and Q = C[y]*D[z] vector P_full, Q_full; // Vectors to store positive, negative, and zero products separately for efficient counting in count_le function vector P_pos, P_neg, P_zero; vector Q_pos, Q_neg, Q_zero; // Store sizes K, L, M, N as long long to avoid potential overflow in calculations like M*N ll K_ll, L_ll, M_ll, N_ll; // Store sizes as int as well for convenience in loops, if needed int K, L, M, N; // Safe multiplication check function: returns true if p * q > x // Uses __int128 if available for safety against overflow. // Otherwise, relies on standard long long multiplication. Problem constraints ensure intermediate products fit in long long. bool check_product_greater(ll p, ll q, ll x) { #ifdef USE_INT128 // Use 128-bit integer type for the product calculation to prevent overflow int128 prod = (int128)p * q; return prod > x; #else // If __int128 is not available, directly compute the product using long long. // Based on constraints |A_w| etc. <= 3e4, max product |P*Q| <= (3e4*3e4)*(3e4*3e4) = (9e8)^2 = 8.1e17. // This fits within standard signed 64-bit integer range (~ -9e18 to 9e18). return (p * q) > x; #endif } // Counts the number of pairs (p, q) from P_full and Q_full such that p * q <= X // Uses two-pointer technique over sorted positive/negative parts for efficiency. ll count_le(ll X) { ll count = 0; // Contribution from pairs involving zero elements: // If P=0 or Q=0, the product is 0. These pairs count if X >= 0. if (X >= 0) { // Count pairs where P=0. Each such P pairs with any Q (MN total Q values). count += (ll)P_zero.size() * M_ll * N_ll; // Count pairs where Q=0 and P!=0. Each such Q pairs with non-zero P values (KL - |P_zero| total). count += (ll)(K_ll * L_ll - P_zero.size()) * Q_zero.size(); // The above correctly counts pairs with at least one zero element without double counting. // The total count for pairs with at least one zero is |P0|*MN + (KL-|P0|)*|Q0| = |P0|*MN + KL*|Q0| - |P0|*|Q0|. } // Case 1: P > 0, Q > 0. Need P * Q <= X. // This case is only possible if X >= 0. if (X >= 0 && !P_pos.empty() && !Q_pos.empty()) { int j = Q_pos.size() - 1; // Pointer starting at the end of sorted Q_pos // Iterate through P_pos ascending for (int i = 0; i < P_pos.size(); ++i) { // For the current P_pos[i], find the largest Q_pos[j] such that P*Q <= X while (j >= 0 && check_product_greater(P_pos[i].val, Q_pos[j].val, X)) { j--; // If P*Q > X, Q_pos[j] is too large, try smaller Q. } // All Q_pos elements from index 0 to j satisfy the condition P*Q <= X. count += (j + 1); } } // Case 2: P > 0, Q < 0. Need P * Q <= X. Product is negative. if (!P_pos.empty() && !Q_neg.empty()) { // Use two pointers: i on P_pos (ascending), j on Q_neg (descending index, from end) int j = Q_neg.size() - 1; for (int i = 0; i < P_pos.size(); ++i) { // Find largest Q_neg[j] s.t. P*Q <= X. Since P > 0, Q_neg[j] < 0, this means finding Q_neg[j] closest to 0. while (j >= 0 && check_product_greater(P_pos[i].val, Q_neg[j].val, X)) { j--; // If P*Q > X, this Q_neg[j] is too large (not negative enough). Need more negative Q. Try Q_neg[j-1]. } // All Q_neg elements from 0 to j satisfy P*Q <= X. Add j+1 to count. count += (j + 1); } } // Case 3: P < 0, Q > 0. Need P * Q <= X. Product is negative. if (!P_neg.empty() && !Q_pos.empty()) { // Symmetric to Case 2 logic, using two pointers. // Iterate i on P_neg (ascending), j on Q_pos (descending index, from end). int j = Q_pos.size() - 1; for(int i = 0; i < P_neg.size(); ++i) { // Find largest Q_pos[j] s.t. P*Q <= X. Since P < 0, Q_pos[j] > 0, P*Q is negative. while (j >= 0 && check_product_greater(P_neg[i].val, Q_pos[j].val, X)) { j--; // If P*Q > X, this Q_pos[j] is too large. Need smaller Q. Try Q_pos[j-1]. } // All Q_pos elements from 0 to j satisfy P*Q <= X. Add j+1 to count. count += (j + 1); } } // Case 4: P < 0, Q < 0. Need P * Q <= X. Product is positive. Only possible if X >= 0. if (X >= 0 && !P_neg.empty() && !Q_neg.empty()) { // Use two pointers: i on P_neg (descending index, least negative first), k on Q_neg (ascending index, most negative first). int k = 0; // Iterate P_neg from largest value (closest to 0) down to smallest (most negative). for (int i = P_neg.size() - 1; i >= 0; --i) { // For fixed P_neg[i], find the smallest Q_neg[k] such that P*Q <= X. // Since P < 0, Q < 0, P*Q is positive. while (k < Q_neg.size() && check_product_greater(P_neg[i].val, Q_neg[k].val, X)) { k++; // If P*Q > X, this Q_neg[k] is too small (too negative). Need less negative Q. Try Q_neg[k+1]. } // The current Q_neg[k] is the first one such that P*Q <= X. // All Q_neg elements from index k to size-1 will also satisfy the condition, because Q gets less negative (closer to 0), // and P is negative, so P*Q decreases. P_neg[i]*Q_neg[k+1] < P_neg[i]*Q_neg[k] <= X. count += (Q_neg.size() - k); // Count elements from index k to end. } } return count; } int main() { // Faster I/O ios_base::sync_with_stdio(false); cin.tie(NULL); ll S; // Read dimensions K, L, M, N and target rank S cin >> K >> L >> M >> N >> S; // Store sizes also as long long for safe arithmetic K_ll = K; L_ll = L; M_ll = M; N_ll = N; // Resize vectors and read input arrays A, B, C, D A.resize(K); B.resize(L); C.resize(M); D.resize(N); for (int i = 0; i < K; ++i) cin >> A[i]; for (int i = 0; i < L; ++i) cin >> B[i]; for (int i = 0; i < M; ++i) cin >> C[i]; for (int i = 0; i < N; ++i) cin >> D[i]; // Generate all products P = A[w]*B[x] and store them with original indices P_full.reserve(K * L); for (int i = 0; i < K; ++i) { for (int j = 0; j < L; ++j) { P_full.push_back({A[i] * B[j], i, j}); } } // Generate all products Q = C[y]*D[z] and store them with original indices Q_full.reserve(M * N); for (int i = 0; i < M; ++i) { for (int j = 0; j < N; ++j) { Q_full.push_back({C[i] * D[j], i, j}); } } // Sort the P and Q product lists based on value sort(P_full.begin(), P_full.end(), comparePItem); sort(Q_full.begin(), Q_full.end(), comparePItem); // Split the sorted lists P_full and Q_full into positive, negative, and zero parts for(const auto& item : P_full) { if (item.val > 0) P_pos.push_back(item); else if (item.val < 0) P_neg.push_back(item); else P_zero.push_back(item); } for(const auto& item : Q_full) { if (item.val > 0) Q_pos.push_back(item); else if (item.val < 0) Q_neg.push_back(item); else Q_zero.push_back(item); } // Binary search for the S-th smallest product value T // Set wide enough initial bounds for the binary search. Max product magnitude is ~8.1e17. ll low = -810000000000000000LL - 2; // A generous lower bound ll high = 810000000000000000LL + 2; // A generous upper bound ll ans_T = high; // Initialize answer T with the upper bound // Standard binary search loop while (low <= high) { // Calculate midpoint safely avoiding overflow ll mid = low + (high - low) / 2; // Check if the count of products <= mid is at least S if (count_le(mid) >= S) { // If yes, mid might be the answer T, or T could be smaller. // Store mid as a potential answer and try smaller values. ans_T = mid; high = mid - 1; } else { // If count < S, T must be larger than mid. low = mid + 1; } } // Output the found S-th smallest value T cout << ans_T << endl; // Find a specific quadruple (a, b, c, d) such that a*b*c*d = ans_T // Iterate through the generated P products for (const auto& p_item : P_full) { ll p_val = p_item.val; // Handle case where p_val is 0 if (p_val == 0) { // If T is 0, we need to find if there exists any Q=0. if (ans_T == 0) { // Use lower_bound to efficiently find if 0 exists in the sorted Q_full list auto it = lower_bound(Q_full.begin(), Q_full.end(), PItem{0, 0, 0}, comparePItem); // Check if iterator is valid and points to an element with value 0 if (it != Q_full.end() && it->val == 0) { // Found a pair (P=0, Q=0). Output corresponding a, b, c, d and exit. cout << A[p_item.idx1] << " " << B[p_item.idx2] << " " << C[it->idx1] << " " << D[it->idx2] << endl; return 0; } } } // Handle case where p_val is non-zero else { // Check if ans_T is divisible by p_val. If yes, calculate target Q value. if (ans_T % p_val == 0) { ll target_q_val = ans_T / p_val; // Use lower_bound to efficiently find potential Q value in sorted Q_full list auto it = lower_bound(Q_full.begin(), Q_full.end(), PItem{target_q_val, 0, 0}, comparePItem); // Check if iterator is valid and points to an element with the target value if (it != Q_full.end() && it->val == target_q_val) { // Found a pair (P, Q) such that P*Q = T. Output corresponding a, b, c, d and exit. cout << A[p_item.idx1] << " " << B[p_item.idx2] << " " << C[it->idx1] << " " << D[it->idx2] << endl; return 0; } } } } // The problem statement guarantees S is valid and a solution exists. // Therefore, the program should always find a quadruple and exit before reaching here. return 0; }