제출 #1285620

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1285620		ecen30	Souvenirs (IOI25_souvenirs)	C++20	25 / 100	13 ms	332 KiB

souvenirs

//This is Grok code. I am using this website to test different AI's and their abilities to solve IOI problems. Please understand. I do not mean to cheat. Just trying to get a good grade on my science project.

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

using namespace std;

pair<vector<int>, long long> transaction(long long M);

void buy_souvenirs(int n, long long P0) {
    vector<long long> price(n);
    price[0] = P0;

    // Step 1: Discover all prices using a single greedy descent
    // We start with M = P0-1 and repeatedly take the "leading" transaction
    // that buys the highest type not yet fully resolved.
    vector<vector<int>> leading(n);
    vector<long long> spent(n, 0);
    vector<int> bought(n, 0);
    int resolved = 0;

    long long M = P0 - 1;
    while (resolved < n - 1) {
        auto [types, rem] = transaction(M);
        sort(types.begin(), types.end());
        long long cost = M - rem;

        int lead = types.empty() ? 0 : types[0];
        if (leading[lead].empty()) {
            leading[lead] = types;
            spent[lead] = cost;
            resolved++;
        }
        for (int t : types) bought[t]++;

        // Reduce M to force buying lower types or resolve current lead
        if (types.size() == 1) {
            M = cost - 1;  // Avoid exact match unless needed
        } else {
            M = cost / types.size();
            if (M * (long long)types.size() == cost) M--;
        }

        // Stop when we have enough information to resolve all
        if (lead == n - 1 && resolved == n - 1) break;
    }

    // Step 2: Resolve prices from highest to lowest
    for (int i = n - 1; i >= 1; --i) {
        if (price[i]) continue;
        long long total = spent[i];
        for (int j : leading[i]) {
            if (j != i && price[j]) {
                total -= price[j];
            }
        }
        price[i] = total;
    }

    // Step 3: Buy exactly i souvenirs of type i (for i=1 to n-1)
    for (int i = 1; i < n; ++i) {
        while (bought[i] < i) {
            transaction(price[i]);
            bought[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