Submission #336673

#TimeUsernameProblemLanguageResultExecution timeMemory
336673cheehengPacking Biscuits (IOI20_biscuits)C++14
12 / 100
1079 ms384 KiB
#include "biscuits.h" #include <bits/stdc++.h> using namespace std; long long S = 0; int k = 0; long long b[65]; long long a1[65]; bool boleh1(long long y, long long x){ for(int i = 0; i < k; i ++){ b[i] = a1[i]; } bool boleh = true; for(long long i = 0; i < x; i ++){ long long rem = y; for(int j = k-1; j >= 0; j --){ long long quotient = min(rem>>j, b[j]); b[j] -= quotient; rem -= (quotient << j); } if(rem != 0){ boleh = false; break; } } return boleh; } bool boleh2(long long y, long long x){ for(int i = 0; i < 60; i ++){ b[i] = a1[i]; } for(int i = 59; i >= 0; i --){ if( y&(1LL<<i) ){ long long rem = x<<i; for(int j = min(i, k-1); j >= 0; j --){ long long quotient = min(rem>>j, b[j]); b[j] -= quotient; rem -= (quotient << j); if(rem == 0){break;} } if(rem != 0){ return false; } } } return true; } long long count_tastiness(long long x, std::vector<long long> a) { k = (int)a.size(); memset(a1, 0, sizeof(a1)); for(int i = 0; i < k; i ++){ S += (a[i]<<i); a1[i] = a[i]; } if(x == 1){ for(int i = 0; i < k; i ++){ b[i] = a[i]; } long long ans2 = 1; long long val = 0; long long mult = 1; long long divider = 1; for(int i = 0; i < k; i ++){ val += a[i]*mult; if(val >= x*(2*mult/divider - 1)*divider ){ }else{ ans2 *= 1+(val/divider); val = 0; divider = mult*2; } mult <<= 1; } ans2 *= 1+(val/divider); //printf("ans2=%lld\n", ans2); //assert(ans == ans2); return ans2; } long long ans = 1; for(long long y = 0; y <= S/x;){ bool boleh = boleh2(y, x); //assert(boleh == boleh1(y, x)); if(boleh){ int range = 1; /*for(int i = 1; i < k; i ++){ if( ( y&((1<<i)-1) ) == 0 ){ if(boleh2(y + (1<<i)-1, x)){ range = (1<<i); }else{ y += (1<<i); break; } } }*/ y ++; //ans += range; }else{ long long lsb = y&(-y); y += lsb; y = y/lsb*lsb; } ans += boleh; } return ans; }

Compilation message (stderr)

biscuits.cpp: In function 'long long int count_tastiness(long long int, std::vector<long long int>)':
biscuits.cpp:99:17: warning: unused variable 'range' [-Wunused-variable]
   99 |             int range = 1;
      |                 ^~~~~
#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...