Submission #1307316

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307316		WH8	Souvenirs (IOI25_souvenirs)	C++20	100 / 100	13 ms	400 KiB

souvenirs

#include <bits/stdc++.h>
using namespace std;
#include "souvenirs.h"
typedef long long ll;
void buy_souvenirs(int N, long long P0) {
	vector<ll> cnt(N, 0), val(N, -1);
	val[0]=P0;
	
	pair<vector<int>, long long> res;
	auto dfs = [&](auto && dfs, vector<int> cur, ll sum)->void{
		while(!cur.empty() ){
			/*cout<<endl;
			printf("state ");
			for(auto it: cur)cout<<it<<", ";
			printf(" : sum is %lld\n", sum);
			for(auto it: val)cout<<it<<" ";
			cout<<endl;*/
			while (!cur.empty() and val[cur.back()] != -1){
				sum-=val[cur.back()];
				cur.pop_back();
			}
			if(cur.empty())break;
			if(cur.size() == 1){
				val[cur.back()]=sum;
				bool found=false;
				for(int j=cur.back()+1;j<N;j++){
					if(val[j] == -1)found=true;
				}
				if(cur.back() != N-1 and found){
					res=transaction(sum-1);
					for(auto it: res.first)cnt[it]++;
					dfs(dfs, res.first, sum-1-res.second);
				}
			}
			else {
				res=transaction(sum/cur.size());
				for(auto it: res.first)cnt[it]++;
				dfs(dfs, res.first, sum/cur.size() - res.second);
			}
		}
	};
	for(int i=1;i<N;i++){
		if(val[i] == -1){
			res = transaction(val[i-1]-1);
			for(auto it : res.first) cnt[it]++;
			dfs(dfs, res.first, val[i-1]-1-res.second);
		}
	}
	/*for(auto it:val)cout<<it<<" ";
	cout<<endl;*/
	for(int i=1;i<N;i++){
		assert(cnt[i] <= i);
		for(int j=0;j<i-cnt[i];j++) transaction(val[i]);
	}
	return;
}

• 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