Submission #1250628

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

souvenirs

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

#define fi first
#define se second
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long lli;
typedef vector<int> vi;
typedef pair<vi, lli> vil;

lli p[105], q[105], m[105];

void buy_souvenirs(int N, long long P0) {
    memset(p, 0, sizeof p);
    memset(q, 0, sizeof q);
    memset(m, 0, sizeof m);
    int left = 1, right = N - 1, k = 0;
    stack<vil> s;
    p[0] = m[0] = P0;
    while (left <= right) {
        lli c = m[k] - 1;
        vil res = transaction(c);
        for (int t : res.fi) {
            q[t]++;
        }
        c -= res.se;
        while (1) {
            vi v;
            int sz = 0;
            lli all_diffs = 0;
            for (int t : res.fi) {
                if (p[t] == 0) {
                    v.pb(t);
                    sz++;
                    all_diffs += (t - v[0]);
                } else {
                    c -= p[t];
                }
            }
            k = max(k, v[0]);
            if (sz > 1) {
                s.push(mp(v, c));
                m[v[0]] = (c + all_diffs + sz - 1) / sz;
                break;
            }
            p[v[0]] = m[v[0]] = c;
            if (s.empty()) {
                break;
            }
            res = s.top();
            s.pop();
            c = res.se;
        }
        while (p[left] != 0) {
            left++;
        }
        while (p[right] != 0) {
            right--;
        }
        while ((k >= right) || (m[k] == 0)) {
            k--;
        }
    }
    for (int i = 1; i < N; i++) {
        while (q[i] < i) {
            transaction(p[i]);
            q[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