#line 2 "/Users/baluteshih/coding/cplibrary/default_code.hpp" #line 2 "/Users/baluteshih/coding/cplibrary/assumption.hpp" #include #include #line 4 "/Users/baluteshih/coding/cplibrary/default_code.hpp" using namespace std; typedef long long ll; typedef pair pii; typedef pair pll; #define X first #define Y second #define SZ(a) ((int)a.size()) #define ALL(v) v.begin(), v.end() template concept PrintableContainer = requires(T& a) { a.begin(); a.end(); } && !std::convertible_to, std::string_view>; template ostream& operator<<(ostream& os, const pair &a); template std::ostream& operator<<(std::ostream& os, const T& a); template ostream& operator<<(ostream& os, const pair &a) { os << "(" << a.first << ", " << a.second << ")"; return os; } template std::ostream& operator<<(std::ostream& os, const T& a) { os << "[ "; bool first = true; for (const auto& item : a) { if (!first) os << ", "; os << item; first = false; } return os << " ]"; } #ifdef bbq #include #define safe cerr<<__PRETTY_FUNCTION__<<" line "<<__LINE__<<" safe\n" #define sepline sepline_() #define debug(a...) debug_(#a, a) #define orange(a...) orange_(#a, a) void debug_(auto s, auto ...a) { cerr << "\e[1;32m(" << s << ") = ("; int f = 0; (..., (cerr << (f++ ? ", " : "") << a)); cerr << ")\e[0m\n"; } void orange_(auto s, auto L, auto R) { cerr << "\e[1;33m[ " << s << " ] = [ "; using namespace experimental; copy(L, R, make_ostream_joiner(cerr, ", ")); cerr << " ]\e[0m\n"; } void sepline_(int length = 50) { cerr << "\e[1;35m"; cerr << string(length, '='); cerr << "\e[0m\n"; } #else #define safe ((void)0) #define sepline safe #define debug(...) safe #define orange(...) safe #endif void chmax(auto &x, auto val) { x = max(x, val); } void chmin(auto &x, auto val) { x = min(x, val); } auto floor_div(auto a, auto b) { return a / b - (a % b && (a < 0) ^ (b < 0)); } auto ceil_div(auto a, auto b) { return a / b + (a % b && (a < 0) ^ (b > 0)); } string bitstring(auto x, int width = -1) { string res; while (x) res.push_back((x & 1) + '0'), x >>= 1; if (res.empty()) res = "0"; if (width != -1) res.resize(width, '0'); ranges::reverse(res); return res; } vector count_array(const auto &container, int sz = -1) { if (sz == -1) sz = *ranges::max_element(container) + 1; vector res(sz); for (auto x : container) ++res[x]; return res; } #line 2 "E.cpp" #line 2 "/Users/baluteshih/coding/cplibrary/DataStructure/SegmentTree.hpp" template class SegmentTree { static constexpr bool hasTag = !std::is_same_v; static_assert(pushdown || hasTag, "Lazy tag must exist when pushdown is false"); int n; std::vector seg; struct Empty {}; [[no_unique_address]] std::conditional_t, Empty> lazy; Value get_val(int rt) { if constexpr (pushdown) return seg[rt]; else return seg[rt] + lazy[rt]; } void up(int rt) { seg[rt] = get_val(rt << 1) + get_val(rt << 1 | 1); } void give_tag(int rt, auto tag) requires (hasTag) { if constexpr (pushdown) seg[rt] = seg[rt] + tag; lazy[rt] = lazy[rt] + tag; } void down(int rt) requires (hasTag && pushdown) { give_tag(rt << 1, lazy[rt]); give_tag(rt << 1 | 1, lazy[rt]); lazy[rt] = Tag(); } void initialize(int l, int r, int rt, const std::vector &data) { if (r - l == 1) return seg[rt] = data[l], void(); int mid = (l + r) >> 1; initialize(l, mid, rt << 1, data); initialize(mid, r, rt << 1 | 1, data); up(rt); } Value range_prod(int L, int R, int l, int r, int rt) { if (L <= l && R >= r) return get_val(rt); if constexpr (hasTag && pushdown) down(rt); int mid = (l + r) >> 1; if constexpr (pushdown) { if (R <= mid) return range_prod(L, R, l, mid, rt << 1); if (L >= mid) return range_prod(L, R, mid, r, rt << 1 | 1); return range_prod(L, R, l, mid, rt << 1) + range_prod(L, R, mid, r, rt << 1 | 1); } else { if (R <= mid) return range_prod(L, R, l, mid, rt << 1) + lazy[rt]; if (L >= mid) return range_prod(L, R, mid, r, rt << 1 | 1) + lazy[rt]; return range_prod(L, R, l, mid, rt << 1) + range_prod(L, R, mid, r, rt << 1 | 1) + lazy[rt]; } } void modify(int x, int l, int r, int rt, const Value &v) { if (r - l == 1) return seg[rt] = v, void(); if constexpr (hasTag && pushdown) down(rt); int mid = (l + r) >> 1; if constexpr (pushdown) { if (x < mid) modify(x, l, mid, rt << 1, v); else modify(x, mid, r, rt << 1 | 1, v); } else { if (x < mid) modify(x, l, mid, rt << 1, v - lazy[rt]); else modify(x, mid, r, rt << 1 | 1, v - lazy[rt]); } up(rt); } void transform(int x, int l, int r, int rt, const auto &func) { if (r - l == 1) return func(seg[rt]), void(); if constexpr (hasTag && pushdown) down(rt); int mid = (l + r) >> 1; if (x < mid) transform(x, l, mid, rt << 1, func); else transform(x, mid, r, rt << 1 | 1, func); up(rt); } void range_transform(int L, int R, int l, int r, int rt, const auto &tag) requires (hasTag) { if (L <= l && R >= r) return give_tag(rt, tag); if constexpr (pushdown) down(rt); int mid = (l + r) >> 1; if (L < mid) range_transform(L, R, l, mid, rt << 1, tag); if (R > mid) range_transform(L, R, mid, r, rt << 1 | 1, tag); up(rt); } void range_transform_beats(int L, int R, int l, int r, int rt, const auto &tag, const auto &tag_condition, auto... tag_sum) requires (hasTag) { if (L <= l && R >= r && tag_condition([&]{ if constexpr(pushdown) return seg[rt]; else return get_val(rt) + (..., tag_sum); }())) return give_tag(rt, tag); assert(r - l > 1); if constexpr (pushdown) down(rt); else ((tag_sum = tag_sum + lazy[rt]), ...); int mid = (l + r) >> 1; if (L < mid) range_transform_beats(L, R, l, mid, rt << 1, tag, tag_condition, tag_sum...); if (R > mid) range_transform_beats(L, R, mid, r, rt << 1 | 1, tag, tag_condition, tag_sum...); up(rt); } int range_left_search(int L, int R, int l, int r, int rt, const auto &condition, auto... tag_sum) { if (r - l == 1) { if (!condition([&]{ if constexpr(pushdown) return seg[rt]; else return get_val(rt) + (..., tag_sum); }())) return R; return l; } int mid = (l + r) >> 1; if constexpr (hasTag && pushdown) down(rt); if constexpr (!pushdown) ((tag_sum = tag_sum + lazy[rt]), ...); if (L <= l && R >= r) { if (condition([&]{ if constexpr(pushdown) return seg[rt << 1]; else return get_val(rt << 1) + (..., tag_sum); }())) return range_left_search(L, R, l, mid, rt << 1, condition, tag_sum...); return range_left_search(L, R, mid, r, rt << 1 | 1, condition, tag_sum...); } int left = R; if (L < mid) left = range_left_search(L, R, l, mid, rt << 1, condition, tag_sum...); if (left == R) { if (R > mid) return range_left_search(L, R, mid, r, rt << 1 | 1, condition, tag_sum...); return R; } return left; } int range_right_search(int L, int R, int l, int r, int rt, const auto &condition, auto... tag_sum) { if (r - l == 1) { if (!condition([&]{ if constexpr(pushdown) return seg[rt]; else return get_val(rt) + (..., tag_sum); }())) return L - 1; return l; } int mid = (l + r) >> 1; if constexpr (hasTag && pushdown) down(rt); if constexpr (!pushdown) ((tag_sum = tag_sum + lazy[rt]), ...); if (L <= l && R >= r) { if (condition([&]{ if constexpr(pushdown) return seg[rt << 1 | 1]; else return get_val(rt << 1 | 1) + (..., tag_sum); }())) return range_right_search(L, R, mid, r, rt << 1 | 1, condition, tag_sum...); return range_right_search(L, R, l, mid, rt << 1, condition, tag_sum...); } int right = L - 1; if (R > mid) right = range_right_search(L, R, mid, r, rt << 1 | 1, condition, tag_sum...); if (right == L - 1) { if (L < mid) return range_right_search(L, R, l, mid, rt << 1, condition, tag_sum...); return L - 1; } return right; } Value get(int x, int l, int r, int rt) { [[no_unique_address]] std::conditional_t tag; while (r - l > 1) { if constexpr (hasTag && pushdown) down(rt); if constexpr (!pushdown) tag = tag + lazy[rt]; int mid = (l + r) >> 1; if (x < mid) r = mid, rt = rt << 1; else l = mid, rt = rt << 1 | 1; } if constexpr (pushdown) return seg[rt]; else return get_val(rt) + tag; } void printnode(int l, int r, int rt) { std::cerr << "[" << l << ", " << r << "): "; if constexpr (hasTag) std::cerr << "val = " << seg[rt] << ", tag = " << lazy[rt]; else std::cerr << seg[rt]; std::cerr << "\n"; } void printinfo(int L, int R, int l, int r, int rt) { printnode(l, r, rt); if (L <= l && R >= r) return; int mid = (l + r) >> 1; if (L < mid) printinfo(L, R, l, mid, rt << 1); if (R > mid) printinfo(L, R, mid, r, rt << 1 | 1); } void printall(int l, int r, int rt) { printnode(l, r, rt); if (r - l == 1) return; int mid = (l + r) >> 1; printall(l, mid, rt << 1); printall(mid, r, rt << 1 | 1); } public: SegmentTree(const std::vector &data): n(data.size()), seg(n << 2) { if constexpr (hasTag) lazy.resize(n << 2); initialize(0, n, 1, data); } SegmentTree(int size): SegmentTree(vector(size)) {} Value get(int x) { assert(0 <= x && x < n); return get(x, 0, n, 1); } Value range_prod(int l, int r) { assert(0 <= l && r <= n); assert(l <= r); if (l == r) return Value(); return range_prod(l, r, 0, n, 1); } void modify(int x, const Value &v) { assert(0 <= x && x < n); modify(x, 0, n, 1, v); } void transform(int x, const auto &func) { assert(0 <= x && x < n); transform(x, 0, n, 1, func); } void range_transform(int l, int r, const auto &tag) requires (hasTag) { assert(0 <= l && r <= n); assert(l <= r); if (l < r) range_transform(l, r, 0, n, 1, tag); } void range_transform_beats(int l, int r, const auto &tag, const auto &tag_condition) requires (hasTag) { assert(0 <= l && r <= n); assert(l <= r); if (l < r) range_transform_beats(l, r, 0, n, 1, tag, tag_condition); } int range_left_search(const auto &condition, int l = -1, int r = -1) { if (l == -1 && r == -1) l = 0, r = n; assert(0 <= l && r <= n); assert(l <= r); if (l == r) return r; return range_left_search(l, r, 0, n, 1, condition); } int range_right_search(const auto &condition, int l = -1, int r = -1) { if (l == -1 && r == -1) l = -1, r = n - 1; ++l, ++r; assert(0 <= l && r <= n); assert(l <= r); if (l == r) return l - 1; return range_right_search(l, r, 0, n, 1, condition); } void printinfo(int l, int r) { assert(0 <= l && r <= n); assert(l <= r); std::cerr << "\e[1;33mInfo [" << l << ", " << r << "):\n"; if (l < r) printinfo(l, r, 0, n, 1); std::cerr << "\e[0m\n"; } void printall() { std::cerr << "\e[1;33mInfo all:\n"; printall(0, n, 1); std::cerr << "\e[0m\n"; } }; #line 4 "E.cpp" int main() { ios::sync_with_stdio(0), cin.tie(0); int n, k, m; cin >> n >> k >> m, --m; vector arr(n); for (int &i : arr) cin >> i; if (accumulate(ALL(arr), 0LL) % (n + 1) != 0) return cout << "-1\n", 0; if (arr[m] <= k + 1) return cout << "-1\n", 0; int mx = 0; for (int i = 0; i < n; ++i) if (i != m) chmax(mx, arr[i]); arr[m] -= 1; for (int i = 0; i < n; ++i) --arr[i]; int race = accumulate(ALL(arr), 0LL) / (n + 1); vector ans, win(n), ord(n); for (int i = 0; i < n; ++i) { if (arr[i] < race) return cout << "-1\n", 0; win[i] = arr[i] - race; } iota(ALL(ord), 0); ranges::sort(ord, [&](int a, int b) { return arr[a] > arr[b]; }); ans.resize(race); priority_queue pq; for (int i = race - 1, j = 0; i >= 0; --i) { while (j < n && i + win[ord[j]] - 1 < k) { if (win[ord[j]] > 0) pq.push(ord[j]); ++j; } if (pq.empty()) return cout << "-1\n", 0; ans[i] = pq.top(), pq.pop(); if (--win[ans[i]] > 0) pq.push(ans[i]); } ans.push_back(m); cout << SZ(ans) << "\n"; for (int i = 0; i < SZ(ans); ++i) cout << ans[i] + 1 << " \n"[i + 1 == SZ(ans)]; }