#1167026 (C++23) No.3588 Already Ready

• 問題: No.3588 Already Ready
• ユーザー: marc2825
• 提出日時: 2026-05-28 13:17:50
• 言語: C++23 (gcc 15.2.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 136 ms / 3,000 ms
• コード長: 8,363 bytes
• コンパイル時間: 2,147 ms
• コンパイル使用メモリ: 341,716 KB
• 実行使用メモリ: 15,488 KB
• 最終ジャッジ日時: 2026-07-10 21:13:24
• 合計ジャッジ時間: 5,896 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge3_0

ファイルパターン	結果
sample	AC * 3
other	AC * 69

ソースコード

#include <bits/stdc++.h>
using namespace std;

const int INF = 1000000000;

// ==================================================
// Segment Tree / Lazy Segment Tree implementation based on ACL (https://github.com/atcoder/ac-library)
// ==================================================

struct RangeAddRangeMinLazySegTree {
    int n, size, logn;
    vector<int> min_value, lazy_add;

    RangeAddRangeMinLazySegTree() : n(0), size(1), logn(0) {}

    RangeAddRangeMinLazySegTree(const vector<int>& initial_values) {
        init(initial_values);
    }

    void init(const vector<int>& initial_values) {
        n = (int)initial_values.size();
        size = 1;
        logn = 0;
        while (size < n) {
            size <<= 1;
            logn++;
        }

        min_value.assign(2 * size, INF);
        lazy_add.assign(size, 0);

        for (int i = 0; i < n; i++) {
            min_value[size + i] = initial_values[i];
        }
        for (int i = size - 1; i >= 1; i--) {
            pull(i);
        }
    }

    void pull(int node) {
        min_value[node] = min(min_value[node * 2], min_value[node * 2 + 1]);
    }

    void apply_to_node(int node, int add_value) {
        min_value[node] += add_value;
        if (node < size) lazy_add[node] += add_value;
    }

    void push(int node) {
        if (lazy_add[node] != 0) {
            apply_to_node(node * 2, lazy_add[node]);
            apply_to_node(node * 2 + 1, lazy_add[node]);
            lazy_add[node] = 0;
        }
    }

    void range_add(int left, int right, int add_value) {
        if (left >= right) return;

        left += size;
        right += size;

        for (int h = logn; h >= 1; h--) {
            if (((left >> h) << h) != left) push(left >> h);
            if (((right >> h) << h) != right) push((right - 1) >> h);
        }

        int original_left = left;
        int original_right = right;

        while (left < right) {
            if (left & 1) apply_to_node(left++, add_value);
            if (right & 1) apply_to_node(--right, add_value);
            left >>= 1;
            right >>= 1;
        }

        left = original_left;
        right = original_right;

        for (int h = 1; h <= logn; h++) {
            if (((left >> h) << h) != left) pull(left >> h);
            if (((right >> h) << h) != right) pull((right - 1) >> h);
        }
    }

    int all_min() const {
        return min_value[1];
    }

    template <class Predicate>
    int max_right(int left, Predicate pred) {
        if (left == n) return n;

        left += size;

        for (int h = logn; h >= 1; h--) {
            push(left >> h);
        }

        int current_min = INF;

        do {
            while ((left & 1) == 0) left >>= 1;

            int next_min = min(current_min, min_value[left]);
            if (!pred(next_min)) {
                while (left < size) {
                    push(left);
                    left *= 2;

                    int candidate_min = min(current_min, min_value[left]);
                    if (pred(candidate_min)) {
                        current_min = candidate_min;
                        left++;
                    }
                }
                return left - size;
            }

            current_min = next_min;
            left++;
        } while ((left & -left) != left);

        return n;
    }
};

struct PointSetRangeMinSegTree {
    int n, size;
    vector<int> min_value;

    PointSetRangeMinSegTree() : n(0), size(1) {}

    PointSetRangeMinSegTree(const vector<int>& initial_values) {
        init(initial_values);
    }

    void init(const vector<int>& initial_values) {
        n = (int)initial_values.size();
        size = 1;
        while (size < n) size <<= 1;

        min_value.assign(2 * size, INF);

        for (int i = 0; i < n; i++) {
            min_value[size + i] = initial_values[i];
        }
        for (int i = size - 1; i >= 1; i--) {
            min_value[i] = min(min_value[i * 2], min_value[i * 2 + 1]);
        }
    }

    void set_value(int index, int value) {
        index += size;
        min_value[index] = value;

        while (index >>= 1) {
            min_value[index] = min(min_value[index * 2], min_value[index * 2 + 1]);
        }
    }

    int all_min() const {
        return min_value[1];
    }

    template <class Predicate>
    int max_right(int left, Predicate pred) {
        if (left == n) return n;

        left += size;
        int current_min = INF;

        do {
            while ((left & 1) == 0) left >>= 1;

            int next_min = min(current_min, min_value[left]);
            if (!pred(next_min)) {
                while (left < size) {
                    left *= 2;

                    int candidate_min = min(current_min, min_value[left]);
                    if (pred(candidate_min)) {
                        current_min = candidate_min;
                        left++;
                    }
                }
                return left - size;
            }

            current_min = next_min;
            left++;
        } while ((left & -left) != left);

        return n;
    }
};


// ==================================================
// Main solution
// ==================================================

int main() {
    int N, K, M;
    cin >> N >> K >> M;

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

    if (S % (N + 1) != 0) {
        cout << -1 << '\n';
        return 0;
    }

    long long T = S / (N + 1);

    if (T < 1) {
        cout << -1 << '\n';
        return 0;
    }

    vector<int> W(N + 1);
    for (int i = 1; i <= N; i++) {
        W[i] = A[i] - T;
        if (W[i] < 0) {
            cout << -1 << '\n';
            return 0;
        }
    }

    if (W[M] < 1) {
        cout << -1 << '\n';
        return 0;
    }

    if (A[M] - 2 < K) {
        cout << -1 << '\n';
        return 0;
    }

    int m = (int)(T - 1);

    vector<int> B(N + 1, 0), rem(N + 1, 0);
    vector<int> deadline(N + 1, INF);
    vector<int> deadline_count(max(1, m) + 1, 0);

    int sumB = 0;

    for (int i = 1; i <= N; i++) {
        int b = W[i] - (i == M ? 1 : 0);
        if (b < 0) {
            cout << -1 << '\n';
            return 0;
        }

        B[i] = b;
        rem[i] = b;
        sumB += b;

        if (b > 0) {
            int d = K + 1 - b;
            if (d < 1) {
                cout << -1 << '\n';
                return 0;
            }

            int effective_deadline = min(d, m);
            deadline[i] = effective_deadline;
            deadline_count[effective_deadline] += b;
        }
    }

    assert(sumB == m);

    if (m == 0) {
        cout << 1 << '\n';
        cout << M << '\n';
        return 0;
    }

    vector<int> slack_init(m + 1, INF);
    int pref = 0;

    for (int x = 1; x <= m; x++) {
        pref += deadline_count[x];

        int slack = x - pref;
        if (slack < 0) {
            cout << -1 << '\n';
            return 0;
        }

        slack_init[x] = slack;
    }

    assert(pref == m);

    RangeAddRangeMinLazySegTree slack_tree(slack_init);

    vector<int> team_init(N + 1, INF);
    for (int i = 1; i <= N; i++) {
        if (rem[i] > 0) {
            team_init[i] = deadline[i];
        }
    }

    PointSetRangeMinSegTree team_tree(team_init);

    vector<int> ans;
    ans.reserve((size_t)T);

    for (int p = 1; p <= m; p++) {
        if (team_tree.all_min() < p) {
            cout << -1 << '\n';
            return 0;
        }

        int first_zero = slack_tree.max_right(p, [](int min_slack) {
            return min_slack > 0;
        });

        int E = (first_zero == m + 1 ? m + 1 : first_zero);

        int c = team_tree.max_right(1, [&](int min_deadline) {
            return min_deadline > E;
        });

        if (c == N + 1) {
            cout << -1 << '\n';
            return 0;
        }

        ans.push_back(c);

        if (p < deadline[c]) {
            slack_tree.range_add(p, deadline[c], -1);
        }

        rem[c]--;

        if (rem[c] == 0) {
            team_tree.set_value(c, INF);
        }
    }

    ans.push_back(M);

    cout << ans.size() << '\n';

    for (int i = 0; i < (int)ans.size(); i++) {
        if (i) cout << ' ';
        cout << ans[i];
    }

    cout << '\n';

    return 0;
}