Submission #1250794

#	Time	Username	Problem	Language	Result	Execution time	Memory
1250794		AMnu	Souvenirs (IOI25_souvenirs)	C++20	100 / 100	12 ms	412 KiB

souvenirs

#include "souvenirs.h"
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;

const int MAXN = 105;

int N, last, buy[MAXN], bp[MAXN];
ll P[MAXN];
bitset <MAXN> B[MAXN];
pair <vector<int>,ll> res;

void dapat(int id) {
	while (last && bp[last] == 1) {
		last--;
	}
	for (int i=1;i<id;i++) {
		if (B[i][id]) {
			B[i][id] = 0;
			P[i] -= P[id];
			bp[i]--;
			if (bp[i] == 1) {
				dapat(i);
			}
		}
	}
}

void beli(ll M) {
	res = transaction(M);
	int id = res.fi[0];
	P[id] = M-res.se;
	for (int x : res.fi) {
		if (bp[x] == 1) {
			P[id] -= P[x];
		}
		else {
			B[id][x] = 1;
			bp[id]++;
		}
		buy[x]++;
	}
	if (bp[id] == 1) {
		dapat(id);
	}
}

void buy_souvenirs(int n, long long P0) {
	N = n;
	P[0] = P0;
	bp[0] = 1;
	last = N-1;
	while (last) {
		for (int i=last;i>=0;i--) {
			if (bp[i]) {
				beli((P[i]-1)/bp[i]);
				break;
			}
		}
	}
	for (int i=1;i<N;i++) {
		while (buy[i] < i) {
			buy[i]++;
			transaction(P[i]);
		}
	}
}

• 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