結果

問題 No.2221 Set X
コンテスト
ユーザー limbo
提出日時 2025-12-02 04:09:10
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 94 ms / 2,000 ms
コード長 2,667 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 717 ms
コンパイル使用メモリ 78,144 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-12-02 04:09:15
合計ジャッジ時間 4,246 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void solve() {
    int N;
    // Read number of projectiles
    if (!(cin >> N)) return;
    
    vector<int> A(N);
    for(int i = 0; i < N; ++i) {
        cin >> A[i];
    }
    
    // Although the problem states A is sorted, strict adherence requires 
    // ensuring it is sorted. Since input is guaranteed sorted, we skip sort.
    
    long long min_cost = -1;
    long long best_W = -1;
    
    // Optimization: The optimal W will never exceed ~2*N.
    // Explanation: f(1) <= 2*N. For any W, f(W) >= W+1.
    // If W > 2*N, then f(W) > 2*N >= f(1), so it cannot be optimal.
    // We also cap at A.back() + 2 because W beyond the furthest projectile 
    // just increases cost linearly.
    long long limit = 2LL * N + 2;
    if (!A.empty()) {
        limit = min(limit, (long long)A.back() + 2);
    }
    
    // Iterate through all candidate widths
    for (long long W = 1; W <= limit; ++W) {
        long long segments = 0;
        int idx = 0;
        bool possible = true;
        
        // Calculate number of segments for this width W using "Jumps"
        while (idx < N) {
            segments++;
            
            // Pruning: If partial cost already exceeds the best found, stop.
            // This is crucial for performance to avoid O(N^2) behavior.
            if (min_cost != -1 && segments * (W + 1) > min_cost) {
                possible = false;
                break;
            }
            
            long long current_pos = A[idx];
            // Calculate the start of the NEXT segment boundary
            // Current segment is [k*W, (k+1)*W), so boundary is (k+1)*W
            long long boundary = (current_pos / W + 1) * W;
            
            // If the boundary is beyond the last projectile, we are done
            if (boundary > A.back()) {
                idx = N; 
                break;
            }
            
            // Efficiently jump to the first projectile in the next segment
            auto it = lower_bound(A.begin() + idx, A.end(), boundary);
            idx = (int)(it - A.begin());
        }
        
        if (possible) {
            long long current_cost = segments * (W + 1);
            
            // Update minimum
            if (min_cost == -1 || current_cost < min_cost) {
                min_cost = current_cost;
                best_W = W;
            }
        }
    }
    
    // Output format as requested
    cout << best_W << "\n" << min_cost << "\n";
}

int main() {
    // Fast I/O
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    solve();
    
    return 0;
}
0