Submission #1257938

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257938		Canuc80k	Souvenirs (IOI25_souvenirs)	C++20	7 / 100	11 ms	412 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 n;
ll res[201], cnt[201];

void guess(ll price) {
    auto [v, x] = transaction(price);
    for (auto x: v) cnt[x] ++;
    price -= x;
    
    for (int i = v.size() - 1; i >= 1; i --) {
        if (res[v[i]] != 1e18) {price -= res[v[i]]; continue;}
        ll rem = 0; for (int j = 0; j < i; j ++) rem += (v[j] - v[i]);
        guess((price - rem) / (i + 1));
        price -= res[v[i]];
    }
    res[v[0]] = price;

    ll nxt = v[0] + 1; 
    while (nxt != n && res[nxt] != 1e18) nxt ++;
    if (nxt == n && res[n - 1] != 1e18) return;
    guess(res[nxt - 1] - 1);
}

void buy_souvenirs(int n, long long p) {
    ::n = n;
    res[0] = p; for (int i = 1; i < n; i ++) res[i] = 1e18;
    guess(res[0] - 1);
    for (int i = 1; i < n; i ++)
        for (int j = cnt[i] + 1; j <= i; j ++)
            transaction(res[i]);

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

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