| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1254698 | fasterthanyou | 축제 (IOI25_festival) | C++20 | 0 ms | 0 KiB |
#include <vector>
#include <algorithm>
#include <cstdint>
#include <utility>
using std::vector;
// Minimal non-negative BigInt (base 1e9) sufficient for this task.
struct BigInt {
static constexpr uint32_t BASE = 1000000000u;
vector<uint32_t> d; // little-endian digits
BigInt() = default;
BigInt(uint64_t v) { assign(v); }
void assign(uint64_t v) {
d.clear();
if (v == 0) return;
while (v > 0) {
d.push_back(static_cast<uint32_t>(v % BASE));
v /= BASE;
}
}
bool is_zero() const { return d.empty(); }
void trim() { while (!d.empty() && d.back() == 0) d.pop_back(); }
int cmp(const BigInt& o) const {
if (d.size() != o.d.size()) return d.size() < o.d.size() ? -1 : 1;
for (int i = static_cast<int>(d.size()) - 1; i >= 0; --i) {
if (d[i] != o.d[i]) return d[i] < o.d[i] ? -1 : 1;
}
return 0;
}
int cmp_small(uint64_t x) const {
if (d.empty()) return x == 0 ? 0 : -1;
if (d.size() >= 3) return 1; // >= BASE^2 > 1e18 > any 64-bit x we will pass here
uint64_t val = (d.size() == 2)
? static_cast<uint64_t>(d[0]) + static_cast<uint64_t>(d[1]) * BASE
: static_cast<uint64_t>(d[0]);
if (val < x) return -1;
if (val > x) return 1;
return 0;
}
void add(const BigInt& y) {
size_t n = std::max(d.size(), y.d.size());
d.resize(n, 0);
uint64_t carry = 0;
for (size_t i = 0; i < n; ++i) {
uint64_t sum = carry + d[i] + (i < y.d.size() ? y.d[i] : 0u);
d[i] = static_cast<uint32_t>(sum % BASE);
carry = sum / BASE;
}
if (carry) d.push_back(static_cast<uint32_t>(carry));
}
void add_small(uint64_t x) {
uint64_t carry = x;
size_t i = 0;
while (carry > 0) {
if (i == d.size()) d.push_back(0);
uint64_t sum = static_cast<uint64_t>(d[i]) + carry;
d[i] = static_cast<uint32_t>(sum % BASE);
carry = sum / BASE;
++i;
}
}
// assume this >= y
void sub(const BigInt& y) {
uint64_t borrow = 0;
for (size_t i = 0; i < d.size(); ++i) {
uint64_t yi = (i < y.d.size() ? y.d[i] : 0u);
uint64_t cur = static_cast<uint64_t>(d[i]);
uint64_t sub_v = yi + borrow;
if (cur >= sub_v) {
d[i] = static_cast<uint32_t>(cur - sub_v);
borrow = 0;
} else {
d[i] = static_cast<uint32_t>(cur + BASE - sub_v);
borrow = 1;
}
}
trim();
}
// assume this >= x
void sub_small(uint64_t x) {
uint64_t carry = x;
size_t i = 0;
while (carry > 0) {
uint64_t cur = (i < d.size() ? d[i] : 0u);
uint64_t xi = carry % BASE;
carry /= BASE;
if (cur >= xi) {
d[i] = static_cast<uint32_t>(cur - xi);
} else {
d[i] = static_cast<uint32_t>(cur + BASE - xi);
carry += 1; // borrow
}
++i;
}
trim();
}
void mul_small(uint32_t m) {
if (is_zero() || m == 1) return;
if (m == 0) { d.clear(); return; }
uint64_t carry = 0;
for (size_t i = 0; i < d.size(); ++i) {
uint64_t prod = static_cast<uint64_t>(d[i]) * m + carry;
d[i] = static_cast<uint32_t>(prod % BASE);
carry = prod / BASE;
}
if (carry) d.push_back(static_cast<uint32_t>(carry));
}
};
static inline bool operator< (const BigInt& a, const BigInt& b) { return a.cmp(b) < 0; }
static inline bool operator<=(const BigInt& a, const BigInt& b) { return a.cmp(b) <= 0; }
static inline bool operator> (const BigInt& a, const BigInt& b) { return a.cmp(b) > 0; }
static inline bool operator>=(const BigInt& a, const BigInt& b) { return a.cmp(b) >= 0; }
static inline bool operator==(const BigInt& a, const BigInt& b) { return a.cmp(b) == 0; }
static inline bool operator!=(const BigInt& a, const BigInt& b) { return a.cmp(b) != 0; }
vector<int> max_coupons(int A, const vector<int>& P, const vector<int>& T) {
struct Item {
int idx;
int price;
int mult; // T >= 2
int64_t k_num; // P * T
int k_den; // T - 1
};
const int n = static_cast<int>(P.size());
vector<Item> boosters;
vector<std::pair<int,int>> plains; // (price, idx) for T==1
boosters.reserve(n);
plains.reserve(n);
for (int i = 0; i < n; ++i) {
if (T[i] == 1) {
plains.emplace_back(P[i], i);
} else {
boosters.push_back(Item{
i,
P[i],
T[i],
static_cast<int64_t>(P[i]) * static_cast<int64_t>(T[i]),
T[i] - 1
});
}
}
// Comparator for K = P*T/(T-1), exact via cross-multiplication.
auto keyLessItem = [&](const Item& a, const Item& b) -> bool {
int64_t left = a.k_num * b.k_den;
int64_t right = b.k_num * a.k_den;
if (left != right) return left < right;
if (a.price != b.price) return a.price < b.price;
return a.idx < b.idx;
};
// Coordinate-compress booster prices
vector<int> uniquePrices;
uniquePrices.reserve(boosters.size());
for (auto &it : boosters) uniquePrices.push_back(it.price);
std::sort(uniquePrices.begin(), uniquePrices.end());
uniquePrices.erase(std::unique(uniquePrices.begin(), uniquePrices.end()), uniquePrices.end());
const int M = static_cast<int>(uniquePrices.size());
auto priceToCoord = [&](int price) -> int {
return static_cast<int>(std::lower_bound(uniquePrices.begin(), uniquePrices.end(), price) - uniquePrices.begin());
};
// Group boosters by price coordinate and sort each group by K
vector<vector<int>> groups(M); // holds indices into boosters
for (int i = 0; i < static_cast<int>(boosters.size()); ++i) {
int d = priceToCoord(boosters[i].price);
groups[d].push_back(i);
}
for (int d = 0; d < M; ++d) {
std::sort(groups[d].begin(), groups[d].end(), [&](int i, int j){
return keyLessItem(boosters[i], boosters[j]);
});
}
vector<int> ptr(M, 0); // next candidate in each price group
// Segment tree over price coords, each node stores best item index by K
struct SegTree {
int n;
vector<int> t; // index into boosters, or -1
const vector<vector<int>>* groups;
vector<int>* ptr;
const vector<Item>* items;
SegTree(int n_, const vector<vector<int>>* groups_, vector<int>* ptr_, const vector<Item>* items_)
: n(n_), t(n_ ? 4*n_ : 0, -1), groups(groups_), ptr(ptr_), items(items_) {}
int pick(int a, int b) const {
if (a == -1) return b;
if (b == -1) return a;
const Item& ia = (*items)[a];
const Item& ib = (*items)[b];
int64_t left = ia.k_num * ib.k_den;
int64_t right = ib.k_num * ia.k_den;
if (left != right) return (left < right) ? a : b;
if (ia.price != ib.price) return (ia.price < ib.price) ? a : b;
return (ia.idx < ib.idx) ? a : b;
}
void build(int v, int tl, int tr) {
if (tl == tr) {
int d = tl;
int candidate = -1;
if ((*ptr)[d] < static_cast<int>((*groups)[d].size())) {
candidate = (*groups)[d][(*ptr)[d]];
}
t[v] = candidate;
} else {
int tm = (tl + tr) >> 1;
build(v<<1, tl, tm);
build(v<<1|1, tm+1, tr);
t[v] = pick(t[v<<1], t[v<<1|1]);
}
}
void build() {
if (n > 0) build(1, 0, n-1);
}
void update(int v, int tl, int tr, int pos) {
if (tl == tr) {
int d = tl;
int candidate = -1;
if ((*ptr)[d] < static_cast<int>((*groups)[d].size())) {
candidate = (*groups)[d][(*ptr)[d]];
}
t[v] = candidate;
} else {
int tm = (tl + tr) >> 1;
if (pos <= tm) update(v<<1, tl, tm, pos);
else update(v<<1|1, tm+1, tr, pos);
t[v] = pick(t[v<<1], t[v<<1|1]);
}
}
void update(int pos) {
if (n > 0) update(1, 0, n-1, pos);
}
int query(int v, int tl, int tr, int l, int r) const {
if (l > r) return -1;
if (l == tl && r == tr) return t[v];
int tm = (tl + tr) >> 1;
int left = query(v<<1, tl, tm, l, std::min(r, tm));
int right = query(v<<1|1, tm+1, tr, std::max(l, tm+1), r);
return pick(left, right);
}
int query(int l, int r) const {
if (n == 0 || l > r) return -1;
return query(1, 0, n-1, l, r);
}
};
SegTree st(M, &groups, &ptr, &boosters);
st.build();
auto lastAffordableCoord = [&](const BigInt& tokens) -> int {
int lo = 0, hi = M; // find first price > tokens, then step back
while (lo < hi) {
int mid = (lo + hi) >> 1;
if (tokens.cmp_small(static_cast<uint64_t>(uniquePrices[mid])) >= 0) {
lo = mid + 1;
} else {
hi = mid;
}
}
return lo - 1;
};
// Build greedy booster sequence
BigInt tokens(static_cast<uint64_t>(A));
vector<BigInt> tokens_after; // tokens after buying k boosters
tokens_after.push_back(tokens);
vector<int> booster_seq;
while (true) {
int r = lastAffordableCoord(tokens);
if (r < 0) break;
int id = st.query(0, r);
if (id == -1) break;
const Item& it = boosters[id];
tokens.sub_small(static_cast<uint64_t>(it.price));
tokens.mul_small(static_cast<uint32_t>(it.mult));
booster_seq.push_back(it.idx);
tokens_after.push_back(tokens);
int d = priceToCoord(it.price);
++ptr[d];
st.update(d);
}
// Sort T=1 coupons by price asc, then idx
std::sort(plains.begin(), plains.end());
int M1 = static_cast<int>(plains.size());
// Prefix sums of T=1 prices
vector<BigInt> pref;
pref.reserve(M1 + 1);
pref.emplace_back(0u);
for (auto &q : plains) {
BigInt next = pref.back();
next.add_small(static_cast<uint64_t>(q.first));
pref.push_back(std::move(next));
}
auto max_plains_with = [&](const BigInt& x) -> int {
// largest m with pref[m] <= x
int lo = 0, hi = M1;
while (lo < hi) {
int mid = (lo + hi + 1) >> 1;
if (pref[mid] <= x) lo = mid;
else hi = mid - 1;
}
return lo;
};
// Choose best prefix of boosters (to maximize boosters + T=1)
int best_total = -1;
int best_k = 0;
for (int k = 0; k < static_cast<int>(tokens_after.size()); ++k) {
int m = max_plains_with(tokens_after[k]);
int total = k + m;
if (total > best_total) {
best_total = total;
best_k = k;
}
}
// Build final order: first best_k boosters in greedy order, then as many T=1 as possible
vector<int> order;
order.reserve(best_total > 0 ? best_total : 0);
for (int i = 0; i < best_k; ++i) order.push_back(booster_seq[i]);
BigInt tok = tokens_after[best_k];
for (int i = 0; i < M1; ++i) {
if (tok.cmp_small(static_cast<uint64_t>(plains[i].first)) >= 0) {
tok.sub_small(static_cast<uint64_t>(plains[i].first));
order.push_back(plains[i].second);
} else {
break;
}
}
return order;
}