Submission #1269610

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269610		brendonw	Souvenirs (IOI25_souvenirs)	C++20	39 / 100	15 ms	1032 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;
	map<ll, pair<vector<int>, ll>> cache;
	auto get = [&](ll cost) {
		if (cache.count(cost)) {
			return cache[cost];
		} else {
			auto [vals, over] = transaction(cost);
			for (auto &val: vals) {
				cnt[val]++;
			}
			cache[cost] = {vals, over};
			return pair{vals, over};
		}
	};
	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;
			if (cur.empty()) {
				for (int i = 0; i < n; ++i) {
					if (prices[i] == -1) {
						cost = prices[i - 1] - 1;
						break;
					}
				}
			} 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();
//				cout << cost << endl;
//				for (int i = 0; i < cur.size(); ++i) {
//
//					cout << "{ ";
//					for (auto &val: cur[i].first) {
//						cout << val << " ";
//					}
//					cout << "}" << " " << cur[i].second << '\n';
//
//				}
//				cout << "-------------------------" << '\n';
			}
			while (count(prices.begin(), prices.end(), -1) != 0) {
				auto [vals, over] = get(cost);
//				for (auto &val: vals) {
//					cnt[val]++;
//				}
				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 = old_sum - 1;
					} else {
						break;
					}
				} else if (vals.size() == 1) {
					prices[vals[0]] = sum;
					clear();
					if (vals[0] == n - 1) {
						break;
					} else {
						cost = sum - 1;
					}
				} 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