#include 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& A, const vector& ans ) { if (ans.empty()) return false; if (ans.back() != M) return false; vector 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& A, const vector& ans ) { if (ans.empty()) return false; if (ans.back() != M) return false; int T = (int)ans.size(); vector 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& A, int& T, vector& 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 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& A, vector& rem, vector& win_so_far, vector& prefix ) { int pos = (int)prefix.size() + 1; // 前半における試合位置、1-indexed if ((int)prefix.size() == T - 1) { vector 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 solve_brute( int N, int K, int M, const vector& A ) { int T; vector d; if (!build_counts(N, K, M, A, T, d)) return {}; vector rem = d; vector win_so_far(N, 0); vector 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 mn, lazy; RangeMinAddSeg() {} // a は 1-indexed RangeMinAddSeg(const vector& 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& 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 mn; LabelMinSeg() {} LabelMinSeg(const vector& 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& 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 solve_fast( int N, int K, int M, const vector& A ) { int T; vector 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 deadline(N, BIG); vector 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 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 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 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 A(N); for (int i = 0; i < N; i++) cin >> A[i]; int T_dummy; vector 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 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; }