Submission #1249424

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249424		weirdflexbutok	Souvenirs (IOI25_souvenirs)	C++20	100 / 100	12 ms	412 KiB

souvenirs

#include "souvenirs.h"
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
 
std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());
const i64 MX = 1e15;

void buy_souvenirs(int n, i64 P0){
    std::vector<i64> p(n);
    p[0] = P0;

    std::set<std::pair<std::vector<int>, i64>> S;//[p1, p2 ... pn], cost
    std::vector<int> sc = {0};
    S.insert(make_pair(sc, p[0]));
    std::vector<int> EQ(n), CNT(n); // we have an eqn where min index = i

    while(!S.empty()){
        auto [v, sm] = *S.rbegin();
        S.erase(*S.rbegin());
        //first update indices to latest
        std::vector<int> nv;

        for(auto x : v){
            if(p[x]) sm -= p[x];
            else nv.push_back(x);
        }

        if(v.front() == 0){
            //ask 0!
            auto [res, rem] = transaction(p[0] - 1);
            i64 used = p[0] - 1 - rem;
            EQ[res.front()] = 1;
            S.insert(std::make_pair(res, used));
            for(auto x : res) CNT[x]++;
            // cout << S.size() << '\n';
        }
        else if(nv.empty()){
            //do nothing
        }
        else if(nv.size() == 1){

            
            p[nv.back()] = sm;
            auto i = nv.back();
            if(i + 1 < n and EQ[i + 1] == 0){
                auto [res, rem] = transaction(p[i] - 1);
                for(auto x : res) CNT[x]++;

                i64 used = p[i] - 1 - rem;
                EQ[res.front()] = 1;
                assert(res.front() == i + 1);
                S.insert(make_pair(res, used));
            }
        }
        else{   
            //ask sm / n
            i64 old = sm;
            sm /= nv.size();
            auto [res, rem] = transaction(sm);
            for(auto x : res) CNT[x]++;

            i64 used = sm - rem;
            EQ[res.front()] = 1;
            EQ[nv.front()] = 1;
            S.insert(make_pair(res, used));
            S.insert(make_pair(nv, old));
        }   
    }   
    for(int i = 0; i < n; i++){
        while(CNT[i] < i) {
            ++CNT[i];
            transaction(p[i]);
        }
    }
}

• 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