Submission #1254871

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

souvenirs

#include "souvenirs.h"
#include <bits/stdc++.h>
using namespace std;
void buy_souvenirs(int N, long long P0) {
	vector<int> bought[N];
	long long cst[N];
	int cnt[N];
	memset(cnt,0,sizeof(cnt));
	bought[0] = {0};
	cst[0] = P0;
	memset(cnt,0,sizeof(cnt));
	stack<int> st;
	st.push(0);
	for(int cur=N;--cur;) {
		while(st.top() != cur) {
			long long nxt;
			if(bought[st.top()].size() == 1)
				nxt = cst[st.top()] - 1;
			else
				nxt = cst[st.top()] / bought[st.top()].size();
			auto [nwBuy, nwCst] = transaction(nxt);
			for(auto bought: nwBuy)
				cnt[bought]++;
			nwCst = nxt - nwCst;
			while(nwBuy.size() && nwBuy.back() > cur) {
				nwCst -= cst[nwBuy.back()];
				nwBuy.pop_back();
			}
			bought[nwBuy[0]] = nwBuy;
			cst[nwBuy[0]] = nwCst;
			st.push(nwBuy[0]);
		}
		st.pop();
		for(int i=0;i<cur;i++)
			if(bought[i].size() && bought[i].back() == cur) {
				bought[i].pop_back();
				cst[i] -= cst[cur];
			}
	}
	for(int cur=0;cur<N;cur++)
		for(int i=cnt[cur];i<cur;i++)
			transaction(cst[cur]);
}

• 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