Submission #1070767

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070767		andrei_iorgulescu	Packing Biscuits (IOI20_biscuits)	C++14	100 / 100	30 ms	1460 KiB

biscuits

#include <bits/stdc++.h>
#include "biscuits.h"
#warning That's not FB, that's my FB

using namespace std;

#define int long long

int count_tastiness(int x, vector<int> a)
{
    vector<int> sp(60);
    while (a.size() < 60)
        a.push_back(0);
    sp[0] = a[0];
    for (int i = 1; i < 60; i++)
        sp[i] = sp[i - 1] + (1ll << i) * a[i];
    for (int i = 0; i < 60; i++)
        sp[i] /= x;
    for (int i = 0; i < 60; i++)
        sp[i] = min(sp[i], (1ll << (i + 1)) - 1);
    vector<vector<int>> dp(60);
    vector<vector<int>> s(60);
    for (int i = 59; i >= 0; i--)
    {
        s[i].push_back(sp[i]);
        sort(s[i].begin(), s[i].end());
        vector<int> ns;
        for (auto it : s[i])
            if (ns.empty() or it != ns.back())
                ns.push_back(it);
        s[i] = ns;
        /*if (i <= 4)
        {
            cout << i << " kkk ";
            for (auto it : s[i])
            {
                cout << it << ' ';
            }
            cout << endl;
        }*/
        dp[i].resize(s[i].size());
        if (i == 0)
            continue;
        for (auto it : s[i])
        {
            if (it - (1ll << i) >= 0 and it - (1ll << i) < sp[i - 1])
                s[i - 1].push_back(it - (1ll << i));
            if (it < sp[i - 1])
                s[i - 1].push_back(it);
        }
    }
    for (int j = 0; j < dp[0].size(); j++)
        dp[0][j] = 1 + s[0][j];
    for (int i = 1; i < 60; i++)
    {
        int pant = -1, pant2 = -1;
        for (int j = 0; j < dp[i].size(); j++)
        {
            while (pant + 1 < s[i - 1].size() and s[i][j] - (1ll << i) >= s[i - 1][pant + 1])
                pant++;
            while (pant2 + 1 < s[i - 1].size() and s[i][j] >= s[i - 1][pant2 + 1])
                pant2++;
            if (pant != -1)
                dp[i][j] += dp[i - 1][pant];
            if (pant2 != -1)
                dp[i][j] += dp[i - 1][pant2];
            /*if (i <= 4)
            {
                cout << i << ' ' << j << ' ' << dp[i][j] << endl;
            }*/
        }
    }
    return dp[59].back();
}

Compilation message (stderr)

biscuits.cpp:3:2: warning: #warning That's not FB, that's my FB [-Wcpp]
    3 | #warning That's not FB, that's my FB
      |  ^~~~~~~
biscuits.cpp: In function 'long long int count_tastiness(long long int, std::vector<long long int>)':
biscuits.cpp:52:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     for (int j = 0; j < dp[0].size(); j++)
      |                     ~~^~~~~~~~~~~~~~
biscuits.cpp:57:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         for (int j = 0; j < dp[i].size(); j++)
      |                         ~~^~~~~~~~~~~~~~
biscuits.cpp:59:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |             while (pant + 1 < s[i - 1].size() and s[i][j] - (1ll << i) >= s[i - 1][pant + 1])
      |                    ~~~~~~~~~^~~~~~~~~~~~~~~~~
biscuits.cpp:61:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |             while (pant2 + 1 < s[i - 1].size() and s[i][j] >= s[i - 1][pant2 + 1])
      |                    ~~~~~~~~~~^~~~~~~~~~~~~~~~~

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