#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){
// Pega contagem de caras dentro do nó da trie contando que já pegamos o bit "bit"
// e a partir daqui só podemos escolher numeros menores que curlimit
if(bit == 0){
return ct;
}
curlimit = min(curlimit,limit);
if(curlimit == (1ll<<bit)-1) // podemos pegar tudo
return ct;
if(curlimit&(1ll<<bit-1)){
curlimit-=(1ll<<bit-1);
return l->ct+r->getcount(bit-1, curlimit);
}
return l->getcount(bit-1, curlimit);
}
void process(int bit){
if(limit == (1ll<<bit)-1) {// podemos pegar tudo
// cerr << '1' << '\n';
ct = l->ct + r->ct;
return;
}
if(limit&(1ll<<bit-1)){
// cerr << '2' << '\n';
ct = l->ct+r->getcount(bit-1, limit-(1ll<<bit-1));
return;
}
// cerr << '3' << '\n';
ct = l->getcount(bit-1, 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(ct[0] >= x,0);
node* nullnode = new node;
*nullnode = node(0,0,nullnode,nullnode);
for(int i = 1; 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 << limit << '\n';
if(limit < 0){
*newr = node(0,(1ll<<i)-1, nullnode, nullnode);
} else {
limit/=x;
// cerr << "->"<< limit << '\n';
limit = min(limit,(1ll<<i)-1);
newr->limit = limit;
}
newl->process(i);
newr->process(i);
l = newl;
r = newr;
// cerr << "resp = "<< ' ' << l->ct << ' ' << r->ct << '\n';
}
return l->ct + r->ct;
}
Compilation message
biscuits.cpp: In member function 'll node::getcount(int, ll)':
biscuits.cpp:38:24: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
38 | if(curlimit&(1ll<<bit-1)){
| ~~~^~
biscuits.cpp:39:23: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
39 | curlimit-=(1ll<<bit-1);
| ~~~^~
biscuits.cpp: In member function 'void node::process(int)':
biscuits.cpp:51:21: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
51 | if(limit&(1ll<<bit-1)){
| ~~~^~
biscuits.cpp:53:49: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
53 | ct = l->ct+r->getcount(bit-1, limit-(1ll<<bit-1));
| ~~~^~
/usr/bin/ld: /tmp/ccpW1XGt.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccrrj4Vr.o:biscuits.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
