#1167025 (C++17) No.3588 Already Ready

• 問題: No.3588 Already Ready
• ユーザー: marc2825
• 提出日時: 2026-05-28 13:15:47
• 言語: C++17 (gcc 15.2.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 170 ms / 3,000 ms
• コード長: 14,244 bytes
• コンパイル時間: 1,736 ms
• コンパイル使用メモリ: 235,648 KB
• 実行使用メモリ: 15,488 KB
• 最終ジャッジ日時: 2026-07-10 21:13:29
• 合計ジャッジ時間: 5,197 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_0

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

ソースコード

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

const int INF = 1000000000;

// ==================================================
// Range-add range-min lazy segment tree
// ==================================================

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;
    }
};

// ==================================================
// Point-set range-min segment tree
// ==================================================

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;
    }
};

bool simulate(int N, int K, int M, const vector<int>& A, const vector<int>& seq) {
    int T = (int)seq.size();
    vector<int> win(N + 1, 0);

    for (int t = 1; t <= T; t++) {
        int c = seq[t - 1];
        if (c < 1 || c > N) return false;

        int before = (t - 1) + win[c];

        if (t < T) {
            if (before >= K) return false;
        } else {
            if (c != M) return false;
            if (before < K) return false;
        }

        win[c]++;
    }

    for (int i = 1; i <= N; i++) {
        if (T + win[i] != A[i]) return false;
    }

    return true;
}

vector<int> solve_fast(int N, int K, int M, const vector<int>& A) {
    long long S = 0;
    for (int i = 1; i <= N; i++) S += A[i];

    if (S % (N + 1) != 0) return {};

    long long T_ll = S / (N + 1);
    if (T_ll < 1) return {};

    int T = (int)T_ll;

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

    if (W[M] < 1) return {};
    if (A[M] - 2 < K) return {};

    int m = 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) return {};

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

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

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

    assert(sumB == m);

    if (m == 0) return vector<int>{M};

    vector<int> slack_initial(m + 1, INF);
    int required_until_now = 0;

    for (int time = 1; time <= m; time++) {
        required_until_now += deadline_count[time];

        int slack = time - required_until_now;
        if (slack < 0) return {};

        slack_initial[time] = slack;
    }

    assert(required_until_now == m);

    RangeAddRangeMinLazySegTree slack_tree(slack_initial);

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

    PointSetRangeMinSegTree team_tree(team_initial);

    vector<int> answer;
    answer.reserve(T);

    for (int position = 1; position <= m; position++) {
        if (team_tree.all_min() < position) return {};

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

        int limit = first_zero_position;

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

        if (chosen_team == N + 1) return {};

        answer.push_back(chosen_team);

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

        rem[chosen_team]--;

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

    answer.push_back(M);
    return answer;
}

string encode_state(int pos, const vector<int>& rem) {
    string s = to_string(pos);
    s.push_back(':');
    for (int i = 1; i < (int)rem.size(); i++) {
        s += to_string(rem[i]);
        s.push_back(',');
    }
    return s;
}

bool brute_can_finish_dfs(
    int N,
    int K,
    int M,
    int m,
    int pos,
    vector<int>& rem,
    unordered_set<string>& memo
) {
    if (pos == m + 1) {
        for (int i = 1; i <= N; i++) {
            if (rem[i] != 0) return false;
        }
        return true;
    }

    string key = encode_state(pos, rem);
    if (memo.count(key)) return false;

    for (int c = 1; c <= N; c++) {
        if (rem[c] == 0) continue;

        int already_won = 0;
        for (int i = 1; i < pos; i++) {
        }

        int before_wins = 0;
        // before_wins = initial_rem[c] - rem[c] is needed,
        // so this DFS version uses a caller-side remaining-only test below instead.
    }

    memo.insert(key);
    return false;
}

