Submission #1250258

#	Time	Username	Problem	Language	Result	Execution time	Memory
1250258		gptopenai	Souvenirs (IOI25_souvenirs)	C++20	0 / 100	11 ms	428 KiB

souvenirs

#include "souvenirs.h"
#include <vector>
#include <algorithm>
#include <cassert>
using namespace std;

/**
 * Simulate what the grader does when you hand it M coins,
 * given a candidate price‐vector P.
 */
static vector<int> simulate(const vector<long long>& P, long long M) {
    vector<int> bought;
    long long R = M;
    int N = (int)P.size();
    for (int i = 0; i < N; i++) {
        if (R >= P[i]) {
            R -= P[i];
            bought.push_back(i);
        }
    }
    return bought;
}

void buy_souvenirs(int N, long long P0) {
    // 1) Observe the seller's response for every 1 <= M < P0:
    vector<vector<int>> obs(P0);
    for (long long M = 1; M < P0; M++) {
        auto resp = transaction(M);
        obs[M] = resp.first;
    }

    // 2) Brute‐force all decreasing sequences 
    //    P[1] > P[2] > ... > P[N-1] drawn from {1,...,P0-1}.
    vector<int> pool;
    for (int x = 1; x < P0; x++) 
        pool.push_back(x);

    vector<long long> P(N);
    P[0] = P0;

    // We'll generate all size-(N-1) permutations of pool
    // then keep only those whose sorted order is strictly decreasing.
    bool found = false;
    vector<int> idx(pool.size());
    fill(idx.begin(), idx.begin() + (N-1), 1);
    // next_permutation on a 0/1 mask to choose subsets of size N-1
    do {
        // collect chosen elements
        vector<int> cand;
        for (int i = 0; i < (int)pool.size(); i++)
            if (idx[i]) 
                cand.push_back(pool[i]);
        // sort in decreasing order
        sort(cand.begin(), cand.end(), greater<int>());

        // build full price‐vector
        for (int i = 1; i < N; i++)
            P[i] = cand[i-1];

        // test this P against every M
        bool ok = true;
        for (long long M = 1; M < P0 && ok; M++) {
            if (simulate(P, M) != obs[M])
                ok = false;
        }
        if (ok) {
            found = true;
            break;
        }
    } while (prev_permutation(idx.begin(), idx.end()) && !found);

    assert(found && "Exactly one price‐vector must match");

    // 3) We now know P[1..N-1].  To get i copies of type i,
    //    simply pay M = P[i] exactly (which buys one type-i souvenir),
    //    and repeat that i times.
    for (int i = 1; i < N; i++) {
        for (int cnt = 0; cnt < i; cnt++) {
            transaction(P[i]);
        }
    }
}

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