結果

問題 No.3588 Already Ready
コンテスト
ユーザー marc2825
提出日時 2026-05-30 09:39:09
言語 C++17
(gcc 15.2.0 + boost 1.90.0)
コンパイル:
g++-15 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 112 ms / 3,000 ms
コード長 12,862 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,654 ms
コンパイル使用メモリ 230,624 KB
実行使用メモリ 32,148 KB
最終ジャッジ日時 2026-07-10 20:58:38
合計ジャッジ時間 5,355 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 69
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

using ll = long long;

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

// ============================================================
// O(NT) の愚直検証: 小さいケース用
// ============================================================
bool validate_answer_slow(
    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;
}

// ============================================================
// O(N+T) の高速検証: 大きいケース用
// ============================================================
bool validate_answer_fast(
    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;

    int T = (int)ans.size();
    vector<int> win(N, 0);

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

        bool is_last = (t + 1 == T);

        // t は 0-indexed。
        // 試合開始直前には、全チームが共通で t 点を得ている。
        // winner はさらに過去の勝利回数 win[winner] 点を得ている。
        int score_before = t + win[winner];

        if (score_before >= K) {
            if (!is_last) return false;
        } else {
            if (is_last) return false;
        }

        win[winner]++;
    }

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

    return true;
}

// ============================================================
// 最終スコアから T と、最後の M 勝利を除いた勝利回数 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;

    // 1試合ごとに合計 N+1 点増える
    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];
    }

    // 勝者は各試合ちょうど1チームなので、勝利回数合計は T
    if (sw != T) return false;

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

    // 最後の試合開始直前に M が ready である必要がある。
    // 最終試合で M は +2 されるので、開始直前スコアは A[M]-2。
    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

    if ((int)prefix.size() == T - 1) {
        vector<int> ans = prefix;
        ans.push_back(M);

        if (validate_answer_slow(N, K, M, A, ans)) {
            prefix = ans;
            return true;
        }

        return false;
    }

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

        // この試合開始直前のチーム i のスコア
        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
// slack[x] の管理用
// ============================================================
struct RangeMinAddSeg {
    int n;
    vector<long long> mn, lazy;

    RangeMinAddSeg() {}

    // a は 1-indexed
    RangeMinAddSeg(const vector<long long>& a) {
        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];
    }

    // ql 以降で slack[x] == 0 となる最小 x を返す。
    // なければ n+1 を返す。
    int first_zero_from(int ql) {
        if (ql > n) return n + 1;
        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 n + 1;

        if (l == r) return l;

        push(node);

        int mid = (l + r) / 2;

        int left = first_zero_from(node * 2, l, mid, ql);
        if (left != n + 1) 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 であってはいけない。
    // 締切は最大でも 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 {};

        // d[i] 回勝つチームの最後の勝利位置を p とすると、
        // 開始直前スコアは (p-1)+(d[i]-1)。
        // ready でないためには (p-1)+(d[i]-1) < K、
        // つまり p <= K-d[i]+1。
        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;
    ans.reserve(T);

    for (int p = 1; p <= L; p++) {
        // 現在時刻 p において、最初に slack[x] == 0 になる x を探す。
        // そこが存在するなら、deadline > x のチームを今選ぶと詰む。
        int e = slack_seg.first_zero_from(p);

        if (e == K + 1) {
            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 に進める。
        //
        // 現在 slack[x] = x-(p-1)-C(x)
        // 次は slack'[x] = x-p-C'(x)
        //
        // 選んだ仕事の締切を D とすると、
        // C'(x)=C(x)       for x < D
        // C'(x)=C(x)-1     for x >= D
        //
        // よって p < x < D の slack だけ -1 される。
        slack_seg.range_add(p + 1, D - 1, -1);
    }

    ans.push_back(M);

    // バリデーション用コードなので高速検証を残す。
    // 提出用なら消してもよい。
    if (!validate_answer_fast(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;
}
0