Submission #1251685

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251685		OttoTheDino	Souvenirs (IOI25_souvenirs)	C++20	100 / 100	12 ms	424 KiB

souvenirs

#include "souvenirs.h"
#include <iostream>
#include <utility>
#include <vector>
using namespace std;

#define rep(i,s,e)		for (int i = s; i <= e; ++i)
#define rrep(i,s,e)		for (int i = s; i >= e; --i)
#define pb			push_back
#define pf			push_front
#define fi			first
#define se			second
#define all(a)			a.begin(), a.end()
#define len(a)			(int)a.size()
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;

const int mx = 100;
ll sum[mx+1], val[mx+1], c[mx+1], d, n;
vi who[mx+1];

int buy (ll p) {
    pair<vi, ll> res = transaction (p);
    int f = res.fi [0];
    sum[f] = p - res.se;
    who[f] = res.fi;
    for (int el : res.fi) ++c[el];
    return f;
}

void go (int i) {
    while (true) {
	int k = 0;
	ll s = 0;
	for (int j : who[i]) {
	    k += val[j] > 0;
	    s += val[j];
	}
	if (k == len(who[i])-1) val[i] = sum[i] - s;

	if (val[i]) {
	    if (i == n-1-d) {
		++d;
		return;
	    }
	    else go ( buy ( val[i]-1 ) );
	}
	else go ( buy ( (sum[i]-s)/(len(who[i])-k) ) );
    }
}

void buy_souvenirs(int N, long long P0) {

    n = N;

    who[0].pb(0);
    sum[0] = P0;
    val[0] = P0;

    go (0);

    rep (i,1,N-1) while (c[i] < i) buy (val[i]);

    return;
}

• 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