Submission #1251051

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251051		a1exeyy	Souvenirs (IOI25_souvenirs)	C++20	100 / 100	12 ms	420 KiB

souvenirs

#include <bits/stdc++.h>
#include "souvenirs.h"

using namespace std;
using ll = long long;

vector<int> tr;
vector<ll> vl;
int n;

int solve(int r, ll k) {
    auto [vec, sm] = transaction(k);
    sm = k - sm;
    for (auto i : vec) tr[i]--;
    int f = 1;
    for (int i = 1; i < vec.size(); i++) f &= vl[vec[i]] != -1;
    int i = vec[0];
    if (f) {
        vl[i] = sm;
        for (int j : vec) if (j != i) vl[i] -= vl[j];
        if (i == r - 1) return i;
        solve(r, vl[i] - 1);
    } else {
        /*int ln = 1;
        for (int i = 1; i < vec.size(); i++) {
            if (vec[i] != vec[i - 1] + 1) break;
            ln++;
        }*/
        while (vec.size()) {
            if (vec.back() < r) break;
            int j = vec.back();
            vec.pop_back();
            sm -= vl[j];
        }
        while (vec.size() > 1) {
            ll nk = sm / vec.size();
            r = solve(r, nk);
            while (vec.size()) {
                if (vec.back() < r) break;
                int j = vec.back();
                vec.pop_back();
                sm -= vl[j];
            }
        }
        vl[i] = sm;
        if (i + 1 < r) {
            solve(r, vl[i] - 1);
        }
    }
    return i;
}

void buy_souvenirs(int N, ll P0) {
    n = N;
    tr.resize(N);
    vl.assign(N, -1);
    for (int i = 0; i < n; i++) tr[i] = i;
    vl[0] = P0;
    solve(n, P0 - 1);
    for (int i = 0; i < n; i++) for (; tr[i] > 0; tr[i]--) transaction(vl[i]);
}

• 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