Submission #1256075

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

souvenirs

#include "souvenirs.h"
#include <bits/stdc++.h>
#define FOR(i, a, b) for (auto i = (a); i <= (b); i++)
#define ROF(i, a, b) for (auto i = (a); i >= (b); i--)
using namespace std;
using ll = long long;
int N;
vector<bool> known;
vector<ll> P;
vector<int> C;
vector<pair<set<int>, ll>> res;
map<ll, pair<vector<int>, ll>> mp;
void know(int i, ll x) {
    if (known[i]) return;
    // assert(!known[i]);
    P[i] = x, known[i] = 1;
    for (auto& p : res) {
        auto& s = p.first;
        auto& x = p.second;
        if (s.count(i)) {
            s.erase(i);
            x -= P[i];
        }
        if (s.size() == 1) know(*s.begin(), x);
    }
}
void cleanup() {
    for (auto [s, x] : res) if (s.size() == 1) know(*s.begin(), x);
    while (1) {
        auto it = res.begin();
        while (it != res.end() && !(*it).first.empty()) it++;
        if (it == res.end()) break;
        res.erase(it);
    }
}
pair<set<int>, ll> query(ll M) {
    vector<int> v; ll x;
    bool f = 0;
    if (mp.find(M) == mp.end()) mp[M] = transaction(M), f = 1;
    tie(v, x) = mp[M];
    x = M - x;
    // if (f) {
    //     cout << M << " :: " << x << " :: ";
    //     for (int i : v) cout << i << " ";
    //     cout << "\n";
    // }
    set<int> s;
    for (int i : v) {
        if (f) C[i]++;
        if (!known[i]) s.insert(i);
        else x -= P[i];
    }
    res.push_back({s, x});
    cleanup();
    return {s, x};
}
void buy_rest() {
    FOR(i, 0, N - 1) {
        // if (!(C[i] <= i)) while (1) {}
        while (C[i]++ < i) transaction(P[i]);
    }
}
void solve() {
    while (1) {
        if (known == vector<bool>(N, 1)) return;
        bool f = 0;
        int k = -1;
        ROF(i, N - 1, 0) {
            if (!known[i]) f = 1;
            else if (f) {k = i; break;}
        }
        if (mp.find(P[k] - 1) == mp.end()) {
            query(P[k] - 1);
            continue;
        }
        ll mn = 1e18;
        for (auto [s, x] : res) mn = min(mn, x / (int)s.size());
        query(mn);
    }
}
// void solve(int S) {
//     // assert(known[S]);
//     bool all = 1;
//     FOR(i, S, N - 1) if (!known[i]) all = 0;
//     if (all) return;
//     if (known[S + 1]) {
//         solve(S + 1);
//         return;
//     }

//     auto [s, x] = query(P[S] - 1);
//     while (1) {
//         for (auto [s, x] : res) if (s.size() == 1) know(*s.begin(), x);
//         ROF(i, N - 1, S) if (known[i]) solve(i);
//         while (1) {
//             auto it = res.begin();
//             while (it != res.end() && !(*it).first.empty()) it++;
//             if (it == res.end()) break;
//             res.erase(it);
//         }
//         bool duus = 1;
//         for (auto [s, x] : res) if (!s.empty() && *s.rbegin() >= S && *s.begin() >= S) duus = 0;
//         if (duus) break;
//         ll mn = 1e18;
//         for (auto [S, X] : res) {
//             mn = min(mn, X / (int)S.size());
//         }
//         tie(s, x) = query(mn);
//     }
//     ROF(i, N - 1, S) if (known[i]) solve(i);
// }
void buy_souvenirs(int _N, long long P0) {
    N = _N, P.resize(N), C.resize(N), known.resize(N);
    know(0, P0);
    solve();
    buy_rest();
}

• 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