Submission #1256054

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256054		Turkhuu	Souvenirs (IOI25_souvenirs)	C++20	4 / 100	1 ms	840 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;
pair<set<int>, ll> query(ll M) {
    vector<int> v; ll x;
    if (mp.find(M) == mp.end()) mp[M] = transaction(M);
    tie(v, x) = mp[M];
    x = M - x;
    set<int> s;
    for (int i : v) {
        C[i]++;
        if (!known[i]) s.insert(i);
        else x -= P[i];
    }
    res.push_back({s, x});
    return {s, x};
}
void buy_rest() {
    FOR(i, 0, N - 1) {
        assert(C[i] <= i);
        while (C[i] < i) query(P[i]);
    }
}
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 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;
    }
    // cout << ":: " << S << " " << P[S] << "\n";
    auto [s, x] = query(P[S] - 1);
    while (s.size() > 1) {
        int m = s.size();
        // cout << " ## " << x << " " << m << "\n";
        auto [s2, x2] = query(x / m);
        s = s2, x = x2;
    }
    if (s.empty()) {
        // cout << "aa\n";
    }
    int i = *s.begin();
    know(i, x);
    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(0);
    buy_rest();
}

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