Submission #1303945

#	Time	Username	Problem	Language	Result	Execution time	Memory
1303945		prism7k	Souvenirs (IOI25_souvenirs)	C++20	7 / 100	12 ms	400 KiB

souvenirs

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

void buy_souvenirs(int N, long long P0) {

	vector<vector<int>> transactions(N);
	vector<int> bought(N, 0);
	vector<long long> sent(N, 0);
	
	// phase 1: buy until last is reached
	long long M = P0 - 1;
	int at = 1;
	while(at + 1 < N) {
		auto res = transaction(M);
		vector<int> souv = res.first;
		long long rem = res.second;
		long long total_cost = M - rem;
		
		sort(souv.begin(), souv.end());
		
		long long min_cost = 0;
		for(int i = 0; i < (int)souv.size(); ++i) {
			bought[souv[i]]++;
			min_cost += N - souv[i];
		}
		transactions[at] = souv;
		sent[at] = total_cost;
		
		long long min_val_of_left = N - at;
		long long amt = N - at;
		total_cost -= min_cost;
		
		min_val_of_left += (total_cost + amt - 1) / amt;
		M = min_val_of_left - 1;
		at++;
	}
	
	// phase 2: find price of last
	auto res = transaction(M);
	vector<int> souv = res.first;
	long long rem = res.second;
	
	assert(souv.size() == 1);
	vector<long long> prices(N, 0);
	prices[N - 1] = M - rem;
	bought[N - 1]++;
	
	// phase 3: backtrack until all are bought
	for(int i = N - 1; i >= 1; --i) {
		if(prices[i] == 0) {
			for(int b : transactions[i]) {
				if(b != i) {
					sent[i] -= prices[b];
				}
			}
			prices[i] = sent[i];
		}
		while(bought[i] < i) {
			transaction(prices[i]);
			bought[i]++;
		}
	}
	prices[0] = P0;
	//~ cout << "PRICES\n";
	//~ for(int i = 0; i < N; ++i) {
		//~ cout << prices[i] << " ";
	//~ }
	//~ cout << "\n-----------\n";
	return;
}

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