Submission #1304041

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304041		thelegendary08	Packing Biscuits (IOI20_biscuits)	C++17	100 / 100	151 ms	174048 KiB

biscuits

#include "biscuits.h"
#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define mp make_pair
#define vi vector<int>
#define f0r(i,n) for(int i = 0; i<n; i++)
#define FOR(i, k, n) for(int i = k; i<n; i++)
#define dout(x) cout<<x<<' '<<#x<<'\n';
#define vout(x) for(auto u : x)cout<<u<<' '; cout<<'\n';
#define vb vector<bool>
#define p2(x) (1LL << (x))
using namespace std;
vi p; 
struct Node{
	int sz, sum; Node *l, *r; 
	Node(int x, int y) : l(NULL), r(NULL), sz(x), sum(y){}
	Node(Node *l, Node *r) : l(l), r(r), sz(0), sum(0){
		if(l)sz+=l->sz,sum+=l->sum;
		if(r)sz+=r->sz,sum+=r->sum;	
	}
	Node(Node *v) : l(v->l), r(v->r), sz(v->sz), sum(v->sum){}
};
Node* update(Node* v, int x){
	// cout<<v->sz<<' '<<x<<'\n';
	if(x==0)return new Node(v); 
	if(v->sum==0)return new Node(v); 
	if(x==v->sz){Node* tmp = new Node(v); tmp->sum = 0; return tmp;}
	if(!v->l){
		// cout<<v->sz<<' '<<v->sum<<'\n';
		v->l = new Node(v->sz/2, v->sum/2), v->r = new Node(v->sz/2, v->sum/2);
	}
	if(x <= (v->sz)/2){
		return new Node(v->l, update(v->r, x)); 	
	}
	else{
		return new Node(update(v->l,x-(v->sz/2)), new Node(v->sz/2,0));
	}
	return v; 
}
long long count_tastiness(long long x, std::vector<long long> a) {
	while(a.size() < 60)a.pb(0); int n = a.size();
	p.resize(n); p[0] = a[0]; FOR(i,1,n)p[i] = p[i-1] + (1LL << i) * a[i]; int mx = p.back(); 
	f0r(i,n)p[i]/=x;  
	Node* root = new Node(1, 1); 
	f0r(i, n){
		Node *newroot = new Node(root, root); 
		// dout(newroot->sum); 
		int del = p2(i+1) - 1 - p[i]; 
		if(del > 0)root = update(newroot, del); else root = newroot; 
		// dout(root->sum);
	}
	return root->sum; 
	return 0;
}

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