Submission #1267986

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267986		thinknoexit	Souvenirs (IOI25_souvenirs)	C++20	100 / 100	11 ms	432 KiB

souvenirs

#include "souvenirs.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 111;
int n;
int cnt[N];
ll P[N];
bool flag[N];
map<ll, pair<vector<int>, ll>> mem;
pair<vector<int>, ll> buy(ll M) {
    pair<vector<int>, ll> res;
    if (mem.count(M)) res = mem[M];
    else {
        mem[M] = res = transaction(M);
        for (auto& x : res.first) {
            cnt[x]++;
        }
    }
    ll used = M - res.second;
    vector<int> v;
    for (auto& x : res.first) {
        if (P[x]) used -= P[x];
        else v.push_back(x);
    }
    return make_pair(v, used);
}
void play(ll p) {
    if (mem.count(p)) return;
    auto now = buy(p);
    flag[now.first[0]] = 1;
    while ((int)now.first.size() > 1) {
        play(now.second / (int)(now.first.size()));
        now = buy(p);
    }
    if ((int)now.first.size() == 1) {
        int nxt = now.first[0];
        P[nxt] = now.second;
        if (nxt != n - 1 && !flag[nxt + 1]) play(P[nxt] - 1);
    }
}
void buy_souvenirs(int _N, ll P0) {
    n = _N;
    P[0] = P0;
    play(P[0] - 1);
    for (int i = 0;i < n;i++) {
        // cerr << P[i] << " \n"[i == n - 1];
        while (cnt[i] < i) transaction(P[i]), cnt[i]++;
    }
    return;
}

• 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