#include 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& 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; } // ----------------------------- // 共通: 最終スコアから T, w, 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; 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]; } 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& A, vector& rem, vector& win_so_far, vector& prefix ) { int pos = (int)prefix.size() + 1; // 1-indexed, 最後の M を除いた試合位置 if ((int)prefix.size() == T - 1) { vector 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 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 // ----------------------------- struct RangeMinAddSeg { int n; vector mn, lazy; RangeMinAddSeg() {} RangeMinAddSeg(const vector& 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& 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 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 でない勝者でなければならない。 // 各 d_i > 0 のチームの締切は最大でも 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 {}; 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; 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 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; }