Submission #307729

#	Time	Username	Problem	Language	Result	Execution time	Memory
307729		CodePlatina	Packing Biscuits (IOI20_biscuits)	C++14	100 / 100	54 ms	1024 KiB

biscuits

#include "biscuits.h"
#include <vector>
#include <algorithm>
#include <utility>
#define pii pair<int, int>
#define piii pair<int, pii>
#define pll pair<long long, long long>
#define plll pair<long long, pll>
#define ff first
#define ss second
#define ee ss.ff
#define rr ss.ss
#include <iostream>

using namespace std;

long long count_tastiness(long long y, vector<long long> a)
{
    int k = a.size();
    vector<long long> b(60); b[0] = a[0];
    for(int i = 1; i < 60; ++i) b[i] = b[i - 1] + (i < k ? (a[i] << i) : 0);
    for(int i = 0; i < 60; ++i) b[i] /= y;
    for(int i = 0; i < 60; ++i) if(b[i] >= (1ll << i + 1)) b[i] = (1ll << i + 1) - 1;

    vector<pll> V; V.push_back({(1ll << 61) - 1, 1});
    for(int i = 59; i >= 0; --i)
    {
        vector<pll> _V;
        for(auto x : V)
        {
            x.ff = min(x.ff, b[i]);
            if(x.ff >= (1ll << i)) _V.push_back({(1ll << i) - 1, x.ss}), _V.push_back({x.ff - (1ll << i), x.ss});
            else _V.push_back(x);
        }
        sort(_V.begin(), _V.end());
        V.clear();
        for(auto x : _V)
        {
            if(V.size() && V.back().ff == x.ff) V.back().ss += x.ss;
            else V.push_back(x);
        }
//        cout << i << endl;
//        for(auto x : V) cout << x.ff << ' ' << x.ss << endl;
    }

    return V[0].ss;
}

Compilation message (stderr)

biscuits.cpp: In function 'long long int count_tastiness(long long int, std::vector<long long int>)':
biscuits.cpp:23:54: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   23 |     for(int i = 0; i < 60; ++i) if(b[i] >= (1ll << i + 1)) b[i] = (1ll << i + 1) - 1;
      |                                                    ~~^~~
biscuits.cpp:23:77: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   23 |     for(int i = 0; i < 60; ++i) if(b[i] >= (1ll << i + 1)) b[i] = (1ll << i + 1) - 1;
      |                                                                           ~~^~~

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