結果
| 問題 | No.3588 Already Ready |
| コンテスト | |
| ユーザー |
 baluteshih
|
| 提出日時 | 2026-07-11 14:48:33 |
| 言語 | C++23(gnu拡張gcc16) (gcc 16.1.0 + boost 1.90.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 13,767 bytes |
| 記録 | |
| コンパイル時間 | 4,849 ms |
| コンパイル使用メモリ | 367,776 KB |
| 実行使用メモリ | 7,988 KB |
| 最終ジャッジ日時 | 2026-07-11 14:48:42 |
| 合計ジャッジ時間 | 8,282 ms |
|
ジャッジサーバーID （参考情報） |
judge3_0 / judge1_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 47 WA * 22 |
ソースコード
#line 2 "/Users/baluteshih/coding/cplibrary/default_code.hpp"
#line 2 "/Users/baluteshih/coding/cplibrary/assumption.hpp"
#include <cassert>
#include <bits/stdc++.h>
#line 4 "/Users/baluteshih/coding/cplibrary/default_code.hpp"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define SZ(a) ((int)a.size())
#define ALL(v) v.begin(), v.end()
template <typename T>
concept PrintableContainer = requires(T& a) {
a.begin();
a.end();
} && !std::convertible_to<std::remove_cvref_t<T>, std::string_view>;
template<class A, class B>
ostream& operator<<(ostream& os, const pair<A, B> &a);
template <PrintableContainer T>
std::ostream& operator<<(std::ostream& os, const T& a);
template<class A, class B>
ostream& operator<<(ostream& os, const pair<A, B> &a) {
os << "(" << a.first << ", " << a.second << ")";
return os;
}
template <PrintableContainer T>
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 <experimental/iterator>
#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<int> count_array(const auto &container, int sz = -1) {
if (sz == -1) sz = *ranges::max_element(container) + 1;
vector<int> res(sz);
for (auto x : container) ++res[x];
return res;
}
#line 2 "E.cpp"
#line 2 "/Users/baluteshih/coding/cplibrary/DataStructure/SegmentTree.hpp"
template<typename Value = int, typename Tag = void, bool pushdown = true>
class SegmentTree {
static constexpr bool hasTag = !std::is_same_v<Tag, void>;
static_assert(pushdown || hasTag, "Lazy tag must exist when pushdown is false");
int n;
std::vector<Value> seg;
struct Empty {};
[[no_unique_address]] std::conditional_t<hasTag, std::vector<Tag>, 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<Value> &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<!pushdown, Tag, Empty> 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<Value> &data): n(data.size()), seg(n << 2) {
if constexpr (hasTag) lazy.resize(n << 2);
initialize(0, n, 1, data);
}
SegmentTree(int size): SegmentTree(vector<Value>(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<int> 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<int> 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<int> 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)];
}