Submission #773210

#	Time	Username	Problem	Language	Result	Execution time	Memory
773210		cadmiumsky	Packing Biscuits (IOI20_biscuits)	C++17	100 / 100	56 ms	1392 KiB

biscuits

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define all(x) (x).begin(),(x).end()
using namespace std;

using ll = long long;
using ld = long double;

#define int ll
#define sz(x) ((int)(x).size())

using pii = pair<int,int>;
using tii = tuple<int,int,int>;

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

const int nmax = 60 + 2;

int k = 0;
vector<ll> a;

vector<ll> nxt;
ll x;
 
unordered_map<ll, ll, custom_hash> dp[nmax]; 
 
 ll bkt(int p, int accum) {
  if(p > k && accum < x) return 1;
  if(dp[p].count(accum)) return dp[p][accum];
  return dp[p][accum] = bkt(p + 1, (a[p] + accum) / 2) + (a[p] + accum >= x? bkt(p + 1, (a[p] + accum - x) / 2) : 0);
}

ll basedkt(int p, int limit) {
  if(p == -1) return 1;
  limit = min({limit, (1LL << p + 1) - 1, a[p]});
  if(dp[p].count(limit)) return dp[p][limit];
  if((1LL << p) <= limit) dp[p][limit] += basedkt(p - 1, limit - (1LL << p));
  dp[p][limit] += basedkt(p - 1, limit);
  return dp[p][limit];
}

long long count_tastiness(long long XXX, std::vector<long long> AAA) {
  x = XXX;
  a = AAA;
  k = sz(a);
  while(sz(a) < nmax) a.emplace_back(0);
  int prv = nmax;
  nxt.resize(nmax);
  
  auto tmp = a;
  
  for(int i = 0; i < sz(a); i++) {
    a[i] *= (1LL << i);
  }
  for(int i = 1; i < sz(a); i++) a[i] += a[i - 1];
  for(auto &b : a) b /= x;
  
  for(int i = 0; i < nmax; i++) dp[i].clear();
  
  int val = a.back();
  
  return basedkt(sz(a) - 1, a.back());
  
  
}
#undef int 

/**
      Anul asta se da centroid.
-- Surse oficiale
*/

Compilation message (stderr)

biscuits.cpp: In function 'll basedkt(ll, ll)':
biscuits.cpp:48:33: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   48 |   limit = min({limit, (1LL << p + 1) - 1, a[p]});
      |                               ~~^~~
biscuits.cpp: In function 'long long int count_tastiness(long long int, std::vector<long long int>)':
biscuits.cpp:60:7: warning: unused variable 'prv' [-Wunused-variable]
   60 |   int prv = nmax;
      |       ^~~
biscuits.cpp:73:7: warning: unused variable 'val' [-Wunused-variable]
   73 |   int val = a.back();
      |       ^~~

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 21 / 21
• Subtask 4: 35 / 35
• Subtask 5: 23 / 23