Submission #1269631

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269631		brendonw	Souvenirs (IOI25_souvenirs)	C++20	39 / 100	12 ms	416 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<int> cnt(n);

	// transaction on nxt
	vector<pair<vector<int>, ll>> cur;
	auto get = [&](ll cost) {
		auto [vals, over] = transaction(cost);
		for (auto &val: vals) {
			cnt[val]++;
		}
		return pair{vals, over};
	};
	vector<bool> used(n);
	while (count(prices.begin(), prices.end(), -1) != 0) {
		auto update = [&](vector<int> vals, ll sum) -> pair<vector<int>, ll> {
			vector<int> 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<int>, 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 = [&](int 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.front(), a.second) > make_pair(b.first.front(), b.second);
				});
				cost = cur.front().second / cur.front().first.size();
			}
//			cost = next();
			while (count(prices.begin(), prices.end(), -1) != 0) {
				auto [vals, over] = get(cost);
//				for (auto &val: vals) {
//					cnt[val]++;
//				}
				ll old = vals[0];
				ll sum = cost - over;
				bool sub = !(vals.size() == 1 && vals[0] == n - 1);
//				ll old_sum = sum;
				tie(vals, sum) = update(vals, sum);
				cur.push_back({vals, sum});
				if (vals.size() == 0) {
					if (sub) {
						cost = next(old);
					} else {
						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: 0 / 28
• Subtask 6: 0 / 33