Submission #1250991

#	Time	Username	Problem	Language	Result	Execution time	Memory
1250991		ByeWorld	Souvenirs (IOI25_souvenirs)	C++20	100 / 100	16 ms	6688 KiB

souvenirs

#include "souvenirs.h"
#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define fi first
#define se second
#define tra transaction
using namespace std;
typedef pair<ll,ll> pii;
typedef pair<vector<int>,ll> pvi;
const int MAXN = 2e5+10;
void chmn(auto &a, auto b){ a = min(a, b); }

ll n, c[MAXN], buy[MAXN];
pvi que[MAXN];

void ask(ll las){
	// cerr << las <<"ask\n";
	auto [aw, sis] = tra(las);
	for(auto in : aw) buy[in]++;
	vector<int> all;
	sis = las-sis;
	for(auto in : aw){
		if(c[in] != -1) sis -= c[in];
		else all.pb(in);
	}

	if(all.size() == 0) return;
	que[all[0]] = pvi(all, sis);
}

void op(){
	// cari yg udh tau
	bool done = 0;
	for(int i=1; i<=n-1; i++){
		if(c[i]==-1 && que[i].se!=-1 && que[i].fi.size() == 1){
			c[i] = que[i].se;
			que[i] = pvi({}, -1);
			done = 1;
		}
	}

	// clean
	if(done){
		for(int i=1; i<=n-1; i++){
			if(c[i]!=-1 || que[i].se == -1) continue;
			vector<int> baru; ll sis = que[i].se;
			for(auto in : que[i].fi){
				if(c[in] == -1) baru.pb(in);
				else sis -= c[in];
			}
			que[i] = {baru, sis};
			done = 1;
		}
	}
	if(done) return;

	// kalo masih ada isinya
	for(int i=n-2; i>=1; i--){
		if(que[i].fi.size() >= 2 && que[i].se != -1){
			int siz = que[i].fi.size();
			ll mn = que[i].se/siz;
			int ba = que[i].fi.back();
			for(int j=ba; j>=0; j--){
				if(c[j] == -1) continue;
				chmn(mn, c[j]-1);
			}

			ask(mn);
			return;
		}
	}
	// i tau, i+1 ga tau
	for(int i=n-2; i>=0; i--){
		if(c[i]!=-1 && c[i+1]==-1){
			// tanya c[i]-1
			ask(c[i]-1);
			return;
		}
	}
}
void buy_souvenirs(int N, long long P0) {
	n = N;
	c[0] = P0;
	for(int i=1; i<=n-1; i++){
		c[i] = -1;
		que[i] = pvi({}, -1);
	}

	while(true){
		bool done = 0;
		for(int i=1; i<=n-1; i++) 
			done |= (c[i]==-1);
		if(!done) break;
		op();

	// for(int i=1; i<=n-1; i++){
	// 	cerr << c[i] << ' ';
	// }
	// cerr <<" cost\n";
	}

	// for(int i=1; i<=n-1; i++){
	// 	cerr << c[i] << ' ';
	// }
	// cerr <<" cost\n";

	for(int i=1; i<=n-1; i++){
		while(buy[i] < i){
			tra(c[i]); buy[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