Submission #1275631

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275631		Nonoze	Souvenirs (IOI25_souvenirs)	C++20	100 / 100	38 ms	424 KiB

souvenirs

#include "souvenirs.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sz(x) (int)x.size()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define fi first
#define se second
#define cmin(a, b) a=min(a, b)
#define cmax(a, b) a=max(a, b)

int n;
vector<int> p, mini, maxi;

bool works(int x, int mid, pair<vector<signed>, int> &res, bool Minimize) {
	int valmin=mid, valmax=mid;
	bool ok=1;
	for (auto y: res.fi) {
		if (y<x) {
			if (mid+(x-y)>maxi[y]) ok=0;
			valmin+=max(mini[y], mid+(x-y));
			valmax+=maxi[y];
		}
		if (y>x) {
			if (mid-(y-x)<mini[y]) ok=0;
			valmin+=mini[y];
			valmax+=min(maxi[y], mid-(y-x));
		}
	}
	return ok && valmin<=res.se && res.se<=valmax;
}

void calc(int x, pair<vector<signed>, int> &res) {
	if (sz(res.fi)==1) {
		mini[x]=maxi[x]=res.se;
		return;
	}
	{ // calc mini
		int l=mini[x], r=maxi[x], ans=mini[x];
		while (l<=r) {
			int mid=(l+r)/2;
			if (works(x, mid, res, 1)) ans=mid, r=mid-1;
			else l=mid+1;
		}
		mini[x]=ans;
	}
	{ // calc maxi
		int l=mini[x], r=maxi[x], ans=maxi[x];
		while (l<=r) {
			int mid=(l+r)/2;
			if (works(x, mid, res, 0)) ans=mid, l=mid+1;
			else r=mid-1;
		}
		maxi[x]=ans;
	}
}

vector<pair<vector<signed>, int>> res;
vector<vector<int>> used;
void process(int id) {
	for (auto x: res[id].fi) {
		calc(x, res[id]);
		// cout << mini[x] << ' ' << maxi[x] << endl;
		if (mini[x]==maxi[x]) {
			// cout << x << endl;
			p[x]=mini[x];
			for (auto &y: used[x]) {
				res[y].se-=p[x];
				res[y].fi.erase(find(all(res[y].fi), x));
			}
			// for (int i=0; i<n; i++) {
			// 	cout << i << ' ' << mini[i] << ' ' << maxi[i] << ' ' << p[i] << endl;
			// }
			for (int i=0; i<x; i++) if (p[i]==-1) cmax(mini[i], p[x]+(x-i));
			for (int i=x+1; i<n; i++) if (p[i]==-1) cmin(maxi[i], p[x]-(i-x));
			for (auto &y: used[x]) process(y);
			used[x].clear();
			return;
		}
	}
}

void buy_souvenirs(signed N, long long P0) {
	n=N; p.resize(n, -1); p[0]=P0;
	vector<int> cnt(n, 0);
	mini.resize(n); maxi.resize(n); mini[0]=maxi[0]=P0;
	for (int i=1; i<n; i++) mini[i]=n-i, maxi[i]=P0-i;
	used.resize(n);
	while (1) {
		int best=-1, bestv=-1;
		for (int i=1; i<n; i++) if (p[i]==-1) {
			if (maxi[i]<bestv || bestv==-1) bestv=maxi[i], best=i;
		}
		if (best==-1) break;
		int i=best;
		assert(cnt[i]<=i);
		// cout << i << ' ' << mini[i] << ' ' << maxi[i] << endl;
		auto r=transaction(maxi[i]);
		res.pb({{}, 0}); res.back().se=maxi[i]-r.se;
		for (auto x: r.fi) {
			cnt[x]++;
			assert(cnt[x]<=x);
			if (p[x]!=-1) {
				res.back().se-=p[x];
			} else {
				res.back().fi.pb(x);
				used[x].pb(sz(res)-1);
			}
		}
		if (r.fi.back()+1<n) cmax(mini.back(), r.se+1);
		for (int j=n-2; j>r.fi.back(); j--) cmax(mini[j], mini[j+1]+1);
		process(sz(res)-1);
	}
	for (int i=1; i<n; i++) {
		assert(cnt[i]<=i);
		if (cnt[i]==i) continue;
		// while (mini[i]<maxi[i]) {
		// 	cout << i << ' ' << mini[i] << ' ' << maxi[i] << endl;
		// 	if (cnt[i]>i) assert(0);
		// 	auto r=transaction(maxi[i]);
		// 	res.pb({{}, 0}); res.back().se=maxi[i]-r.se;
		// 	for (auto x: r.fi) {
		// 		cnt[x]++;
		// 		if (p[x]!=-1) {
		// 			res.back().se-=p[x];
		// 		} else {
		// 			res.back().fi.pb(x);
		// 			used[x].pb(sz(res)-1);
		// 		}
		// 	}
		// 	process(sz(res)-1);
		// }
		while (cnt[i]<i) cnt[i]++, transaction(p[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