| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1280740 | tschav_ | 축제 (IOI25_festival) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define bigint vector<int>
static void normalize(bigint &v) {
while (v.size() > 1 and v.back() == 0) v.pop_back();
if (v.empty()) v.push_back(0);
}
bigint to_bigint(int A) {
string s = to_string(A);
bigint v;
v.reserve(s.size());
for (int i = int(s.size()) - 1; i >= 0; --i) {
v.push_back(s[i] - '0');
}
normalize(v);
return v;
}
bigint add(const bigint &a, const bigint &b) {
bigint result;
int carry = 0;
int maxSize = max(a.size(), b.size());
result.reserve(maxSize + 1);
for (int i = 0; i < maxSize; ++i) {
int digit1 = (i < a.size()) ? a[i] : 0;
int digit2 = (i < b.size()) ? b[i] : 0;
int sum = digit1 + digit2 + carry;
result.push_back(sum % 10);
carry = sum / 10;
}
if (carry) result.push_back(carry);
normalize(result);
return result;
}
bigint subtract(const bigint &a, const bigint &b) {
bigint result;
result.reserve(a.size());
int carry = 0;
int n = a.size();
for (int i = 0; i < n; ++i) {
int digit1 = a[i];
int digit2 = (i < b.size()) ? b[i] : 0;
int diff = digit1 - digit2 - carry;
if (diff < 0) {
diff += 10;
carry = 1;
} else {
carry = 0;
}
result.push_back(diff);
}
normalize(result);
return result;
}
bigint multiply(const bigint &a, const bigint &b) {
bigint result(a.size() + b.size(), 0);
for (int i = 0; i < a.size(); ++i) {
long long carry = 0;
for (int j = 0; j < b.size() or carry; ++j) {
long long cur = result[i + j] + carry + 1ll * a[i] * (j < b.size() ? b[j] : 0);
result[i + j] = int(cur % 10);
carry = cur / 10;
}
}
normalize(result);
return result;
}
void print(const bigint &x) {
for (int i = int(x.size()) - 1; i >= 0; --i) cout << x[i];
}
int compare(const bigint &a, const bigint &b) {
if (a.size() < b.size()) return -1;
if (a.size() > b.size()) return 1;
for (int i = int(a.size()) - 1; i >= 0; --i) {
if (a[i] < b[i]) return -1;
if (a[i] > b[i]) return 1;
}
return 0;
}
vector<int> max_coupons(int A, vector<int> P, vector<int> T){
int sum = accumulate(T.begin(),T.end(),0);
int n = P.size();
if(sum != n){
vector<int> R;
using pii = pair<int,int>;
priority_queue<pii> pq[5];
for(int i = 0; i < n; ++i){
pq[T[i]].push(pii{-P[i], i});
}
vector<bigint> Q(P.size());
for(int i = 0; i < P.size();++ i) {
Q[i] = to_bigint(P[i]);
}
bigint curr = to_bigint(A);
while(R.size() < n){
bigint mx = to_bigint(0);
int mxc = 0;
for(int i = 1; i <= 4; ++i){
if(pq[i].empty()) continue;
int H = pq[i].top().second;
int pb = -pq[i].top().first;
bigint pay = to_bigint(pb);
if(compare(curr,pay) == -1) continue;
bigint coef = to_bigint(T[H]);
bigint G = subtract(curr,pay);
bigint mult = multiply(G, coef);
if(compare(mult,mx) > -1) {
mxc = i;
mx = mult;
}
}
if(mxc == 0) break;
auto [t,ind] = pq[mxc].top();
pq[mxc].pop();
curr = mx;
R.push_back(ind);
}
return R;
}
vector<int> R;
vector<int> idx(n);
iota(idx.begin(),idx.end(),0);
sort(idx.begin(),idx.end(),[&](int i, int j) {
return P[i] < P[j];
});
int cnt = 0;
int curr= A;
for(int i = 0; i < n; ++i){
if(curr >= P[idx[i]]){
++cnt;
R.push_back(idx[i]);
curr -= P[idx[i]];
} else break;
}
return R;
}
int main() {
auto V = max_coupons(4, vector<int>{3,1,1,1}, vector<int>{4,1,1,1});
for(auto &i : V) cout << i << " ";
}