# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1252268 | Jasonwei | Souvenirs (IOI25_souvenirs) | C++20 | 0 ms | 0 KiB |
/*
-A2 --indent=tab=4 --indent-classes --indent-switches --indent-namespaces --indent-preprocessor -xg -p -xd -H -xj -xe
read all problems
do first-eye problems
read rev order
uhhh dont fail impl
*/
#include <bits/stdc++.h>
#define ll long long
#define double long double
#define re(a, b, c, d) for (auto a = b; a <= c; a += d)
#define de(a, b, c, d) for (auto a = b; a >= c; a -= d)
#define ms(a, b) memset(a, b, sizeof (a))
#define imax INT_MAX
#define imin INT_MIN
#define wh(a) while (a --)
#define PII pair <int, int>
#define F first
#define S second
#define pb push_back
#define eb emplace_back
#include "souvenirs.h"
template <typename T> bool chkmin (T &a, T b) {
return (b < a) ? a = b, 1 : 0;
}
template <typename T> bool chkmax (T &a, T b) {
return (b > a) ? a = b, 1 : 0;
}
using namespace std;
const int _N = 105;
int T, a[_N], n;
ll val[_N];
void solve (ll cur) {
auto [t, w] = transaction (cur);
for (auto x : t) c[x] ++;
while (val[t.back ()]) w += val[t.back ()], t.pop_back ();
int j = 0;
while (j + 1 < t.size() && t[j + 1] == t[j] + 1) j ++;
while (t.size() > 1) {
int x = t.size();
if (x - 1 <= j) solve ((cur - w) / x);
else solve ((cur - w) / (j + 2));
while (val[t.back ()]) w += val[t.back ()], t.pop_back ();
}
val[t[0]] = cur - w;
if (t[0] < n && ! val[t[0] + 1]) solve (val[t[0]] - 1);
return ;
}
void buy_souvenirs (int N, ll P0) {
n = N - 1;
solve (P0 - 1);
re (i, 1, n, 1) while (c[i] < i) transaction (val[i]), c[i] ++;
}