Submission #1269639

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269639		brendonw	Souvenirs (IOI25_souvenirs)	C++20	100 / 100	12 ms	420 KiB

souvenirs

#include "souvenirs.h"
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

void buy_souvenirs(int n, ll p0) {
	vector<ll> prices(n, -1);
	prices[0] = p0;
	vector<ll> cnt(n);

	// transaction on nxt
	vector<pair<vector<ll>, ll>> cur;
	map<ll, pair<vector<ll>, ll>> cache;
	auto get = [&](ll cost) {
		if (cache.count(cost) == 1) {
			return cache[cost];
		}
		auto [vals, over] = transaction(cost);
		for (auto &val: vals) {
			cnt[val]++;
		}
		return cache[cost] = pair{vector<ll>(vals.begin(), vals.end()), over};
	};
	vector<bool> used(n);
	while (count(prices.begin(), prices.end(), -1) != 0) {
		auto update = [&](vector<ll> vals, ll sum) -> pair<vector<ll>, ll> {
			vector<ll> new_vals;
			for (auto &val: vals) {
				if (prices[val] == -1) {
					new_vals.push_back(val);
				} else {
					sum -= prices[val];
				}
			}
			return {new_vals, sum};
		};
		auto update_cur = [&]() {
			vector<pair<vector<ll>, ll>> new_cur;
			for (auto [vals, sum]: cur) {
				tie(vals, sum) = update(vals, sum);
				if (!vals.empty()) {
					new_cur.push_back({vals, sum});
				}
			}
			cur = new_cur;
		};
		auto clear = [&]() {
			while (true) {
				update_cur();
				bool changed = false;
				for (auto &[vals, sum]: cur) {
					if (vals.size() == 1) {
						prices[vals[0]] = sum;
						changed = true;
					}
				}
				if (!changed) {
					break;
				}
			}
		};
		bool started = false;

		while (!cur.empty() || !started) {
			started = true;
			ll cost = 0;
			auto next = [&](ll i) -> ll {
				for (; i < n; ++i) {
					if (prices[i] == -1) {
						return prices[i - 1] - 1;
					}
				}
				return -1;
			};
			if (cur.empty()) {
				cost = next(0);
			} else {
				std::sort(cur.begin(), cur.end(), [](auto a, auto b) {
					return make_pair(a.first.back(), a.first.front()) > make_pair(b.first.back(), b.first.front());
				});
//				for (int i = 0; i < cur.size(); ++i) {
//
//					cout << "{ ";
//					for (auto &val: cur[i].first) {
//						cout << val << " ";
//					}
//					cout << "}" << " " << cur[i].second << '\n';
//
//				}
//				cout << "-------------------------" << '\n';
				cost = cur.front().second / cur.front().first.size();
			}
//			cost = next();
			while (count(prices.begin(), prices.end(), -1) != 0) {
//				cout << cost << endl;
//				cout << cnt[4] << endl;
				auto [vals, over] = get(cost);
//				for (auto &val: vals) {
//					cnt[val]++;
//				}
				ll old = vals[0];
				ll sum = cost - over;
				tie(vals, sum) = update(vals, sum);
				cur.push_back({vals, sum});
				if (vals.size() == 0) {
					cost = next(old);
					if (cost == -1) {
						break;
					}
				} else if (vals.size() == 1) {
					prices[vals[0]] = sum;
					clear();
					cost = next(vals[0]);
					if (cost == -1) {
						break;
					}
				} else {
					cost = sum / vals.size();
				}
			}
			clear();
		}

	}
	for (int i = 0; i < n; ++i) {
		while (cnt[i] < i) {
			assert(transaction(prices[i]).first.size() == 1);
			cnt[i]++;
		}
//		assert(cnt[i] == i);
	}

	return;
}

• Subtask 0: 0 / 0
• Subtask 1: 4 / 4
• Subtask 2: 3 / 3
• Subtask 3: 14 / 14
• Subtask 4: 18 / 18
• Subtask 5: 28 / 28
• Subtask 6: 33 / 33