Submission #1080531

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080531		anango	Packing Biscuits (IOI20_biscuits)	C++17	0 / 100	1072 ms	4408 KiB

biscuits

#include "biscuits.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;
#define cout cerr

const int JFF = 300000;

int flog(int x) {
    //MSB of x
    int ct=0;
    while (x>1) {
        x>>=1;
        ct++;
    }
    return ct;
}

int X;
vector<int> A;
map<pair<int,int>,int> cache;

int solve(int mval, int index) {
    //index is the last relevant index
    //consider that we take this bit
    //then how much do we need from lower bits
    //and thus what is the max we can take from lower bits as well
    //if we don't take the bit, just round down to the power of 2
    if (index==-1) {
        return mval>=0;
    }
    if (mval<0) {
        return 0;
    }
    if (cache.count({mval,index})) {
        return cache[{mval,index}];
    }
    if (mval<(1LL<<index)) {
        return cache[{mval,index}] = solve(mval,index-1);
    }
    int s1 = solve((1LL<<index)-1,index-1);
    //we take this bit
    int req = X;
    int ava = A[index];
    int k;
    if (ava>=req) {
        //take bit for free
        k=(1LL<<index)-1;
    }
    else {
        //req>ava
        int rem = req-ava; //need to fundraise from smaller powers
        int reqsum = rem*(1LL<<index);
        int actualsum = 0;
        for (int i=0; i<index; i++) {
            actualsum+=(1LL<<i)*A[i];
        }
        if (actualsum<reqsum) {
            k=-1; //no sol
        } 
        else {
            int rem_for_prev_indices = actualsum-reqsum;
            k = rem_for_prev_indices/X;
        }
        //assert(k<=((1LL<<fl)-1));
        k=min(k,((1LL<<index)-1));
        cout << "DOING " << mval <<" " << index <<" " << req<<" " << reqsum <<" " << actualsum <<" " << endl;
    }
    int s2 = solve(k,index-1);
    cout << "CHOSEN" <<" " << mval <<" " << index <<" " << k << endl;
    cout << "answered " << mval <<" " << index <<" " << s1 <<" " << s2 << " " << s1+s2 << endl;
    return cache[{mval,index}] = s1+s2;


}

long long count_tastiness(long long x, std::vector<long long> a) {
    cout << "STARTING NEW TEST CASE" << endl;
    cache.clear();
    while (a.size()<62) {
        a.push_back(0);
    }
    A = a;
    X = x;
    int le = ((int)a.size())-1;
    int ans = solve(((1LL<<(le+1))-1), le);
	return ans;
}

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