Submission #1254633

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

souvenirs

#include "bits/stdc++.h"
#include "souvenirs.h"
using namespace std;

int N;
vector<long long> cnt_bought, prices;

void find_prices(long long p){
	auto [L, R] = transaction(p-1);

	for (int x : L)
		cnt_bought[x]++;

	while (L.size() > 1){
		if (prices[L.back()]){
			R += prices[L.back()];
			L.pop_back();
			continue;
		}

		long long m = (p - 1 - R) / (long long)L.size();
		find_prices(m+1);
	}

	prices[L[0]] = p - 1 - R;

	if (L[0] != N-1 && prices[L[0]+1] == 0){
		find_prices(prices[L[0]]);
	}
}

void buy_souvenirs(int N, long long P0) {
	::N = N;
	cnt_bought.assign(N, 0);
	prices.assign(N, 0);

	find_prices(P0);

	for (int i = 1; i < N; i++){
		while (cnt_bought[i] != i){
			transaction(prices[i]);
			cnt_bought[i]++;
		}
	}
}

• 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