結果
| 問題 |
No.1440 The Quiz Competition
|
| コンテスト | |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:18:12 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,563 bytes |
| コンパイル時間 | 661 ms |
| コンパイル使用メモリ | 73,220 KB |
| 実行使用メモリ | 7,844 KB |
| 最終ジャッジ日時 | 2025-05-14 13:19:01 |
| 合計ジャッジ時間 | 1,863 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | WA * 27 |
ソースコード
#include <iostream>
#include <algorithm>
#include <vector> // Included for standard practice, though not strictly needed here
// Use typedef for long long for brevity
typedef long long ll;
// Using namespace std for convenience
using namespace std;
// Check function for X_upper: Checks if (K-1) * max(0LL, X+1) <= A
// Returns true if the condition holds, false otherwise.
// Assumes K >= 2 as K=1 is handled separately in main.
bool check_upper(ll X, ll K, ll A) {
// K is at least 2, so K-1 is at least 1.
ll K_minus_1 = K - 1;
// Calculate max(0LL, X+1) safely
// Check if X is LLONG_MAX to prevent overflow in X+1.
// However, X is bounded by A (<= 10^9), so X+1 will not overflow standard 64-bit ll.
ll val_plus_1 = X + 1;
ll term = max(0LL, val_plus_1);
// If term is 0, the condition becomes 0 <= A. Since A is always non-negative, this is true.
if (term == 0) {
return true;
}
// Use unsigned __int128 for intermediate product calculation to avoid potential overflow.
// This type is available in GCC/Clang compilers and handles values up to 2^128 - 1.
// The maximum product could be around (2e5) * (1e9) = 2e14, which fits within signed long long.
// But using unsigned __int128 is safer and handles larger intermediate values if necessary.
unsigned __int128 k128 = K_minus_1;
unsigned __int128 t128 = term;
// Calculate required A based on K-1 participants needing score >= X+1
unsigned __int128 required_A = k128 * t128;
// Check if the available A is sufficient.
return required_A <= (unsigned __int128)A;
}
// Check function for X_max: Checks if K * max(0LL, X) <= A
// Returns true if the condition holds, false otherwise.
// Assumes K >= 1.
bool check_max(ll X, ll K, ll A) {
// Calculate max(0LL, X)
ll term = max(0LL, X);
// If term is 0, condition is 0 <= A, which is true since A >= 0.
if (term == 0) {
return true;
}
// Use unsigned __int128 for intermediate product calculation to avoid overflow.
unsigned __int128 k128 = K;
unsigned __int128 t128 = term;
// Calculate required A based on K participants needing score >= X
unsigned __int128 required_A = k128 * t128;
// Check if the available A is sufficient.
return required_A <= (unsigned __int128)A;
}
int main() {
// Use faster I/O operations
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int T; // Number of test cases
cin >> T;
while (T--) {
ll N; // Number of participants
ll A; // Total correct answers
ll W; // Total incorrect answers
ll K; // Target rank
cin >> N >> A >> W >> K;
// Handle edge case K=1 directly.
// The maximum score for rank 1 is always A (achieved by one person getting all A correct answers and 0 incorrect).
if (K == 1) {
cout << A << "\n";
continue;
}
// Define the binary search range for score X.
ll low_bound;
if (W == 0) {
// If W=0, penalty is always 0. Scores S_i = a_i >= 0. Minimum possible score is 0.
low_bound = 0;
} else {
// If W > 0, scores can be negative.
// The minimum score is roughly -W*(W+1)/2. Max W=10^9, so W^2/2 is about 5*10^17.
// Use -10^18 as a safe lower bound.
low_bound = -1000000000000000000LL; // -1 * 10^18
}
// The maximum possible score for any individual is A.
ll high_bound = A;
// Initialize results to a value indicating no solution found yet.
// Using low_bound - 1 ensures that if no value satisfies the check, this initial value is kept.
ll X_upper = low_bound - 1;
ll current_low = low_bound;
ll current_high = high_bound;
// Binary search to find the maximum X satisfying the check_upper condition.
// check_upper derives from the necessary condition that K-1 people must have score > X, minimum is X+1.
while(current_low <= current_high) {
// Calculate midpoint safely avoiding overflow for large bounds.
ll mid = current_low + (current_high - current_low) / 2;
if (check_upper(mid, K, A)) {
// mid satisfies the condition. It's a possible upper bound or lower. Record it.
X_upper = mid;
// Try to find a larger X that also satisfies the condition.
current_low = mid + 1;
} else {
// mid does not satisfy the condition. Need to check smaller values.
current_high = mid - 1;
}
}
// Initialize X_max similarly
ll X_max = low_bound - 1;
current_low = low_bound;
current_high = high_bound;
// Binary search to find the maximum X satisfying the check_max condition.
// check_max derives from the necessary condition that K people must have score >= X.
while(current_low <= current_high) {
ll mid = current_low + (current_high - current_low) / 2;
if (check_max(mid, K, A)) {
// mid satisfies the condition. Record it.
X_max = mid;
// Try to find a larger X.
current_low = mid + 1;
} else {
// mid does not satisfy. Need to check smaller values.
current_high = mid - 1;
}
}
// The maximum possible score for the K-th person is constrained by both necessary conditions.
// So, take the minimum of the two bounds found.
ll final_X = min(X_upper, X_max);
// Special condition: If W=0, all scores must be non-negative (S_i = a_i >= 0).
// If the computed maximum possible score final_X is negative, Rank K cannot exist
// with a non-negative score. This implies it's impossible to achieve rank K.
if (W == 0 && final_X < 0) {
cout << ":(\n";
} else {
// If final_X remained at the initial 'impossible' value (low_bound - 1),
// it means neither check found any feasible score.
// However, the logic ensures some value (possibly negative) is usually found unless A=0 and K is large.
// The check `W == 0 && final_X < 0` handles the critical impossibility case.
// Otherwise, output the calculated maximum score.
cout << final_X << "\n";
}
}
return 0;
}