| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1280723 | tschav_ | Festival (IOI25_festival) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
static const int MOD = 1e9+7;
#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;
size_t maxSize = max(a.size(), b.size());
result.reserve(maxSize + 1);
for (size_t 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;
size_t n = a.size();
for (size_t 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 (size_t i = 0; i < a.size(); ++i) {
long long carry = 0;
for (size_t 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){
bigint curr = to_bigint(A);
vector<int> R;
bigint mx = to_bigint(0);
int mxc = -1;
set<int> st;
for(int i = 0; i < P.size();++i) st.insert(i);
vector<bigint> Q(P.size());
for(int i = 0; i < P.size();++ i) {
Q[i] = to_bigint(P[i]);
}
auto it = st.begin();
while(true){
if(it == st.end()) {
if(mxc != -1) {
st.erase(mxc);
R.emplace_back(mxc);
mxc = -1;
curr = mx;
mx = to_bigint(0);
it = st.begin();
continue;
} else break;
}
auto idx = *it;
int ind = compare(curr, Q[idx]);
if(ind == -1) {++it; continue;}
bigint sub = subtract(curr,Q[idx]);
if(T[idx] == 2) {
bigint coeff = to_bigint(2);
sub = multiply(sub, coeff);
}
ind = compare(sub, mx);
if(ind == -1) {++it; continue;}
else if (ind == 0) {
if(mxc == -1 or T[mxc] < T[idx]) {
mx = sub;
mxc = idx;
}
} else {
mx = sub;
mxc = idx;
}
++it;
}
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>{2,1,1,1}, vector<int>{2,1,1,1});
for(auto &i : V) cout << i << " ";
}