結果
| 問題 |
No.1361 [Zelkova 4th Tune *] QUADRUPLE-SEQUENCEの詩
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:10:34 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 11,516 bytes |
| コンパイル時間 | 1,193 ms |
| コンパイル使用メモリ | 84,372 KB |
| 実行使用メモリ | 32,372 KB |
| 最終ジャッジ日時 | 2025-05-14 13:12:02 |
| 合計ジャッジ時間 | 11,608 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 47 WA * 27 |
ソースコード
#include <iostream>
#include <vector>
#include <algorithm>
// 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<ll> A, B, C, D;
// Vectors to store all products P = A[w]*B[x] and Q = C[y]*D[z]
vector<PItem> P_full, Q_full;
// Vectors to store positive, negative, and zero products separately for efficient counting in count_le function
vector<PItem> P_pos, P_neg, P_zero;
vector<PItem> 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;
}