Submission #829195

#	Time	Username	Problem	Language	Result	Execution time	Memory
829195		definitelynotmee	Packing Biscuits (IOI20_biscuits)	C++17	0 / 100	2 ms	952 KiB

biscuits

#include "biscuits.h"
//#include"grader.cpp"
#include<bits/stdc++.h>
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using pii = pair<int,int>;
const ll INFL = 2e18;
using pll = pair<ll,ll>;

struct node{
	node* l, *r;
	ll ct, limit; // maior cara copiado;

	node(ll a = 0, ll b = 0, node* ll = nullptr, node* rr = nullptr){
		l = ll;
		r = rr;
		ct = a;
		limit = b;
	}

	ll getcount(int bit, ll curlimit){
		if(bit == -1){
			return ct;
		}
		if(curlimit == (1ll<<bit)-1)
			return ct;
		if(ct == 0)
			return 0;
		if(bool(curlimit&(1ll<<bit))){
			return l->ct+r->getcount(bit-1,min(curlimit%(1ll<<bit), limit));
		}
		return l->getcount(bit-1, min(curlimit%(1ll<<bit), limit));
	}

};

long long count_tastiness(long long x, std::vector<long long> a) {
	a.resize(5,0);

	int k = a.size();

	vector<ll> ct(k);

	ct[0] = a[0];

	for(int i = 1; i < k; i++){
		ct[i] = a[i]*(1ll<<i)+ct[i-1];
	}

	node* l = new node, *r = new node;
	*l = node(1,0);
	*r = node(0,0);

	for(int i = 0; i < k; i++){
		if((1ll<<i)*x >= INFL)
			break;

		node* newl = new node;
		node* newr = new node;

		*newl = node(l->ct+r->ct,(1ll<<i)-1,l,r);

		ll limit = ct[i]-(1ll<<i)*x;
		
		// cerr << i << ":\n";

		// cerr << "limit = " << limit << '\n';
		if(limit < 0){
			*newr = node(0,0,l,r);
		} else {
			limit /= x;
			limit = min(limit,(1ll<<i)-1);
			// cerr << "->" << limit << '\n';
			if(limit&(1ll<<i-1)){
				// cerr << "=> " << l->ct << ' ' << r->getcount(i-1,limit%(1ll<<i-1)) << '\n';
				*newr = node(l->ct + r->getcount(i-1,limit%(1ll<<i-1)), limit,l,r);
			} else *newr = node(l->getcount(i-1,limit), limit,l,r);
		}

		l = newl;
		r = newr;

		// cerr << "resp = "<< ' ' << l->ct << ' ' << r->ct << '\n';
	}


	return l->ct + r->ct;
	
}

Compilation message (stderr)

biscuits.cpp: In function 'long long int count_tastiness(long long int, std::vector<long long int>)':
biscuits.cpp:77:20: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   77 |    if(limit&(1ll<<i-1)){
      |                   ~^~
biscuits.cpp:79:55: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   79 |     *newr = node(l->ct + r->getcount(i-1,limit%(1ll<<i-1)), limit,l,r);
      |                                                      ~^~

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