| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1249434 | mondellbit | Souvenirs (IOI25_souvenirs) | C++20 | 0 ms | 0 KiB |
#include "souvenirs.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define ull unsigned long long
#define pb push_back
#define ins insert
#define lb lower_bound
#define ub upper_bound
#define eb emplace_back
#define F first
#define S second
#define T third
#define FOR(i, x, y) for(ll i = x; i <= y; i++)
#define FORJ(i, x, y, j) for(ll i = x; i <= y; i += j)
#define FORD(i, x, y) for(ll i = y; i >= x; --i)
#define REP(i, n) for(ll i = 0; i < n; i++)
#define REPF(i, n) for(ll i = 0; i + 1 < n; i++)
#define N 105
#define INF 100000000000000000
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define accu(a) accumulate(all(a), 0ll)
template<typename T> inline T gcd(T a,T b) { while (b != 0) swap(b, a %= b); return a; }
template<typename T> inline T lcm(T a, T b){ return (a / gcd(a, b)) * b;}
struct payment {
vector<ll> items;
ll price;
};
payment leading[N];
ll price[N];
int cnt_bought[N];
int know_leading;
pair<vector<ll>, ll> add_leading(ll curp) {
auto ret = transaction(curp);
vector<ll> items(all(ret.F));
sort(all(items));
if (leading[items[0]].price == 0) know_leading++;
leading[items[0]] = payment{items, curp - ret.S};
for (ll i : items) cnt_bought[i]++;
return {items, ret.S};
}
void calc_price(int i) {
ll me = leading[i].price;
for (ll j : leading[i].items) if (j != i) me -= price[j];
price[i] = me;
}
void buy_souvenirs(int n, ll P0) {
ll curp = P0 - 1;
REP(i, n) leading[i] = payment{vector<ll>(), 0};
while (true) {
auto ret = add_leading(curp);
curp -= ret.S;
curp = curp / ret.F.size();
if (ret.F.size() == 1) curp--;
if (ret.F[0] == n - 1) break;
}
while (know_leading < n - 1) {
int unknown = n - 1;
while (leading[unknown].price) {
if (!price[unknown]) calc_price(unknown);
unknown--;
}
int known = unknown;
while (leading[known].price == 0) known--;
ll totp = leading[known].price;
int totn = leading[known].items.size();
for (ll j : leading[known].items) {
if (j > unknown) {
if (!price[j]) calc_price(j);
totn--;
totp -= price[j];
}
}
if (totn == 1) totp--;
else totp /= totn;
auto ret = add_leading(totp);
int cnt_unknown = ret.F.size();
ll tot = totp - ret.S;
for (ll i : ret.F) {
if (price[i]) {
tot -= price[i];
cnt_unknown--;
}
}
if (cnt_unknown == 1) {
price[ret.F[0]] = tot;
}
}
FORD(i, 0, n - 1) {
ll me = leading[i].price;
for (ll j : leading[i].items) if (j != i) me -= price[j];
price[i] = me;
while (cnt_bought[i] < i) {
transaction(price[i]);
cnt_bought[i]++;
}
}
}