oj.uz

Submission #829204

# Submission time Handle Problem Language Result Execution time Memory
829204 2023-08-18T06:25:48 Z definitelynotmee Packing Biscuits (IOI20_biscuits) C++17
0 / 100
 11 ms 4216 KB 
#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(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));
	}


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

long long count_tastiness(long long x, std::vector<long long> a) {
	a.resize(60,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);

	node* nullnode = new node;
	*nullnode = node(0,0,nullnode,nullnode);

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

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

		*newl = node(0,(1ll<<i)-1,l,r);
		*newr = node(0,0,l,r);
		ll limit = ct[i]-(1ll<<i)*x;
		
		// cerr << i << ":\n";

		// cerr << "limit = " << limit << '\n';
		if(limit < 0){
			*newr = node(0,0,nullnode,nullnode);
		} else {
			newr->limit = limit/x;
		}
		newl->process(i);
		newr->process(i);

		l = newl;
		r = newr;

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


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

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 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 340 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 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 4216 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 340 KB Output isn't correct
2 Halted 0 ms 0 KB -