Submission #410326

#	Time	Username	Problem	Language	Result	Execution time	Memory
410326		bipartite_matching	Packing Biscuits (IOI20_biscuits)	C++14	100 / 100	65 ms	1308 KiB

biscuits

#include <bits/stdc++.h>
//#include <unordered_map>


#define forint(i, N) for (long long i = 0; i < (N); i++)

using namespace std;

typedef long long ll;

vector<ll> sum(61, 0);

unordered_map<ll, ll> m;

long long count(long long x, vector<long long>& a, ll max_y) {
	// returns how many y <= max_y that are OK

	//cerr << "hello - " << max_y << endl;
	if (m[max_y] > 0) {
		return m[max_y];
	}
	if (max_y == 0) {
		m[0] = 1;
		return 1;
	} 
	if (max_y == 1) {
		if (a[0] >= x) {
			m[1] = 2;
			return 2;
		}
		else {
			m[1] = 1;
			return 1;
		}
	}

	int i = 0;
	while ((1ll << i) < max_y) {
		i++;
		//cerr << max_y << " ja " << (1ll <<i) << endl;
	}

	//(2^(i-1) < max_y << (2^i)
	if (max_y == (1ll << i)) {
		if (max_y <= sum[i] / x) {
			m[max_y] = count(x, a, max_y - 1) + 1;
			return m[max_y];
		}
		else {
			m[max_y] = count(x, a, max_y - 1);
			return m[max_y];
		}
	}

	if (sum[i-1]/x < (1ll << (i - 1))) {
		m[max_y] = count(x, a, (1ll << (i - 1)));
		return m[max_y];
	}

	// ((1 << (i - 1)) + y) * x < s[i-1]
	// ((1 << (i - 1)) + y) < s[i-1]/x
	// y < s[i-1]/x - (1 << (i - 1))
	ll min_v = min(max_y - (1ll << (i - 1)), sum[i-1]/x - (1ll << (i - 1)));

	m[max_y] = count(x, a, (1ll << (i - 1))) + count(x, a, min_v) - 1;                                                       
	return m[max_y];


}

long long count_tastiness(long long x, vector<long long> a) {
  	m.clear();
  	
	int k = a.size();

	sum[0] = a[0];

	for (int i = 1; i < k; i++) {
		sum[i] = sum[i - 1] + (a[i] << i);
	}
	for (int i = k; i < sum.size(); i++) {
		sum[i] = sum[i - 1];
	}

	return count(x, a, (ll)1e18);

}

Compilation message (stderr)

biscuits.cpp: In function 'long long int count_tastiness(long long int, std::vector<long long int>)':
biscuits.cpp:81:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |  for (int i = k; i < sum.size(); i++) {
      |                  ~~^~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 21 / 21
• Subtask 4: 35 / 35
• Subtask 5: 23 / 23