Submission #1267968

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267968		zwezdinv	Souvenirs (IOI25_souvenirs)	C++20	4 / 100	12 ms	408 KiB

souvenirs

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

void buy_souvenirs(int n, long long p0) {
	struct basket {
		std::vector<int> items = {};
		long long s = 0;
	};
	std::vector<basket> a(n);
	std::vector<int> cnt(n);
	auto ask = [&](long long s) -> basket {
		auto [occ, rem] = transaction(s);
		for (auto x : occ) cnt[x]++;
		return {occ, s - rem};
	};
	auto filter = [&](basket& k) -> void {
		basket ret;
		ret.s = k.s;
		for (auto x : k.items) {
			if (x == k.items[0] || a[x].items.size() != 1) {
				ret.items.push_back(x);
			} else {
				ret.s -= a[x].s;
			}
		}
		std::swap(ret, k);
	};
	a[1] = ask(p0 - 1);
	for (int i = n - 1; i > 0; --i) {
		int j = i;
		while (a[j].s == 0) j--;
		while (j != i) {
			filter(a[j]);
			long long q;
			if (a[j].items.size() == 1) q = a[j].s - 1;
			else q = a[j].s / a[j].items.size();
			auto s = ask(q);
			j = s.items[0];
			a[j] = s;
		}
		filter(a[i]);
	}
	for (int i = 0; i < n; ++i) {
		while (cnt[i] < i) {
			transaction(a[i].s);
		}
	}
}

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