Submission #466064

#	Time	Username	Problem	Language	Result	Execution time	Memory
466064		blue	Packing Biscuits (IOI20_biscuits)	C++17	12 / 100	3 ms	332 KiB

biscuits

#include "biscuits.h"
#include <vector>
#include <iostream>
using namespace std;

//x = number of people (p)
//y = tastiness of each bag (i)

long long pow2[64];

long long x;

void tle_assert(bool b)
{
    if(!b) while(1);
}

long long solve(vector<long long> B)
{

    if((int)B.size() == 1) return 1;

    // cerr << "solve ";
    // for(long long b:B) cerr << b << ' ';
    // cerr << '\n';

    //Case 1 - no transformation
    long long ans1 = 1;
    for(int i = 0; i+1 < (int)B.size(); i++)
        ans1 *= 2;

    // cerr << "ans1 = " << ans1 << '\n';

    //Case 2
    long long ans2;
    int posX1 = -1;
    long long val = 0;
    for(int i = (int)B.size() - 1; i >= 0; i--)
    {
        val += pow2[i] * B[i];
        if(x <= 4'000'000'000'000'000'000LL / pow2[(int)B.size() - 1] && val >= x * pow2[(int)B.size() - 1])
        {
            posX1 = i;
            break;
        }
    }
        // if(B[i] >= x+1)
        // {
        //     posX1 = i;
        //     break;
        // }

    if(posX1 == -1)
        ans2 = 0;
    else
    {
        B.resize(posX1+1);
        B[posX1] = 0;
        ans2 = solve(B);
    }

    return ans1 + ans2;
}

long long count_tastiness(long long x1, vector<long long> a)
{
    // cerr << "\n\n\n\n\n";
    pow2[0] = 1;
    for(int e = 1; e < 64; e++)
        pow2[e] = (pow2[e-1] * 2);

    x = x1;

    while((int)a.size() < 62) a.push_back(0);
	int k = (int)a.size();

    for(int i = 0; i+1 < k; i++)
    {
        long long M;

        if(a[i] <= x+1)
            M = 0;
        else if(a[i] % 2 == x % 2)
            M = (a[i] - x);
        else
            M = (a[i] - x) - 1;

        a[i] -= M;
        a[i+1] += M/2;
    }

    // for(int i = 0; i < 10; i++) cerr << a[i] << ' ';
    // cerr << '\n';

    vector<long long> B;

    long long res = 1;
    for(int i = 0; i < k; i++)
    {
        B.push_back(a[i]);
        if(a[i] < x)
        {
            res *= solve(B);
            B.clear();
        }
    }

    return res;
}

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