Submission #772779

#	Time	Username	Problem	Language	Result	Execution time	Memory
772779		cadmiumsky	Packing Biscuits (IOI20_biscuits)	C++17	33 / 100	922 ms	19944 KiB

biscuits

#include <bits/stdc++.h>
#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;
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 bkt2(int p, int accum) {
  if(p >= k && accum < x) return 1;
  return bkt(p + 1, (a[p] + accum) / 2) + (a[p] + accum >= x? bkt(p + 1, (a[p] + accum - x) / 2) : 0);
}

long long count_tastiness(long long XXX, std::vector<long long> AAA) {
  x = XXX;
  a = AAA;
  k = sz(a);
  if(x <= 1e4) {
    for(int i = 0; i < nmax; i++) dp[i].clear();
    while(sz(a) < nmax) a.emplace_back(0);
    return bkt(0, 0);
  }
  else { return bkt2(0, 0); }
}
#undef int 

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

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