Submission #1314402

#	Time	Username	Problem	Language	Result	Execution time	Memory
1314402		Cyanberry	Festival (IOI25_festival)	C++20	Compilation error	0 ms	0 KiB

festival

#include "festival.h"
#include <bits/stdc++.h>
#define cost first
#define ind second
#define ll long long
using namespace std;
ll c = 0;
vector<ll> pref1{0};

ll bs(ll money) {
	if (money >= pref1.back()) {
		return pref1.size()-1;
	}
	ll l = 0, r = pref1.size();
	while(r-l > 1) {
		// cout<<l<<' '<<r<<'\n';
		ll m = (r+l)/2;
		if (pref1[m] <= money) {
			l = m;
		} else {
			r = m;
		}
	}
	return l;
} 

std::vector<int> max_coupons(int A, std::vector<int> P, std::vector<int> T) {
	pref1 = {0};
	c = 0;
	vector<vector<pair<ll, int>>> options(4, vector<pair<ll, int>>{});
	for (int i = 0; i < P.size(); ++i) {
		options[T[i]-1].push_back({P[i], i});
	}
	for (int i = 0; i < 4; ++i) sort(options[i].begin(), options[i].end());
	for (int i = 0; i < options[0].size(); ++i) {
		pref1.push_back(pref1.back() + options[0][i].first);
		++c;
	}
	int t2 = options[1].size(), t3 = options[2].size(), t4 = options[3].size();
	pair<ll, vector<int>> dp[t2+1][t3+1][t4+1];
	for (int i = 0; i < t2; ++i) {
		for (int j = 0; j < t3; ++j) {
			for (int k = 0; k < t4; ++k) {
				dp[i][j][k] = {-1, vector<int>{}};
			}
		}
	}
	dp[0][0][0] = {A, vector<int>{}};
	for (int i = 0; i <= t2; ++i) {
		for (int j = 0; j <= t3; ++j) {
			for (int k = 0; k <= t4; ++k) {
				if (dp[i][j][k].first < 0) continue;
				dp[i][j][k] = min(dp[i][j][k], 4000000000ll);
				vector<int> adding = dp[i][j][k].second;
				if (i != t2) {
					if ((dp[i][j][k].first - options[1][i].cost) * 2 > dp[i+1][j][k].first) {
						dp[i+1][j][k] = {(dp[i][j][k].first - options[1][i].cost) * 2, adding};
						dp[i+1][j][k].second.push_back(options[1][i].ind);
					}
				}
				if (j != t3) {
					if ((dp[i][j][k].first - options[2][j].cost) * 3 > dp[i][j+1][k].first) {
						dp[i][j+1][k] = {(dp[i][j][k].first - options[2][j].cost) * 3, adding};
						dp[i][j+1][k].second.push_back(options[2][j].ind);
					}
				}
				if (k != t4) {
					if ((dp[i][j][k].first - options[3][k].cost) * 4 > dp[i][j][k+1].first) {
						dp[i][j][k+1] = {(dp[i][j][k].first - options[3][k].cost) * 4, adding};
						dp[i][j][k+1].second.push_back(options[3][k].ind);
					}
				}
				cerr<<i<<' '<<j<<' '<<k<<' '<<dp[i][j][k].first<<'\n';
			}
		}
	}
	ll a, b, o, d;
	vector<int> ret;
	for (ll i = 0; i <= t2; ++i) {
		for (ll j = 0; j <= t3; ++j) {
			for (ll k = 0; k <= t4; ++k) {
				if (dp[i][j][k].first == -1) continue;
				ll n = i + j + k;
				if (dp[i][j][k].first >= pref1.back()) {
					ret = dp[i][j][k].second;
					for (ll l = 0; l < c; ++l) {
						ret.push_back(options[0][l].ind);
					}
					continue;
				}
				ll _c = bs(dp[i][j][k].first);
				if (ret.size() < n + _c) {
					ret = dp[i][j][k].second;
					for (ll l = 0; l < _c; ++l) {
						ret.push_back(options[0][l].ind);
					}
				}
			}
		}
	}
	
	return ret;
}

std::vector<int> brutality(int A, std::vector<int> P, std::vector<int> T) {
	pref1 = {0};
	c = 0;
	vector<vector<pair<ll, int>>> options(4, vector<pair<ll, int>>{});
	for (int i = 0; i < P.size(); ++i) {
		options[T[i]-1].push_back({P[i], i});
	}
	for (int i = 0; i < 4; ++i) sort(options[i].begin(), options[i].end());
	for (int i = 0; i < options[0].size(); ++i) {
		pref1.push_back(pref1.back() + options[0][i].first);
		++c;
	}
	int t2 = options[1].size();
	vector<int> ret;
	ll best1s = bs(A), loc = 0, score = bs(A), running = A;
	for (int i = 0; i < t2; ++i) {
		if (running > 2e9) {
			loc = t2;
			score = t2;
			best1s = P.size() - t2;
			break;
		}
		running = (running - options[1][i].cost) * 2;
		// cout<<i<<' '<<running<<' '<<options[1][i].cost<<'\n';
		if (running < 0) break;
		int ones = bs(running);
		if (i + ones > score) {
			best1s = ones;
			loc = i+1;
			score = i + ones + 1;
		}
	}
	for (int i = 0; i < loc; ++i) {
		ret.push_back(options[1][i].ind);
	}
	for (int i = 0; i < best1s; ++i) {
		ret.push_back(options[0][i].ind);
	}
	return ret;
}

Compilation message (stderr)

festival.cpp: In function 'std::vector<int> max_coupons(int, std::vector<int>, std::vector<int>)':
festival.cpp:53:50: error: no matching function for call to 'min(std::pair<long long int, std::vector<int> >&, long long int)'
   53 |                                 dp[i][j][k] = min(dp[i][j][k], 4000000000ll);
      |                                               ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/13/vector:62,
                 from festival.h:1,
                 from festival.cpp:1:
/usr/include/c++/13/bits/stl_algobase.h:233:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  233 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/13/bits/stl_algobase.h:233:5: note:   template argument deduction/substitution failed:
festival.cpp:53:50: note:   deduced conflicting types for parameter 'const _Tp' ('std::pair<long long int, std::vector<int> >' and 'long long int')
   53 |                                 dp[i][j][k] = min(dp[i][j][k], 4000000000ll);
      |                                               ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algobase.h:281:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  281 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/13/bits/stl_algobase.h:281:5: note:   template argument deduction/substitution failed:
festival.cpp:53:50: note:   deduced conflicting types for parameter 'const _Tp' ('std::pair<long long int, std::vector<int> >' and 'long long int')
   53 |                                 dp[i][j][k] = min(dp[i][j][k], 4000000000ll);
      |                                               ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:61,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
                 from festival.cpp:2:
/usr/include/c++/13/bits/stl_algo.h:5775:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(initializer_list<_Tp>)'
 5775 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/13/bits/stl_algo.h:5775:5: note:   template argument deduction/substitution failed:
festival.cpp:53:50: note:   'std::pair<long long int, std::vector<int> >' is not derived from 'std::initializer_list<_Tp>'
   53 |                                 dp[i][j][k] = min(dp[i][j][k], 4000000000ll);
      |                                               ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algo.h:5785:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(initializer_list<_Tp>, _Compare)'
 5785 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/13/bits/stl_algo.h:5785:5: note:   template argument deduction/substitution failed:
festival.cpp:53:50: note:   'std::pair<long long int, std::vector<int> >' is not derived from 'std::initializer_list<_Tp>'
   53 |                                 dp[i][j][k] = min(dp[i][j][k], 4000000000ll);
      |                                               ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~