Submission #1249392

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

souvenirs

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

int N;
ll prices[105];
ll cnt[105];
map<ll, pair<vector<int>,ll>> cache;
pair<vector<int>,ll>  query(ll x){
	//returns the unknown types and their sum of costs
	vector<int> bought;
	ll change;
	bool cached = false;
	if (cache.count(x)){
		tie(bought, change) = cache[x];	
		cached = true;
	}
	else{
		tie(bought, change) = transaction(x);
		cache[x] = make_pair(bought, change);
	}
	ll paid =  x - change;
	vector<int> ret;
	for (auto u: bought){
		if (!cached) cnt[u]--;
		if (prices[u] != -1){
			paid -= prices[u];
		} else{
			ret.emplace_back(u);
		}
	}
	return make_pair(ret, paid);
}

void solve(ll x){
	vector<int> bought; ll total;
	tie(bought, total) = query(x);
	while (bought.size() > 1){
		solve(total/bought.size());
		tie(bought, total) = query(x);
	}
	if (bought.size() == 1){
		ll idx = bought[0];
		prices[idx] = total;
		if (idx != N - 1 && prices[idx + 1] == -1){
			solve(total - 1);
		}
	}
}

void buy_souvenirs(int n, ll p0){
	memset(prices,-1,sizeof(prices));
	for (int i=0;i<n;i++) cnt[i] = i;
	prices[0] = p0;
	N = n;
	solve(p0 - 1);
	for (int i=1;i<n;i++){
		while (cnt[i]--){
			transaction(prices[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