제출 #829204

#제출 시각아이디문제언어결과실행 시간메모리
829204definitelynotmee비스킷 담기 (IOI20_biscuits)C++17
0 / 100
11 ms4216 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...