제출 #1256564

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1256564		jamesbamber	선물 (IOI25_souvenirs)	C++20	100 / 100	12 ms	420 KiB

souvenirs

#include "souvenirs.h"
#include <utility>
#include <vector>
#include <cassert>
#include <iostream>

using namespace std;

void buy_souvenirs(int N, long long P0) {

    vector<long long> p(N, -1);
    vector<int> bought(N, 0);
    p[0] = P0;

    auto my_transaction = [&](long long M) {
        // cerr << "transaction: " << M << endl;
        // for(auto x: p) cerr << x << " ";
        // cerr << endl;

        auto [v, c] = transaction(M);
        for(int x: v) bought[x]++;
        return make_pair(v, M - c);
    };

    auto clean_group = [&](vector<int> &v, long long &c) {
        vector<int> new_v;
        for(int x: v) {
            if(p[x] != -1) c -= p[x];
            else new_v.push_back(x);
        }

        v = new_v;
    };

    auto rec = [&](auto &&self, vector<int> v, long long c) -> void {
        // cerr << v.size() << " " << c << endl;
        clean_group(v, c);
        while(v.size() > 1) {
            auto [next_v, next_c] = my_transaction(c / v.size());

            self(self, next_v, next_c);
            clean_group(v, c);
        }

        assert(v.size() == 1);
        p[v[0]] = c;

        for(int i=v[0]; i<N; i++) {
            if(p[i] == -1) {
                auto [v, c] = my_transaction(p[i-1] - 1);
                self(self, v, c);
            }
        }
    };

    for(int i=1; i<N; i++) {
        if(p[i] == -1) {
            auto [v, c] = my_transaction(p[i-1] - 1);
            rec(rec, v, c);
        }
        assert(p[i] != -1);
        // cerr << i << " price " << p[i] << endl;
        while(bought[i] < i) my_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