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

• 問題: No.3588 Already Ready
• ユーザー: marc2825
• 提出日時: 2026-05-30 09:34:34
• 言語: C++17 (gcc 15.2.0 + boost 1.90.0)
• 結果: TLE
• 実行時間: -
• コード長: 10,371 bytes
• コンパイル時間: 1,683 ms
• コンパイル使用メモリ: 229,816 KB
• 実行使用メモリ: 33,048 KB
• 最終ジャッジ日時: 2026-07-10 20:58:32
• 合計ジャッジ時間: 10,363 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_1

ファイルパターン	結果
sample	AC * 3
other	AC * 34 TLE * 1 -- * 34

ソースコード

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

using ll = long long;

const long long INF64 = (1LL << 60);
const long long BIG = (1LL << 61);

// -----------------------------
// 解の検証用シミュレーション
// -----------------------------
bool validate_answer(
    int N,
    int K,
    int M,
    const vector<int>& A,
    const vector<int>& ans
) {
    if (ans.empty()) return false;
    if (ans.back() != M) return false;

    vector<int> score(N, 0);

    for (int t = 0; t < (int)ans.size(); t++) {
        int winner = ans[t];
        if (winner < 0 || winner >= N) return false;

        bool is_last = (t + 1 == (int)ans.size());

        if (score[winner] >= K) {
            if (!is_last) return false;
        } else {
            if (is_last) return false;
        }

        for (int i = 0; i < N; i++) score[i]++;
        score[winner]++;
    }

    return score == A;
}

// -----------------------------
// 共通: 最終スコアから T, w, d を復元
// -----------------------------
bool build_counts(
    int N,
    int K,
    int M,
    const vector<int>& A,
    int& T,
    vector<int>& d
) {
    long long S = 0;
    for (int x : A) S += x;

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

    T = (int)(S / (N + 1));
    if (T <= 0) return false;

    vector<int> w(N);
    long long sw = 0;

    for (int i = 0; i < N; i++) {
        if (A[i] < T) return false;
        w[i] = A[i] - T;
        sw += w[i];
    }

    if (sw != T) return false;

    // 最後の勝者 M は少なくとも1回勝っている必要がある
    if (w[M] <= 0) return false;

    // 最後の試合開始直前に M が ready である必要がある
    if (A[M] - 2 < K) return false;

    d = w;
    d[M]--;

    return true;
}

// -----------------------------
// 小さい場合: 愚直 DFS
// -----------------------------
bool brute_dfs(
    int N,
    int K,
    int M,
    int T,
    const vector<int>& A,
    vector<int>& rem,
    vector<int>& win_so_far,
    vector<int>& prefix
) {
    int pos = (int)prefix.size() + 1; // 1-indexed, 最後の M を除いた試合位置

    if ((int)prefix.size() == T - 1) {
        vector<int> ans = prefix;
        ans.push_back(M);
        if (validate_answer(N, K, M, A, ans)) {
            prefix = ans;
            return true;
        }
        return false;
    }

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

        // この試合開始直前のスコア
        int score_before = (pos - 1) + win_so_far[i];

        // 最後以外で ready なチームが勝つとそこで終了してしまうので不可
        if (score_before >= K) continue;

        rem[i]--;
        win_so_far[i]++;
        prefix.push_back(i);

        if (brute_dfs(N, K, M, T, A, rem, win_so_far, prefix)) {
            return true;
        }

        prefix.pop_back();
        win_so_far[i]--;
        rem[i]++;
    }

    return false;
}

vector<int> solve_brute(
    int N,
    int K,
    int M,
    const vector<int>& A
) {
    int T;
    vector<int> d;

    if (!build_counts(N, K, M, A, T, d)) return {};

    vector<int> rem = d;
    vector<int> win_so_far(N, 0);
    vector<int> prefix;

    bool ok = brute_dfs(N, K, M, T, A, rem, win_so_far, prefix);
    if (!ok) return {};

    return prefix;
}

// -----------------------------
// Range add + range min segment tree
// -----------------------------
struct RangeMinAddSeg {
    int n;
    vector<long long> mn, lazy;

    RangeMinAddSeg() {}

    RangeMinAddSeg(const vector<long long>& a) {
        // a は 1-indexed
        n = (int)a.size() - 1;
        mn.assign(4 * (n + 5), BIG);
        lazy.assign(4 * (n + 5), 0);
        build(1, 1, n, a);
    }

    void build(int node, int l, int r, const vector<long long>& a) {
        if (l == r) {
            mn[node] = a[l];
            return;
        }
        int mid = (l + r) / 2;
        build(node * 2, l, mid, a);
        build(node * 2 + 1, mid + 1, r, a);
        mn[node] = min(mn[node * 2], mn[node * 2 + 1]);
    }

    void push(int node) {
        long long z = lazy[node];
        if (z == 0) return;

        for (int ch : {node * 2, node * 2 + 1}) {
            mn[ch] += z;
            lazy[ch] += z;
        }
        lazy[node] = 0;
    }

    void range_add(int ql, int qr, long long x) {
        if (ql > qr) return;
        ql = max(ql, 1);
        qr = min(qr, n);
        if (ql > qr) return;
        range_add(1, 1, n, ql, qr, x);
    }

    void range_add(int node, int l, int r, int ql, int qr, long long x) {
        if (qr < l || r < ql) return;
        if (ql <= l && r <= qr) {
            mn[node] += x;
            lazy[node] += x;
            return;
        }

        push(node);
        int mid = (l + r) / 2;
        range_add(node * 2, l, mid, ql, qr, x);
        range_add(node * 2 + 1, mid + 1, r, ql, qr, x);
        mn[node] = min(mn[node * 2], mn[node * 2 + 1]);
    }

