Submission #1252184

#	Time	Username	Problem	Language	Result	Execution time	Memory
1252184		kuroba	Souvenirs (IOI25_souvenirs)	C++20	100 / 100	12 ms	420 KiB

souvenirs

#include "souvenirs.h"

#include <iostream>
using namespace std;

// Compile with:
// g++ -std=gnu++20 -O2 -o souvenir souvenirs.h souvenirs.cpp
// Can call:
// std::pair<std::vector<int>, long long> transaction(long long M)
long long price[101];
long long bought[101];
bool debug = false;
void recurse(int N, long long guess) {
    pair<vector<int>, long long> ret = transaction(guess);
    vector<int>& items = ret.first;
    long long remainder = ret.second;
    for (int i = 0; i < items.size(); i++) {
        bought[items[i]]++;
    }

    if (debug) {
        cout << "Transaction: " << guess << " returns (";
        for (int i = 0; i < items.size(); i++) {
            cout << items[i] << " ";
        }
        cout << ") and remainder " << remainder << endl;
    }
    if (items.size() == 1) {
        // only hit one item
        // we know it's exact value.
        long long s = guess - remainder;
        price[items[0]] = s;
        if (debug) {
            cout << "Deduced price[" << items[0] << "] = " << s << endl;
        }
        if (items[0] < N-1) {
            // if there's more items to the right,
            // we should recurse further
            recurse(N, s-1);
        }
    }
    else {
        // hit multiple items
        // Guess the average of them (this is guaranteed to be safe).

        // While we don't know the price of all of our items, make "safe" guesses,
        //
        while (true) {
            int known_items = 0;
            int last_unknown_idx = 0;
            long long s = guess - remainder;
            for (int i = 0; i < items.size(); i++) {
                if (price[items[i]] != 0) {
                    known_items += 1;
                    s -= price[items[i]];
                }
                else {
                    last_unknown_idx = i;
                }
            }
            if (known_items == items.size()-1) {
                price[items[last_unknown_idx]] = s;
                if (debug) {
                    cout << "Deduced price[" << items[last_unknown_idx] << "] = " << s << endl;
                }
                known_items += 1;
            }
            if (known_items == items.size()) {
                break;
            }
            long long unknown_items = items.size() - known_items;

            if (debug) {
                cout << "known_items = " << known_items << ", unknown_items = " << unknown_items << ", s = " << s << endl;
                cout << "state transaction: " << guess << " returns (";
                for (int i = 0; i < items.size(); i++) {
                    cout << items[i] << " ";
                }
                cout << ") and remainder " << remainder << endl;
                for (int i = 0; i < N; i++) {
                    cout << "i = " << i << ", p = " << price[i] << ", b = " << bought[i] << endl;
                }
                // for (int i = 0; i < items.size(); i++) {
                //     cout << "item: " << items[i] << " " << price[items[i]] << endl;
                // }
                // cout << "Starting new recursion with " << s / unknown_items << endl;
            }
            recurse(N, s / unknown_items);
        }
    }
    // Find the next smallest number that we don't know.
    for (int i = N-1; i > items[0]; i--) {
        if (price[i] == 0 && price[i-1] != 0) {
            recurse(N, price[i-1] - 1);
        }
    }
}

void buy_souvenirs(int N, long long P0) {
    long long x = P0;
    for (int i = 0; i < N; i++) {
        price[i] = 0;
        bought[i] = 0;
    }
    price[0] = P0;
    for (int i = 1; i < N; i++) {
        if (price[i] == 0) {
            if (debug) {
                cout << "Top level call for " << i << endl;
            }
            recurse(N, price[i-1] - 1);       
        }
        if (price[i] == 0) {
            cout << "Failed to deduce " << i << endl;
            return;
        }
    }
    
    for (int i = 0; i < N; i++) {
        while (bought[i] < i){
            if (price[i] != 0) {
                transaction(price[i]);
                bought[i]++;
            }
            else {
                cout << "Did not deduce price of " << i << endl;
                break;
            }
        }
    }
    if (debug) {
        cout << "Final answer: " << endl;
        for (int i = 0; i < N; i++) {
            cout << i << ": " << price[i] << ", " << bought[i] << endl;
        }
    }
}

• 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