Submission #1268215

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268215		LucaDantas	Souvenirs (IOI25_souvenirs)	C++20	3 / 100	11 ms	408 KiB

souvenirs

#include "souvenirs.h"
#include <bits/stdc++.h>
using namespace std;

void buy_souvenirs(int N, long long P0) {
    vector<pair<vector<int>, long long>> queries(N);
    queries[0] = {{0}, P0};
    vector<int> P(N); // if we know the value we assign it here, if we don't know it's 0
    P[0] = P0;
    vector<int> cnt(N); // how many times each item was queried

    vector<int> known_heads = {0};
    int discovered = N; // up until which point from the back we know the values of

    auto update_query = [&](int head) {
        assert(head < discovered);
        auto &[arr, sum] = queries[head];
        while(arr.back() >= discovered) {
            sum -= P[arr.back()];
            arr.pop_back();
            assert(arr.size() >= 1);
        }
    };

    auto get_query_value = [&](int head) {
        update_query(head);
        long long sum = queries[head].second;
        int sz = (int) queries[head].first.size();
        return (sum+sz-1) / sz - 1;
    };

    auto get_true_value = [&](int head) {
        update_query(head);
        return queries[head].second;
    };

    auto update_cnts = [&](vector<int> res) {
        for(int x : res)
            cnt[x]++;
    };

    while(discovered != 0) {
        int last_head = known_heads.back();
        // printf("last head %d\n", last_head);

        if(discovered == last_head+1) {
            P[last_head] = get_true_value(last_head); // just do the sum minus the values of all the others which we already know
            discovered--;
            known_heads.pop_back();
            continue;
        }

        int query_value = get_query_value(last_head);
        // printf("query_value %d\n", query_value);
        pair<vector<int>, long long> res = transaction(query_value);
        update_cnts(res.first);
        int new_head = res.first.front();
        // printf("new head %d\n", new_head);
        assert(new_head < discovered);

        queries[new_head] = {res.first, query_value - res.second};
        known_heads.push_back(new_head);
    }

    for(int i = 0; i < N; i++)
        while(cnt[i] < i) {
            ++cnt[i];
            transaction(P[i]);
        }
}

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