Submission #1249487

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249487		Temmie	Souvenirs (IOI25_souvenirs)	C++20	4 / 100	13 ms	412 KiB

souvenirs

#include <bits/stdc++.h>

std::pair <std::vector <int>, long long> transaction(long long);

void buy_souvenirs(int n, long long p0) {
	std::vector <long long> p(n, -1);
	p[0] = p0;
	std::map <int, std::pair <std::vector <int>, long long>> mp;
	mp[0] = { { 0 }, p0 };
	std::vector <long long> cnt(n, 0);
	auto ask = [&] (long long val) {
		auto t = transaction(val);
		std::sort(t.first.rbegin(), t.first.rend());
		for (int x : t.first) cnt[x]++;
		if (t.first.size() == 1) p[t.first[0]] = val - t.second;
		if (!mp.count(t.first[0])) mp[t.first[0]] = { t.first, val - t.second };
		return t;
	};
	for (long long avg = p0 - 1; p[n - 1] == -1; ) {
		auto t = ask(avg);
		avg = (avg - t.second + t.first.size() - 1) / t.first.size() - 1;
	}
	while (*std::min_element(p.begin(), p.end()) < 0) {
		int i = n - 1;
		while (p[i] != -1) i--;
		while (!mp.count(i)) i--;
		bool unkn = false;
		for (int x : mp[i].first) if (x != i && p[i] == -1) unkn = true;
		if (unkn) {
			long long q = mp[i].second;
			int tot = 1;
			for (int j = 1; j < (int) mp[i].first.size(); j++)
				if (p[mp[i].first[j]] != -1)
					q -= p[mp[i].first[j]];
				else
					tot++;
			(void) ask((q + tot - 1) / tot - 1);
		} else {
			long long q = mp[i].second;
			for (int j = 1; j < (int) mp[i].first.size(); j++) q -= p[mp[i].first[j]];
			p[i] = q;
			auto t = ask(q - 1);
		}
	}
	for (int i = 0; i < n; i++) if (cnt[i] < i) ask(p[i]);
}

• 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