제출 #388466

#제출 시각아이디문제언어결과실행 시간메모리
388466JimmyZJX비스킷 담기 (IOI20_biscuits)C++14
0 / 100
7 ms400 KiB
#include <iostream> #include <fstream> #include <algorithm> #include <cstring> #include <climits> #include <cassert> #include <tuple> #include <queue> #include <stack> #include <vector> #include <map> #include <set> #include <string> using namespace std; typedef long long LL; typedef vector<int> Vi; typedef vector<LL> VL; typedef vector<bool> Vb; typedef vector<vector<int>> Vii; #define MAXP 61 #define forR(i, n) for (int i = 0; i < (n); i++) VL preSum(MAXP); LL count(LL x, VL a, int p) { // [ 0, 2^p ) ++ [ 2^p , 2^(p+1) ) if (p == 0) { return a[0] >= x ? 2 : 1; } LL count_before_p = count(x, a, p - 1); if (a[p] >= x) { return 2 * count_before_p; } else if (p > 0 && a[p] + (preSum[p - 1] >> p) >= x) { LL rest = (x - a[p]) * (1LL << p); int c; for (c = p - 1; c >= 0 && rest > 0; c--) { LL cnt = min(a[c], rest / (1LL << c)); rest -= cnt * (1LL << c); a[c] -= cnt; } assert(rest == 0); LL chooseP = count(x, a, c); return count_before_p + chooseP; } else { return count_before_p; } } LL count_tastiness(LL x, VL a) { int k = a.size(); a.resize(MAXP); LL c = 0; forR(i, MAXP) { a[i] += c; c = 0; if (a[i] > x) { c = (a[i] - x) / 2; a[i] -= c * 2; } } forR(i, MAXP) { preSum[i] = i > 0 ? preSum[i - 1] : 0; preSum[i] += ((LL)1 << i) * a[i]; } //VL counts(MAXP + 1); // counts[p]: [ 0 , 2^p ) //counts[0] = 1; //for (int p = 1; p <= MAXP; p++) { // if (a[p] >= x) { // return 2 * counts[p - 1]; // } else if (a[p] + (preSum[p - 1] >> p) >= x) { // LL rest = (x - a[p]) * (1LL << p); // int c; for (c = p - 1; c >= 0; c--) { // LL cnt = min(a[c], rest / (1LL << c)); // rest -= cnt * (1LL << c); // a[c] -= cnt; // if (rest == 0) break; // } // assert(rest == 0); // LL chooseP = 0; // auto preSumBackup = preSum; // { // forR(i, p) { // preSum[i] = i > 0 ? preSum[i - 1] : 0; // preSum[i] += ((LL)1 << i) * a[i]; // } // chooseP = count(x, a, p - 1); // } // preSum = preSumBackup; // return count_before_p + chooseP; // } else { // return counts[p - 1]; // } //} return count(x, a, MAXP - 1); } #ifdef TEST_LOCAL int main() { LL res; res = count_tastiness(3, VL{ 5,2,1 }); res = count_tastiness(2, VL{ 2,1,2 }); return 0; } #endif

컴파일 시 표준 에러 (stderr) 메시지

biscuits.cpp: In function 'LL count_tastiness(LL, VL)':
biscuits.cpp:58:6: warning: unused variable 'k' [-Wunused-variable]
   58 |  int k = a.size();
      |      ^
#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...