# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1249656 | PurpleCrayon | Souvenirs (IOI25_souvenirs) | C++20 | 0 ms | 0 KiB |
#include "souvenirs.h"
#include <utility>
#include <vector>
#include <cassert>
#include <algorithm>
#include <numeric>
#include <iostream>
using namespace std;
const int N = 5e2+10;
using ll = long long;
int n;
int a[N];
int cnt_used[N];
ll ceil_div(ll x, ll y) {
return (x + y - 1) / y;
}
pair<vector<bool>, ll> qry(ll x) {
// returns whether each thing is in or not and the sum of chosen things, updates cnt_used
vector<bool> chosen(n);
auto [idx, left] = transaction(x);
for (int x : idx) chosen[x] = 1, cnt_used[x]++;
return make_pair(chosen, x - left);
}
int cnt_calls = 0;
int rec(int r, ll x) {
cnt_calls++;
if (cnt_calls >= 10) {
exit(0);
}
auto [chosen, sum] = qry(x);
int l = 0;
while (!chosen[l]) l++;
while (true) {
for (int i = r+1; i < n; i++) {
assert(a[i] != -1);
if (chosen[i]) {
sum -= a[i];
chosen[i] = 0;
}
}
if (count(chosen.begin(), chosen.end(), 1) == 1) {
a[l] = sum;
if (l < r && a[l+1] == -1) {
rec(r, a[l]-1);
}
return l;
}
int k = 0;
for (int i = l; i <= r && chosen[i]; i++) {
k++;
}
for (int i = l + k; i <= r; i++) {
if (chosen[i]) { // if I chose anything later, consider everything later as one item
k++;
break;
}
}
// max is >= ceil(sum / k)
// min is < than that
ll pivot_x = ceil_div(sum, k) - 1;
int pivot = rec(r, pivot_x);
r = pivot - 1;
}
return l;
}
void buy_souvenirs(int _n, ll P0) {
n = _n;
memset(a, -1, sizeof(a));
memset(cnt_used, 0, sizeof(cnt_used));
a[0] = P0;
assert(rec(n-1, a[0] - 1) == 1);
for (int i = 1; i < n; i++) {
while (cnt_used[i] < i) {
qry(a[i]);
}
}
}