Submission #1258306

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258306		allin27x	Souvenirs (IOI25_souvenirs)	C++20	25 / 100	13 ms	1380 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;
	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: 0 / 14
• Subtask 4: 18 / 18
• Subtask 5: 0 / 28
• Subtask 6: 0 / 33