Submission #1347346

#	Time	Username	Problem	Language	Result	Execution time	Memory
1347346		MMihalev	Cookies (JOI23_cookies)	C++20	63 / 100	103 ms	8440 KiB

cookies

#include<iostream>
#include<set>
#include<vector>
#include<algorithm>
using namespace std;
const int MAX_N=503;

int n,m;
int a[MAX_N];
int b[MAX_N];

bool state[MAX_N][MAX_N][MAX_N];
bool dp[MAX_N][MAX_N][MAX_N];
int minsum[MAX_N];

vector<int>boxes[MAX_N];
vector<int>box;
void constructans()
{
    random_shuffle(box.begin(),box.end());
    set<pair<int,int>>s;
    for(int i=1;i<=n;i++)s.insert({a[i],i});
    
    int j=0;
    for(int B:box)
    {
        j++;
        vector<int>curbox;
        for(auto [sz,type]:s)curbox.push_back(type);

        for(int i=1;i<=B;i++)
        {
            boxes[j].push_back(curbox.back());
            s.erase({a[curbox.back()]--,curbox.back()});
            if(a[curbox.back()])s.insert({a[curbox.back()],curbox.back()});
            curbox.pop_back();
        }
    }

    cout<<box.size()<<"\n";
    for(int i=1;i<=box.size();i++)
    {
        cout<<boxes[i].size()<<" ";
        for(int x:boxes[i])cout<<x<<" ";
        cout<<"\n";
    }
}

int main ()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    cin>>n;
    int all=0;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        all+=a[i];
    }

    for(int boxes=1;boxes<=all;boxes++)
    {
        for(int i=1;i<=n;i++)
        {
            minsum[boxes]+=min(boxes,a[i]);
        }
    }

    cin>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>b[i];
    }
    sort(b+1,b+m+1);
    reverse(b+1,b+m+1);
    
    dp[0][0][0]=1;

    for(int id=1;id<=m;id++)
    {
        for(int boxes=0;boxes<=all;boxes++)
        {
            for(int sum=0;sum<=all;sum++)
            {
                if(dp[id-1][boxes][sum])
                {
                    dp[id][boxes][sum]=1;
                    state[id][boxes][sum]=0;
                    continue;
                }

                if(boxes && sum>=b[id] && dp[id][boxes-1][sum-b[id]] && sum<=minsum[boxes])
                {
                    dp[id][boxes][sum]=1;
                    state[id][boxes][sum]=1;
                }
            }
        }
    }

    int ans=-1;
    for(int boxes=1;boxes<=all;boxes++)
    {
        if(dp[m][boxes][all])
        {
            ans=boxes;
            break;
        }
    }

    if(ans==-1)
    {
        cout<<-1<<"\n";
        return 0;
    }

    int id=m,boxes=ans,sum=all;

    while(boxes)
    {
        if(state[id][boxes][sum])
        {
            box.push_back(b[id]);
            boxes--;
            sum-=b[id];
        }
        else id--;
    }

    constructans();

    return 0;
}

Compilation message (stderr)

cookies.cpp: In function 'void constructans()':
cookies.cpp:20:19: warning: 'void std::random_shuffle(_RAIter, _RAIter) [with _RAIter = __gnu_cxx::__normal_iterator<int*, vector<int> >]' is deprecated: use 'std::shuffle' instead [-Wdeprecated-declarations]
   20 |     random_shuffle(box.begin(),box.end());
      |     ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:61,
                 from cookies.cpp:4:
/usr/include/c++/13/bits/stl_algo.h:4581:5: note: declared here
 4581 |     random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
      |     ^~~~~~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 0 / 7
• Subtask 3: 12 / 12
• Subtask 4: 45 / 45
• Subtask 5: 0 / 15
• Subtask 6: 0 / 15