    long long all_min() const {
        return mn[1];
    }

    int first_zero_from(int ql) {
        if (ql > n) return (int)INF64;
        return first_zero_from(1, 1, n, ql);
    }

    int first_zero_from(int node, int l, int r, int ql) {
        if (r < ql || mn[node] > 0) return (int)INF64;

        if (l == r) return l;

        push(node);
        int mid = (l + r) / 2;

        int left = first_zero_from(node * 2, l, mid, ql);
        if (left != (int)INF64) return left;

        return first_zero_from(node * 2 + 1, mid + 1, r, ql);
    }
};

// -----------------------------
// チーム番号順に見て、deadline <= x である最小チームを探す segtree
// -----------------------------
struct LabelMinSeg {
    int n;
    vector<long long> mn;

    LabelMinSeg() {}

    LabelMinSeg(const vector<long long>& a) {
        n = (int)a.size();
        mn.assign(4 * (n + 5), BIG);
        build(1, 0, n - 1, a);
    }

    void build(int node, int l, int r, const vector<long long>& a) {
        if (l == r) {
            mn[node] = a[l];
            return;
        }
        int mid = (l + r) / 2;
        build(node * 2, l, mid, a);
        build(node * 2 + 1, mid + 1, r, a);
        mn[node] = min(mn[node * 2], mn[node * 2 + 1]);
    }

    void update(int idx, long long val) {
        update(1, 0, n - 1, idx, val);
    }

    void update(int node, int l, int r, int idx, long long val) {
        if (l == r) {
            mn[node] = val;
            return;
        }
        int mid = (l + r) / 2;
        if (idx <= mid) update(node * 2, l, mid, idx, val);
        else update(node * 2 + 1, mid + 1, r, idx, val);
        mn[node] = min(mn[node * 2], mn[node * 2 + 1]);
    }

    int first_leq(long long x) {
        if (mn[1] > x) return -1;
        return first_leq(1, 0, n - 1, x);
    }

    int first_leq(int node, int l, int r, long long x) {
        if (l == r) return l;
        int mid = (l + r) / 2;

        if (mn[node * 2] <= x) {
            return first_leq(node * 2, l, mid, x);
        } else {
            return first_leq(node * 2 + 1, mid + 1, r, x);
        }
    }
};

// -----------------------------
// 大きい場合: 想定解法
// -----------------------------
vector<int> solve_fast(
    int N,
    int K,
    int M,
    const vector<int>& A
) {
    int T;
    vector<int> d;

    if (!build_counts(N, K, M, A, T, d)) return {};

    int L = T - 1;

    // 前半 L 試合は全て ready でない勝者でなければならない。
    // 各 d_i > 0 のチームの締切は最大でも K なので、L > K なら不可能。
    if (L > K) return {};

    vector<long long> deadline(N, BIG);
    vector<long long> cnt_deadline(K + 1, 0);

    for (int i = 0; i < N; i++) {
        if (d[i] == 0) continue;

        if (d[i] > K) return {};

        int D = K - d[i] + 1;
        if (D <= 0 || D > K) return {};

        deadline[i] = D;
        cnt_deadline[D] += d[i];
    }

    // slack[x] = x - 締切 x 以下の残り仕事数
    vector<long long> slack(K + 1, 0);
    long long pref = 0;

    for (int x = 1; x <= K; x++) {
        pref += cnt_deadline[x];
        slack[x] = x - pref;
    }

    RangeMinAddSeg slack_seg(slack);

    if (slack_seg.all_min() < 0) return {};

    vector<long long> label_vals(N);
    for (int i = 0; i < N; i++) {
        label_vals[i] = (d[i] > 0 ? deadline[i] : BIG);
    }

    LabelMinSeg label_seg(label_vals);

    vector<int> ans;

    for (int p = 1; p <= L; p++) {
        // 最初に slack が 0 になる締切 e がある場合、
        // deadline > e のチームを選ぶと詰む。
        long long e = slack_seg.first_zero_from(p);

        if (e == INF64) {
            e = K;
        }

        int idx = label_seg.first_leq(e);

        if (idx == -1) return {};

        int D = (int)deadline[idx];

        if (D < p) return {};

        ans.push_back(idx);

        d[idx]--;

        if (d[idx] == 0) {
            label_seg.update(idx, BIG);
        }

        // 時刻を p から p+1 に進める。
        // 選んだチームの締切 D より前の prefix では、使える枠が1つ減る。
        slack_seg.range_add(p + 1, D - 1, -1);
    }

    ans.push_back(M);

    if (!validate_answer(N, K, M, A, ans)) {
        // バリデーション用コードなので、念のため最終チェック
        return {};
    }

    return ans;
}

// -----------------------------
// main
// -----------------------------
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, K;
    cin >> N >> K;

    int M;
    cin >> M;
    M--;

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

    int T_dummy;
    vector<int> d_dummy;

    if (!build_counts(N, K, M, A, T_dummy, d_dummy)) {
        cout << -1 << '\n';
        return 0;
    }

    int T = T_dummy;

    // 愚直を使う範囲。
    // バリデーション目的なら好みに応じて変更してください。
    const int BRUTE_N_LIMIT = 8;
    const int BRUTE_T_LIMIT = 18;

    vector<int> ans;

    if (N <= BRUTE_N_LIMIT && T <= BRUTE_T_LIMIT) {
        ans = solve_brute(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] + 1;
    }
    cout << '\n';

    return 0;
}