| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 479194 | khoabright | Packing Biscuits (IOI20_biscuits) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define ff first
#define ss second
#define pii pair<int, int>
#define all(x) x.begin(), x.end()
#define rep(i, a, b) for (int i = (int)a; i <= (int)b; ++i)
#define rep1(i, a, b) for (int i = (int)a; i >= (int)b; --i)
#define mp make_pair
#define vii vector<vector<int>>
#define ll long long
int64_t count_tastiness(int64_t x, vector<int64_t> a) {
function<void()> merge = [&]() {
int n = a.size();
rep(i, 0, n - 2) {
if (a[i] <= 2) continue;
a[i + 1] += (a[i] - 1) / 2;
a[i] = 2 - (a[i] % 2);
}
};
merge();
int64_t ans = 1, cur = 0;
// rep(i, 0, a.size() - 1) {
// cout << a[i] << ' ';
// }
//cout << '\n';
rep1(k, 60, 0) {
if (a[k] == 0) {
ans *= (cur + 1);
cur = 0;
//the 0 seperate two segments because none of them is constrained to the other
}
else {
cur = cur * 2 + a[k];
// x2 if for not use a[i] and use 1 * (2^i)
// + a[i] means: if a[i] = 1, there is y = 2^i + 0*(2^(i+1)) + 0*...
//if a[i] = 2, there is a possible value (the max one): 2*(2^i) + a[i+1]*(2^i+1) + ... (?)
// explain (?): if we use 2*(2^i), then we cannot use (a[i+1]-x)*(2^i+1) (for some x>0)
//because we've already use (a[i+1]-x+1)*(2^i+1)
//i.e. 2*(2^i)+(a[i+1]-x)*(2^i+1) = (a[i+1]-x+1)*(2^i+1)
//=> we have to use a[i]*(2^i) for all i => max value.
//(This is the key reason why we iterate i from big to small)
}
}
ans *= (cur + 1);
return ans;
}
// int main() {
// long long x;
// vector<long long> v(61);
// cin >> x;
// rep(i, 0, 4) {
// cin >> v[i];
// }
// cout << count_tastiness(x, v);
// }