제출 #1249669

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1249669		QwertyPi	선물 (IOI25_souvenirs)	C++20	100 / 100	12 ms	428 KiB

souvenirs

#include "souvenirs.h"
#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N_MAX = 100 + 11;
bool used[N_MAX][N_MAX], eq[N_MAX][N_MAX];
int sum[N_MAX], P[N_MAX];

int _N;

int _transaction(int pay) {
    // cout << "TRANS " << pay << endl;
    auto [C, rem] = transaction(pay);
    assert(!C.empty());
    int cost = pay - rem;
    sum[C[0]] = cost;
    for (int i = 0; i < (int) C.size(); i++) {
        used[C[0]][C[i]] = eq[C[0]][C[i]] = true;
        if (i > 0 && P[C[i]] && eq[C[0]][C[i]]) {
            eq[C[0]][C[i]] = false, sum[C[0]] -= P[C[i]];
        }
    }
    // for (int i = 0; i < _N; i++) {
    //     for (int j = 0; j < _N; j++) {
    //         cout << eq[i][j] << ' ';
    //     }
    //     cout << ' ';
    //     cout << sum[i] << ' ';
    //     cout << P[i] << ' ';
    //     cout << '\n';
    // }
    return C[0];
}

void solve(int N) {
    if (N == 0) return;

    int prv = -1, cnt = 1;
    for (int j = N - 1; j >= 0; j--) {
        if (eq[j][j]) {
            prv = j;
            cnt = accumulate(eq[j] + j, eq[j] + N, 0LL);
            break;
        }
    }
    // cout << "prv = " << prv << endl;
    assert(prv >= 0);
    while (prv < N - 1) {
        int r = _transaction((sum[prv] - 1) / cnt);
        prv = r;
        cnt = accumulate(eq[prv] + prv, eq[prv] + N, 0LL);
    }
    P[N - 1] = sum[N - 1];
    for (int i = 0; i < N - 1; i++) {
        if (eq[i][N - 1]) eq[i][N - 1] = false, sum[i] -= P[N - 1];
    }
    solve(N - 1);
}

void buy_souvenirs(int32_t N, int P0) {
    _N = N;
    eq[0][0] = 1; sum[0] = P[0] = P0;
    solve(N);
    // for (int i = 0; i < _N; i++) {
    //     for (int j = 0; j < _N; j++) {
    //         cout << used[i][j] << ' ';
    //     }
    //     cout << '\n';
    // }
    // for (int i = 0; i < _N; i++) {
    //     cout << P[i] << ' ';
    // }
    // cout << '\n';
    for (int i = 1; i < N; i++) {
        for (int j = i; j < N; j++) {
            if (!used[i][j]) {
                transaction(P[j]);
            }
        }
    }
}

• 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