#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(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);
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
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);
| ~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
304 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
296 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4072 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
