Submission #1277814

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277814		stephit	Souvenirs (IOI25_souvenirs)	C++20	4 / 100	1 ms	400 KiB

souvenirs

#include "souvenirs.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long

int cnt[101];
ll p[101];

void buy_souvenirs(int n, long long p0) {
    ll t = p0 - 1;
    // từ t / 2^i -> t / 2^(i-1) co nhieu nhat 2 so

    vector<int> v; ll r;
    auto ask = [&](ll M) -> void {
        auto [vv, rr] = transaction(M);
        for (int i : vv) cnt[i]++;
        v = vv, r = rr;
    };
    
    while (1) {
        ask(t);
        if (v.back() == n - 1) {
            if (v.size() == 1) p[n - 1] = t - r;
            if (v.size() == 2) {
                ll tong = t - r;
                ask(tong / 2);
                p[n - 1] = tong / 2 - r;
                p[n - 2] = tong - p[n - 1];
            }
            break;
        }
        t /= 2;
    }

    while (t < p0 - 1) {
        t *= 2;
        ask(t);
        while (!v.empty() && p[v.back()] > 0) {
            r += p[v.back()];
            v.pop_back();
        }
        if (v.size() == 1) p[v[0]] = t - r;
        if (v.size() == 2) {
            ll tong = t - r;
            ask(tong / 2);
            p[v[1]] = tong / 2 - r;
            p[v[0]] = tong - p[v[1]];
        }
    }

    for (int i = 1; i <= n - 1; i++) {
        for (int j = cnt[i] + 1; j <= i; j++) transaction(p[i]);
    }
}

• 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