Submission #1021467

#	Time	Username	Problem	Language	Result	Execution time	Memory
1021467		j_vdd16	Packing Biscuits (IOI20_biscuits)	C++17	9 / 100	1086 ms	215484 KiB

biscuits

#include <algorithm>
#include <bitset>
#include <cstdint>
#include <cstring>
#include <iostream>
#include <limits.h>
#include <math.h>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

#define int long long
#define ll long long
#define loop(X, N) for(int X = 0; X < (N); X++)
#define all(V) V.begin(), V.end()
#define rall(V) V.rbegin(), V.rend()

using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;


int count_tastiness(int x, vi a)
{
	constexpr int N = 60;
	while (a.size() < N)
		a.push_back(0);

	vi pref(N, 0);
	pref[0] = a[0];
	for (int i = 1; i < N; i++) {
		a[i] *= (1LL << i);
		pref[i] = pref[i - 1] + a[i];
	}

	map<int, int> values = { {0, 1} };
	for (int bit = N - 1; bit >= 0; bit--)
	{
		map<int, int> nextValues;
		for (auto [sub, posCount] : values)
		{
			nextValues[max(0LL, sub - a[bit])] += posCount; 

			int count = pref[bit] - sub;
			if (count / (1LL << bit) >= x)
				nextValues[max(0LL, sub + x * (1LL << bit) - a[bit])] += posCount;
		}

		swap(values, nextValues);
	}

	
	/*vector<tuple<int, int, int>> values = {{0, 0, 1LL << N}};
	for (int bit = N - 1; bit >= 0; bit--)
	{
		vector<tuple<int, int, int>> nextValues;
		for (auto [sub, l, r] : values)
		{
			sub = max(0LL, sub);
			int count = pref[bit] - sub;
			int m = (l + r) / 2;

			nextValues.push_back({ sub - a[bit], l, m });
			
			if (count / (1LL << bit) >= x)
				nextValues.push_back({ sub + x * (1LL << bit) - a[bit], m, r});
		}

		swap(values, nextValues);
	}*/
	
	int result = 0;
	for (auto [sub, posCount] : values)
		result += posCount;

	return result;
}

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