Submission #1249716

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249716		chithanhnguyen	Souvenirs (IOI25_souvenirs)	C++20	25 / 100	11 ms	416 KiB

souvenirs

#include "souvenirs.h"
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define sz(x) (int)(x).size()

const int MAXN = 105;
int N;
int P[MAXN], sum[MAXN], cnt[MAXN];
bool equation[MAXN][MAXN];

int build_equation(int pay) {
    auto [items, leftover] = transaction(pay);
    assert(!items.empty());
    int total = pay - leftover;
    int base = items[0];
    sum[base] = total;

    for (int i : items) {
        equation[base][i] = true;
        cnt[i]++;
        if (i != base && P[i]) {
            equation[base][i] = false;
            sum[base] -= P[i];
        }
    }
    return base;
}

void buy_souvenirs(signed num, int P0) {
    N = num;
    equation[0][0] = true;
    sum[0] = P[0] = P0;

    int known = 1;
    while (known < N) {
        int pivot = -1, k = 0;
        for (int i = N - 1; i >= 0; --i) {
            if (equation[i][i]) {
                pivot = i;
                k = 0;
                for (int j = pivot; j < N; ++j)
                    if (equation[pivot][j]) ++k;
                break;
            }
        }

        while (pivot < N - 1) {
            int next = build_equation((sum[pivot] - 1) / k);
            pivot = next;
            k = 0;
            for (int j = pivot; j < N; ++j)
                if (equation[pivot][j]) ++k;
        }

        int cur = N - known;
        P[cur] = sum[cur];
        ++known;

        for (int i = 0; i < cur; ++i) {
            if (equation[i][cur]) {
                equation[i][cur] = false;
                sum[i] -= P[cur];
            }
        }
    }

    for (int i = 1; i < N; ++i) {
        while (cnt[i] < i) {
            ++cnt[i];
            transaction(P[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