bool brute_can_finish_by_simulation(
    int N,
    int K,
    int M,
    const vector<int>& A,
    const vector<int>& prefix,
    const vector<int>& B
) {
    long long S = 0;
    for (int i = 1; i <= N; i++) S += A[i];
    int T = (int)(S / (N + 1));
    int m = T - 1;

    vector<int> used(N + 1, 0);
    for (int x : prefix) used[x]++;

    for (int i = 1; i <= N; i++) {
        if (used[i] > B[i]) return false;
    }

    vector<int> rem(N + 1);
    for (int i = 1; i <= N; i++) rem[i] = B[i] - used[i];

    unordered_set<string> memo;

    function<bool(int)> dfs = [&](int pos) -> bool {
        if (pos == m + 1) {
            vector<int> seq = prefix;
            seq.push_back(M);
            return simulate(N, K, M, A, seq);
        }

        string key = encode_state(pos, rem);
        if (memo.count(key)) return false;

        for (int c = 1; c <= N; c++) {
            if (rem[c] == 0) continue;

            rem[c]--;
            vector<int> seq = prefix;
            int filled = (int)prefix.size();
            // This DFS is only for tiny T, so rebuild the partial sequence from external recursion is awkward.
            rem[c]++;
        }

        memo.insert(key);
        return false;
    };

    return false;
}

bool brute_suffix_possible(
    int N,
    int K,
    int M,
    const vector<int>& A,
    const vector<int>& current
) {
    long long S = 0;
    for (int i = 1; i <= N; i++) S += A[i];
    if (S % (N + 1) != 0) return false;

    int T = (int)(S / (N + 1));
    int m = T - 1;

    if ((int)current.size() > m) return false;

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

    if (W[M] < 1) return false;
    if (A[M] - 2 < K) return false;

    vector<int> B(N + 1);
    for (int i = 1; i <= N; i++) {
        B[i] = W[i] - (i == M ? 1 : 0);
        if (B[i] < 0) return false;
    }

    vector<int> used(N + 1, 0);
    for (int c : current) {
        if (c < 1 || c > N) return false;
        used[c]++;
        if (used[c] > B[c]) return false;
    }

    vector<int> partial_win(N + 1, 0);
    for (int t = 1; t <= (int)current.size(); t++) {
        int c = current[t - 1];
        int before = (t - 1) + partial_win[c];
        if (before >= K) return false;
        partial_win[c]++;
    }

    vector<int> rem = B;
    for (int i = 1; i <= N; i++) rem[i] -= used[i];

    unordered_set<string> memo;

    function<bool(vector<int>&)> dfs = [&](vector<int>& seq) -> bool {
        int pos = (int)seq.size() + 1;

        if (pos == m + 1) {
            vector<int> full = seq;
            full.push_back(M);
            return simulate(N, K, M, A, full);
        }

        string key = encode_state(pos, rem);
        if (memo.count(key)) return false;

        for (int c = 1; c <= N; c++) {
            if (rem[c] == 0) continue;

            seq.push_back(c);
            rem[c]--;

            int before = (pos - 1);
            int wins_before = 0;
            for (int x : seq) {
                if (x == c) wins_before++;
            }
            wins_before--;

            before += wins_before;

            if (before < K && dfs(seq)) return true;

            rem[c]++;
            seq.pop_back();
        }

        memo.insert(key);
        return false;
    };

    vector<int> seq = current;
    return dfs(seq);
}

vector<int> solve_bruteforce(int N, int K, int M, const vector<int>& A) {
    long long S = 0;
    for (int i = 1; i <= N; i++) S += A[i];

    if (S % (N + 1) != 0) return {};
    int T = (int)(S / (N + 1));
    if (T < 1) return {};

    int m = T - 1;

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

    for (int pos = 1; pos <= m; pos++) {
        bool found = false;

        for (int c = 1; c <= N; c++) {
            ans.push_back(c);

            if (brute_suffix_possible(N, K, M, A, ans)) {
                found = true;
                break;
            }

            ans.pop_back();
        }

        if (!found) return {};
    }

    ans.push_back(M);

    if (!simulate(N, K, M, A, ans)) return {};
    return ans;
}

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

    vector<int> A(N + 1);
    for (int i = 1; i <= N; i++) cin >> A[i];

    long long S = 0;
    for (int i = 1; i <= N; i++) S += A[i];

    int T_est = -1;
    if (S % (N + 1) == 0) T_est = (int)(S / (N + 1));

    vector<int> ans;

    const int BRUTE_N_LIMIT = 8;
    const int BRUTE_T_LIMIT = 10;

    if (T_est >= 0 && N <= BRUTE_N_LIMIT && T_est <= BRUTE_T_LIMIT) {
        ans = solve_bruteforce(N, K, M, A);
    } else {
        ans = solve_fast(N, K, M, A);
    }

    if (ans.empty()) {
        cout << -1 << '\n';
        return 0;
    }

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

    return 0;
}