Submission #1249657

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249657		PurpleCrayon	Souvenirs (IOI25_souvenirs)	C++20	0 / 100	0 ms	416 KiB

souvenirs

#include "souvenirs.h"
#include <utility>
#include <vector>
#include <cassert>
#include <algorithm>
#include <numeric>
#include <iostream>
#include <cstring>
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]);
        }
    }
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 4
• Subtask 2: 0 / 3
• Subtask 3: 0 / 14
• Subtask 4: 0 / 18
• Subtask 5: 0 / 28
• Subtask 6: 0 / 33