Submission #622366

#	Time	Username	Problem	Language	Result	Execution time	Memory
622366		8e7	Packing Biscuits (IOI20_biscuits)	C++17	0 / 100	147 ms	7752 KiB

biscuits

//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r){
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define lb __int128
#define maxn 100005
#define pii pair<int, int>
#define ff first
#define ss second
#include "biscuits.h"

vector<lb> f, sum;

lb getcnt(lb v, int k) {
	if (v < 0) return 0;
	if (k < 0) return 1;
	if (v>>k) {
		return (k ? sum[k-1] : 1) + getcnt(min(v - ((v>>k)<<k), f[k]), k-1);
	} else {
		return getcnt(v, k-1);
	}
}

lb ans[200005];
long long count_tastiness(long long x, std::vector<long long> a) {
	for (int i = 0;i < 60;i++) a.push_back(0);
	int k = a.size();
	for (int i = 0;i < k-1;i++) {
		ll d = max(0LL, ((a[i] - x)/2)*2);
		a[i] -= d;
		a[i+1] += d/2;
	}
	pary(a.begin(), a.end());
	f.clear(), sum.clear();
	f.resize(k, 0);
	sum.resize(k, 0);
	
	for (int i = 0;i < k;i++) {
		lb tot = 0;	
		for (int j = i-1;j >= 0;j--) {
			tot <<= 1;
			tot += a[j];
		}
		tot = min(tot, tot + (((lb)(a[i] - x))<<i));
		if (tot < 0) tot = -1;
		else tot = tot / x;
		f[i] = tot;
	}
	//pary(f.begin(), f.end());
	ans[0] = 0;
	int siz = 1;
	for (int i = 0;i < k;i++) {
		int s = siz;
		for (int j = 0;j < s;j++) {
			if (ans[j] <= f[i]) {
				ans[siz++] = ans[j] + (((lb)1)<<i);
			} else {
				break;
			}
		}
	}
	return siz;
}
/*

1
1 40
1000

*/

Compilation message (stderr)

biscuits.cpp: In function 'long long int count_tastiness(long long int, std::vector<long long int>)':
biscuits.cpp:13:19: warning: statement has no effect [-Wunused-value]
   13 | #define pary(...) 0
      |                   ^
biscuits.cpp:44:2: note: in expansion of macro 'pary'
   44 |  pary(a.begin(), a.end());
      |  ^~~~

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