Submission #1278235

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278235		SabaKharebava	Festival (IOI25_festival)	C++20	32 / 100	78 ms	9616 KiB

festival

#include<bits/stdc++.h>

using namespace std;

#define pb push_back

const long long MOD = 9223372036854775807;

long long test(long long a, vector<int> order, vector<int> p, vector<int> t) {
	for (int e : order)
		a = ((a-p[e]) * t[e]) % MOD;
	return a;
}

vector<int> max_coupons(int ra, vector<int> p, vector<int> t) {
	int n = p.size();
	long long a = ra;

	vector<int> order, order1;
	for (int i = 0; i < n; i++) {
		if (t[i] == 1)
			order1.pb(i);
		else
			order.pb(i);
	}

	sort(order.begin(), order.end(), [&](int i, int j) {
		if (t[i] == t[j]) {
			return p[i] < p[j]; 
		} else {
			long long A = -p[i]*t[i]*t[j] - p[j]*t[j];
			long long B = -p[j]*t[i]*t[j] - p[i]*t[i];

			if (A == B)
				return p[i] < p[j];
			return A > B;
		}
	});
	sort(order1.begin(), order1.end(), [&](int i, int j) {
		return p[i] < p[j];
	});

	vector<int> ans;
	long long val = test(a, order, p, t);
	if (val >= 0) {
		ans = order;
		a = val;
	} else {
		vector<bool> used(order.size(), false);
		bool bought;
		while (true) {
			bought = false;
			for (int i = 0; i < order.size(); i++) {
				if (used[i])
					continue;
				else if (a >= p[order[i]]) {
					bought = true;
					a = ((a - p[order[i]]) * t[order[i]]) % MOD;
					ans.pb(order[i]);
					used[i] = true;
					break;
				}
			}

			if (!bought)
				break;
		}
	}
	for (int e : order1) {
		if (a >= p[e]) {
			ans.pb(e);
			a -= p[e];
		}
	}

	return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 12
• Subtask 4: 0 / 15
• Subtask 5: 27 / 27
• Subtask 6: 0 / 16
• Subtask 7: 0 / 18