結果
| 問題 |
No.2221 Set X
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:19:36 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 7,595 bytes |
| コンパイル時間 | 1,206 ms |
| コンパイル使用メモリ | 116,376 KB |
| 実行使用メモリ | 7,844 KB |
| 最終ジャッジ日時 | 2025-05-14 13:20:47 |
| 合計ジャッジ時間 | 6,031 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 13 TLE * 1 -- * 26 |
ソースコード
#include <iostream>
#include <vector>
#include <numeric>
#include <set> // Use set to maintain sorted order and uniqueness of candidates
#include <unordered_set> // Use unordered_set for fast calculation of distinct floor values
#include <algorithm>
#include <cmath>
int main() {
// Optimize input/output operations
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int N;
std::cin >> N;
std::vector<long long> A(N);
bool all_zero = true; // Flag to check if all elements are zero
for (int i = 0; i < N; ++i) {
std::cin >> A[i];
if (A[i] != 0) {
all_zero = false;
}
}
// Initialize minimum f value and the corresponding X
long long min_f = -1;
long long best_X = -1;
// Calculate f(1)
if (N > 0) { // Check N>0 based on constraints
// Compute the number of distinct values for X=1
std::unordered_set<long long> distinct_floors_1;
for (long long val : A) {
// For X=1, floor(val / 1) = val
distinct_floors_1.insert(val);
}
// f(1) = (1+1) * |{A_1, ..., A_N}|. Since A is sorted and distinct, this is N.
// The provided A is already sorted A_1 < ... < A_N
// But it can contain 0. Example: 0 1 2 3. Distinct values are 0,1,2,3. Size is N.
// Exception: If N=1 and A={0}, size is 1.
// Generally, size is N if elements are distinct.
// The problem states A_1 < A_2 < ... < A_N, so they are distinct. Size is N.
min_f = (1 + 1) * (long long)N;
best_X = 1;
} else {
// N=0 is not possible based on constraints 1 <= N <= 10^5
return 1; // Error case
}
// Calculate f(A_N + 1) if A_N >= 0
// A_N is the last element A[N-1]
if (N > 0 && A[N - 1] >= 0) {
long long X = A[N - 1] + 1;
// X must be a positive integer. If A[N-1]=0, X=1. If A[N-1]=-1 (not possible), X=0.
if (X > 0) {
// For X > A_N, floor(A_i / X) = 0 for all i, since 0 <= A_i <= A_N < X.
// The set of distinct floor values is {0}. Its size is 1.
long long current_f = (X + 1) * 1;
// Update min_f and best_X if current_f is better or equal (take smaller X)
if (min_f == -1 || current_f < min_f) { // Initialize min_f if not set, or update if smaller
min_f = current_f;
best_X = X;
} else if (current_f == min_f) { // If equal, choose the smaller X
best_X = std::min(best_X, X);
}
}
}
// Set of candidate X values. Use std::set to keep them sorted and unique.
std::set<long long> candidate_X;
candidate_X.insert(1); // Always check X=1
if (N > 0 && A[N-1] >= 0) {
long long X_an_plus_1 = A[N-1] + 1;
if (X_an_plus_1 > 0) { // Check if A_N+1 is a positive integer
candidate_X.insert(X_an_plus_1); // Check X = A_N + 1
}
}
// Use the current minimum f value as an upper bound to prune candidate X values.
// Any X must satisfy (X+1) * |S(X)| >= X+1.
// If X+1 > min_f, then this X cannot achieve a smaller f value.
// So we only need to consider X such that X+1 <= min_f.
long long current_min_f_bound = min_f;
// Generate candidate X values.
// Critical points for X are where floor(A_i / X) potentially changes value.
// This happens around X = A_i / k for integer k.
// The value floor(A_i / X) changes from floor(A_i / (X-1)) at X = floor(A_i / k) + 1.
// We test candidate points X = floor(A_i / k) and X = floor(A_i / k) + 1.
for (int i = 0; i < N; ++i) {
if (A[i] == 0) continue; // floor(0/k) = 0, doesn't give interesting candidates beyond X=1
long long k = 1;
while (true) { // Loop through distinct floor values floor(A_i / k)
long long floor_val = A[i] / k;
// Candidate check points are X = floor_val and X = floor_val + 1
// Check X = floor_val
if (floor_val > 0) { // X must be positive integer
// Minimum possible f value for X=floor_val is (floor_val+1)*1.
// Check if this minimal value is potentially better than current minimum.
if (floor_val + 1 <= current_min_f_bound)
candidate_X.insert(floor_val);
}
// Check X = floor_val + 1
long long cand_X_plus1 = floor_val + 1;
if (cand_X_plus1 > 0) { // X must be positive integer
// Minimum possible f value for X=cand_X_plus1 is (cand_X_plus1 + 1)*1.
if (cand_X_plus1 + 1 <= current_min_f_bound) {
candidate_X.insert(cand_X_plus1);
}
}
if (floor_val == 0) break; // Quotient is 0, will remain 0 for larger k. Stop.
// Jump k to the smallest value > k such that floor(A_i / k') < floor_val
// This is k' = A_i / floor_val + 1
k = A[i] / floor_val + 1;
// Check if k might have overflowed or become too large
if (k > A[i] && A[i] > 0) break; // Optimization: if k > A_i, floor(A_i/k)=0
if (k <= 0) break; // Protect against potential overflow leading to non-positive k
}
}
// Iterate through the sorted unique candidate X values
for (long long X : candidate_X) {
if (X == 0) continue; // X must be a positive integer
// Optimization: If the minimal possible value (X+1)*1 is already >= current minimum f,
// and X is not the current best_X, we can potentially skip. Check carefully.
// If X+1 > min_f, then f(X) = (X+1)|S(X)| >= X+1 > min_f, so skip.
// If X+1 == min_f, then f(X) = (X+1)|S(X)| >= min_f. It can only be equal if |S(X)|=1.
// If f(X) == min_f, we only update best_X if X < current best_X.
if (X + 1 > min_f) continue;
// Calculate the number of distinct floor values for current X
std::unordered_set<long long> distinct_floors;
for (long long val : A) {
distinct_floors.insert(val / X);
}
// Handle edge case N=0? Constraints say N>=1.
// If all A_i are 0, distinct_floors will contain only 0. Size is 1.
// If N>0 and distinct_floors is empty, this is unexpected. If A contains values >=0 and X>=1, floor is always >=0.
// Let's ensure size is at least 1 if N>0.
size_t set_size = distinct_floors.size();
if (N > 0 && set_size == 0) {
// This case should only happen if all A_i=0 and X >= 1. Then {0} is the set.
if (all_zero) set_size = 1;
else { /* Possibly an error or unexpected state */ }
}
// Calculate f(X) = (X+1) * |S(X)|
long long current_f = (X + 1) * set_size;
// Update minimum f value and best X
if (current_f < min_f) {
min_f = current_f;
best_X = X;
// We could update current_min_f_bound here, but candidate generation is already done.
// Iterating in increasing order of X, this update doesn't prune more candidates.
} else if (current_f == min_f) {
// If f values are equal, choose the smaller X
best_X = std::min(best_X, X);
}
}
// Output the minimum X and the minimum f value
std::cout << best_X << std::endl;
std::cout << min_f << std::endl;
return 0;
}