oj.uz

Submission #410314

# Submission time Handle Problem Language Result Execution time Memory
410314 2021-05-22T13:49:04 Z bipartite_matching Packing Biscuits (IOI20_biscuits) C++14
0 / 100
 2 ms 332 KB 
#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) {
	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

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

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 292 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -