Submission #1252512

#	Time	Username	Problem	Language	Result	Execution time	Memory
1252512		SamAnd	Souvenirs (IOI25_souvenirs)	C++20	100 / 100	12 ms	428 KiB

souvenirs

#include "souvenirs.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N = 102;

int n;
ll p[N];
int q[N];

void rec(vector<int> v, ll s)
{
    while (1)
    {
        assert(!p[v[0]]);
        while (p[v.back()])
        {
            s -= p[v.back()];
            v.pop_back();
        }
        if (sz(v) == 1)
        {
            if (p[v[0] + 1])
            {
                p[v[0]] = s;
                return;
            }
            ll t = s - 1;
            auto u = transaction(t);
            ll ss = t - u.se;
            vector<int> vv = u.fi;
            for (int i = 0; i < sz(vv); ++i)
                ++q[vv[i]];
            rec(vv, ss);
        }
        else
        {
            ll t = s / sz(v);
            if (s % sz(v) == 0)
                --t;
            auto u = transaction(t);
            ll ss = t - u.se;
            vector<int> vv = u.fi;
            for (int i = 0; i < sz(vv); ++i)
                ++q[vv[i]];
            rec(vv, ss);
        }
    }
}

void buy_souvenirs(int N, long long P0)
{
    n = N;
    p[n] = -1;
    rec(vector<int>{0}, P0);
    for (int i = 0; i < n; ++i)
    {
        assert(p[i]);
        while (q[i] < i)
        {
            transaction(p[i]);
            ++q[i];
        }
    }
    return;
}

/*
7
342 88 55 7 6 5 4
*/

• 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