제출 #1252223

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1252223		dreamnguyen	선물 (IOI25_souvenirs)	C++20	100 / 100	12 ms	424 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 M) {
    auto [items, leftover] = transaction(M);
    if (items.empty()) exit(0);
    int total = M - leftover;
    int base = items[0];
    rhs[base] = total;
    cnt[base]++;

    for (int i : items) {
        equation[base][i] = true;
        if (i != base) {
            cnt[i]++;
            if (P[i] && equation[base][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] = P0; P[0] = P0;

    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 = accumulate(equation[i] + i, equation[i] + cur, 0LL);
                break;
            }
        }

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

        while (pivot < cur - 1) {
            pivot = build_equation((rhs[pivot] - 1) / k);
            k = accumulate(equation[pivot] + pivot, equation[pivot] + cur, 0LL);
        }

        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: 3 / 3
• Subtask 3: 14 / 14
• Subtask 4: 18 / 18
• Subtask 5: 28 / 28
• Subtask 6: 33 / 33