Submission #1070086

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070086		Arapak	Packing Biscuits (IOI20_biscuits)	C++17	0 / 100	1030 ms	348 KiB

biscuits

#include "biscuits.h"
#include "bits/stdc++.h"
using namespace std;

#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;

#ifdef DEBUG
auto& operator<<(auto &os, const pair<auto,auto> &p) {
	return os<<"("<<p.first<<", "<<p.second<<")";
}
auto& operator<<(auto &os, const auto &v) {
	os<<"{";
	for(auto it=begin(v);it!=end(v);++it) {
		if(it != begin(v)) os<<", ";
		os<<(*it);
	}
	return os<<"}";
}

void dbg_out(auto... x) {
	((cerr<<' '<<x), ...) << endl;
}
#define dbg(x...) cerr<<"("<<#x<<"):", dbg_out(x);
#else
#define dbg(...)
#endif
typedef vector<ll> vll;

const ll inf = ll(1e18) + 7;

ll k;

ll num(ll val, vll a) {
	if(val == 0) return inf;
	if(val >= (1LL<<k)) return 0;
	vll needed(k, 0);
	rep(i,0,k)
		if((val>>ll(i)) & 1LL)
			needed[i] = 1;
	ll result = 0;
	while(true) {
		int mini = -1;
		rep(i,0,k) {
			if(needed[i] == 0) continue;
			if(mini == -1 || (a[i] / needed[i]) < (a[mini] / needed[mini]))
				mini = i;
		}
		if(mini == -1) break;
		ll res = a[mini] / needed[mini];
		result += res;
		if(mini == 0) break;
		rep(i,0,k) a[i] -= res * needed[i];
		needed[mini-1] += needed[mini] * 2;
		needed[mini] = 0;
	}
	return result;
}

ll count_tastiness(ll x, vll a) {
	k = sz(a);
	ll res = 0;
	rep(i,0,100007) {
		bool poss = num(i, a) >= x;
		if(poss) dbg(i);
		res += poss;
	}
	return res;
}

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