Submission #1258325

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

souvenirs

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

const int N = 104;

int pr[N];
int lf[N];


void buy(vector<signed> a, int price){
	if (a.size() == 1){
		pr[a[0]] = price; return;
	}
	if (pr[a.back()]){
		price -= pr[a.back()]; a.pop_back(); 
		return buy(a, price);
	}
	int m = a.size();
	int am = price/m;
	// for (int x: a) cout<<x<<' '; cout<<'\n';
	for (int i=a[0]; i<a.back(); i++) if (pr[i]) am = pr[i]-1;
	auto [v, r] = transaction(am);
	for (auto x: v) lf[x]--;
	buy(v, am - r);
	buy(a, price);
}

void buy_souvenirs(signed N, long long P0) {
	for (int i=0; i<N; i++) lf[i] = i;
	int last = 0;
	while (1){
		auto [v, r] = transaction(P0-1);
		for (auto x: v) lf[x]--;
		buy(v, P0-1-r);
		int fs = -1;
		for (int i=last+2; i<N; i++) if (!pr[i]) {fs = i-1; break;}
		if (fs == -1) break;
		P0 = pr[fs]; last = fs;
	}
	for (int i=0; i<N; i++) while (lf[i]) transaction(pr[i]), lf[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