제출 #1250909

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1250909		ByeWorld	선물 (IOI25_souvenirs)	C++20	25 / 100	11 ms	440 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;

ll n, c[MAXN], buy[MAXN];
vector<pvi> que;
bool done = 0;

void clean(){
	done = 1;
	vector<pvi> all;
	for(auto [vec, tot] : que){
		vector<int> baru;
		for(auto in : vec){
			if(c[in] == -1) baru.pb(in);
			else tot -= c[in];
		}
		if(baru.size()==1){
			c[baru[0]] = tot;
			done = 0;
		} else {
			all.pb(make_pair(baru, tot));
		}
	}
	swap(all, que);
}

ll las, cari;
void op(){
	while(true){
		auto [aw, sis] = tra(las);
		for(auto in : aw) buy[in]++;
		vector<int> vec;
		for(auto in : aw){
			if(c[in] != -1) sis -= c[in];
			else vec.pb(in);
		}

		ll tot = las-sis;
		if(vec.size() == 1){
			c[vec[0]] = tot;
			if(vec[0] == cari) break;
			las = tot-1;

		} else {
			que.pb(pvi(vec, tot));
			las = tot/vec.size();
		}
	}
}
void buy_souvenirs(int N, long long P0) {
	n = N;
	c[0] = P0;
	for(int i=1; i<=n-1; i++) c[i] = -1;

	las = c[0]-1; cari = n-1;
	op();

	while(!done) clean();

	while(!que.empty()){
		auto [aw, sis] = que.back(); que.pop_back();

		for(int i=n-1; i>=1; i--){
			if(c[i]==-1){
				cari = i; break;
			}
		}
		las = sis/aw.size();
		op();

		while(!done) clean();
	}

	// 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: 0 / 14
• Subtask 4: 18 / 18
• Subtask 5: 0 / 28
• Subtask 6: 0 / 33