Submission #1249720

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249720		chithanhnguyen	Souvenirs (IOI25_souvenirs)	C++20	4 / 100	0 ms	428 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], rhs[MAXN], cnt[MAXN];
bool equation[MAXN][MAXN];

int build_equation(int pay) {
    auto [items, leftover] = transaction(pay);
    if (items.empty()) exit(0);
    int total = pay - leftover;
    int base = items[0];
    rhs[base] = total;
    cnt[base]++;

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

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

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

        if (pivot == -1) exit(0);

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

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

        --cur;
    }

    for (int i = 1; i < N; ++i) {
        while (cnt[i] < i) {
            transaction(P[i]);
            cnt[i]++;
        }
    }
}

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