結果

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

ソースコード

diff #
raw source code 

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

using namespace std;

// A lightweight Doubly Linked List Node wrapper
struct Node {
    int prev = -1;
    int next = -1;
};

// Global arrays to simulate the linked lists for 'plus' and 'minus' sets
// We use these to get O(1) removals and fast iteration
vector<Node> plus_nodes;
vector<Node> minus_nodes;
int plus_head = 0;
int minus_head = 0;
int list_size; // Tracks len(plus)

// Function to remove index 'u' from the 'plus' list
void remove_plus(int u) {
    int p = plus_nodes[u].prev;
    int n = plus_nodes[u].next;
    
    if (p != -1) plus_nodes[p].next = n;
    else plus_head = n; // If we removed the head
    
    if (n != -1) plus_nodes[n].prev = p;
    
    list_size--; // Decrease the count of active clusters
}

// Function to remove index 'u' from the 'minus' list
void remove_minus(int u) {
    int p = minus_nodes[u].prev;
    int n = minus_nodes[u].next;
    
    if (p != -1) minus_nodes[p].next = n;
    else minus_head = n;
    
    if (n != -1) minus_nodes[n].prev = p;
}

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

    int N;
    if (!(cin >> N)) return 0;

    vector<long long> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }

    // Initialize logic variables
    long long arg_x = 1;
    long long min_val = 2LL * N; // Safe upper bound f(1) approx 2N

    // --- Initialize Linked Lists ---
    // 'plus' initially contains 0, 1, ..., N-1
    // 'minus' initially contains 0, 1, ..., N-1
    plus_nodes.resize(N);
    minus_nodes.resize(N);
    list_size = N;

    for (int i = 0; i < N; i++) {
        if (i > 0) plus_nodes[i].prev = i - 1;
        if (i < N - 1) plus_nodes[i].next = i + 1;
        
        if (i > 0) minus_nodes[i].prev = i - 1;
        if (i < N - 1) minus_nodes[i].next = i + 1;
    }

    // --- Precompute Differences ---
    // We store (difference, index)
    // We sort ascending to process smallest gaps first
    vector<pair<long long, int>> diff;
    diff.reserve(N - 1);
    for (int i = 0; i < N - 1; i++) {
        diff.push_back({A[i+1] - A[i], i});
    }
    sort(diff.begin(), diff.end());

    int diff_ptr = 0;
    int diff_sz = diff.size();

    // Loop X from 1 to 2N
    for (long long x = 1; x <= 2 * N; x++) {
        
        // Process all gaps smaller than or equal to current Width x
        // If gap <= x, the segments merge.
        while (diff_ptr < diff_sz && diff[diff_ptr].first <= x) {
            int i = diff[diff_ptr].second;
            // Remove 'i' from plus (it's no longer a start of a cluster)
            remove_plus(i);
            // Remove 'i+1' from minus (it's no longer an end of a cluster)
            remove_minus(i + 1);
            diff_ptr++;
        }

        // --- Heuristic Pruning (The "Editorial" Logic) ---
        // Cost = (Segments) * (x + 1)
        // Segments = list_size
        // If Segments * (x+1) >= min_val, we can't beat the record.
        // This keeps the complexity to O(N log N) total.
        if (list_size * (x + 1) < min_val) {
            long long tmp = 0;

            // Iterate through active 'plus' indices (Cluster Starts)
            int curr = plus_head;
            while (curr != -1) {
                tmp += (A[curr] / x);
                curr = plus_nodes[curr].next;
            }

            // Iterate through active 'minus' indices (Cluster Ends)
            curr = minus_head;
            while (curr != -1) {
                tmp -= (A[curr] / x);
                curr = minus_nodes[curr].next;
            }

            // Add the count of clusters
            tmp += list_size;
            
            // Calculate final mana cost
            long long total_cost = tmp * (x + 1);

            if (total_cost < min_val) {
                min_val = total_cost;
                arg_x = x;
            }
        }
    }

    cout << arg_x << "\n" << min_val << "\n";

    return 0;
}
0