제출 #1249503

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1249503		sofapuden	선물 (IOI25_souvenirs)	C++20	25 / 100	12 ms	412 KiB

souvenirs

#include "souvenirs.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

void buy_souvenirs(int n, ll p0) {
	vector<vector<int>> cu(n);
	vector<int> amm(n, 0);
	int tot = 0;
	vector<ll> sus(n, 0);
	ll nxt = p0 - 1;
	while(!cu.back().size()) {
		auto [x, rm] = transaction(nxt);
		for(auto y : x) amm[y]++;
		tot++;
		ll su = nxt - rm;
		ll am = x.size();
		cu[x[0]] = x;
		sus[x[0]] = su;
		nxt = (su + am - 1) / am - 1;
	}
	while(tot < n - 1) {
		for(int i = n - 2; i; --i) {
			if(!cu[i].size()) break;
			while(cu[i].size() > 1) {
				sus[i] -= sus[cu[i].back()];
				cu[i].pop_back();
			}
		}
		for(int i = n - 2; i; --i) {
			if(cu[i].size() && !cu[i + 1].size()) {
				while(cu[cu[i].back()].size() == 1) {
					sus[i] -= sus[cu[i].back()];
					cu[i].pop_back();
				}
				ll nxt = (sus[i] + (int)cu[i].size() - 1) / (int)cu[i].size() - 1;
				auto [x, rm] = transaction(nxt);
				for(auto y : x) amm[y]++;
				tot++;
				cu[x[0]] = x;
				ll su = nxt - rm;
				sus[x[0]] = su;
				break;
			}
		}
	}
	for(int i = n - 2; i; --i) {
		if(!cu[i].size()) break;
		while(cu[i].size() > 1) {
			sus[i] -= sus[cu[i].back()];
			cu[i].pop_back();
		}
	}
	for(int i = 1; i < n; ++i){
		while(amm[i] != i) {
			transaction(sus[i]);
			amm[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