Submission #1257911

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257911		Canuc80k	Souvenirs (IOI25_souvenirs)	C++20	28 / 100	5 ms	420 KiB

souvenirs

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;

std::pair<std::vector<int>, long long> transaction(long long M);

ll res[201], cnt[201];
pair<vector<int>, ll> g[201];

void buy_souvenirs(int n, long long p) {
    for (int i = 1; i < n; i ++) res[i] = 1e18;
    res[0] = p;

    ll p2 = 1;
    while (true) {
        auto [v, x] = transaction(p / (1ll << p2));
        for (auto x: v) cnt[x] ++;
        g[v[0]].first = v;
        g[v[0]].second = p / (1ll << p2) - x;
        
        if (v[0] >= n - 2) {
            if (v[0] == n - 1) {
                res[n - 1] = p / (1ll << p2) - x; break;
            }
            if (v[0] == n - 2) {
                if (v.size() == 2) {
                    ll sum = p / (1ll << p2) - x;
                    auto [v, x] = transaction(sum / 2);
                    for (auto x: v) cnt[x] ++;
                    res[n - 1] = sum / 2 - x;
                    res[n - 2] = sum - res[n - 1];
                    break;
                }
                if (v.size() == 1) {
                    res[n - 2] = p / (1ll << p2) - x;
                    auto [v, x] = transaction(res[n - 2] - 1);
                    for (auto x: v) cnt[x] ++;
                    res[n - 1] = res[n - 2] - 1 - x; 
                    break;
                }
            }
        }
        p2 ++;
    }

    // for (int i = 0; i < n; i ++) cout << i << ' ' << cnt[i] << endl;

    ll start = n - 2;
    if (res[n - 2] != (ll)1e18) start --;
    for (int i = start; i >= 1; i --) {
        // cout << "Debug: " << i << endl;
        if (g[i].second != 0) {
            ll price = g[i].second;
            for (auto x: g[i].first) {
                if (x != i) {
                    price -= res[x];
                }
            }
            res[i] = price;
            continue;
        }
        // cout << "Stop: " << 1 << endl;
        ll bound_left = res[i + 1] + 1;
        if (i + 2 < n) bound_left = max(bound_left, res[i + 1] + res[i + 2]);
        ll bound_right = res[i + 1] * 2;
        bound_right = min(bound_right, res[0] - 1);
        
        ll price = bound_right;
        // cout << "Stop: " << 2 << ' ' << bound_right << endl;
        auto [v, x] = transaction(price);
        // cout << "Stop: " << 3 << endl;
        for (auto x: v) cnt[x] ++;
        for (auto y: v) {
            if (y != i) price -= res[y];
        }
        
        price -= x;
        // if (price < 0) cout << bound_left << ' ' << bound_right << endl;
        res[i] = price;
        
        // cout << "Stop: " << 4 << endl;
    }
    
    // for (int i = 1; i < n; i ++)
    // cout << "Res[i]: " << i << ' ' << res[i] << '\n';
for (int i = 1; i < n; i ++)
        for (int j = cnt[i] + 1; j <= i; j ++)
            transaction(res[i]);
}

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