Submission #836877

#	Time	Username	Problem	Language	Result	Execution time	Memory
836877		alvingogo	Cookies (JOI23_cookies)	C++14	13 / 100	129 ms	244384 KiB

cookies

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;

int main(){
    AquA;
    int n;
    cin >> n;
    vector<int> a(n);
    int s=0;
    const int gd=15005;
    vector<int> c(gd);
    for(int i=0;i<n;i++){
        cin >> a[i];
        c[a[i]]++;
        s+=a[i];
    }
    for(int i=gd-2;i>=1;i--){
        c[i]+=c[i+1];
    }
    for(int i=2;i<gd;i++){
        c[i]+=c[i-1];
    }
    int m;
    cin >> m;
    vector<int> b(m+1);
    for(int i=1;i<=m;i++){
        cin >> b[i];
    }
    vector<vector<bitset<gd> > > bt(gd+1);
    vector<bitset<gd> > lp(gd);
    for(int i=1;i<gd;i++){
        lp[i]|=lp[i-1];
        for(int j=c[i-1]+1;j<=c[i];j++){
            lp[i][j]=1;
        }
    }
    bt[0].resize(m+1);
    bt[0][0][0]=1;
    for(int i=0;i<gd;i++){
        for(int j=0;j+1<bt[i].size();j++){
            bt[i][j+1]|=bt[i][j];
        }
        int cnt=0;
        for(int j=1;j<=m && (i+1)*b[j]<gd;j++){
            cnt=j;
        }
        bt[i+1].resize(cnt+1);
        for(int j=1;j<bt[i+1].size();j++){
            bt[i+1][j]|=(bt[i][j]<<b[j])&lp[i+1];
        }
    }
    for(int i=0;i<gd;i++){
        for(int j=0;j<bt[i].size();j++){
            if(bt[i][j][s]){
                vector<int> k;
                while(i>0 && j>0){
                    if(i>0 && s-b[j]>=0 && bt[i-1][j][s-b[j]]){
                        k.push_back(b[j]);
                        s-=b[j];
                        i--;
                    }
                    else{
                        j--;
                    }
                }
                assert(i==0);
                p_q<pair<int,int> > pq;
                for(int f=0;f<n;f++){
                    pq.push({a[f],f});
                }
                cout << k.size() << "\n";
                for(auto h:k){
                    vector<pair<int,int> > d;
                    cout << h << ' ';
                    for(int p=0;p<h;p++){
                        d.push_back(pq.top());
                        pq.pop();
                    }
                    for(auto z:d){
                        pq.push({z.fs-1,z.sc});
                        cout << z.sc+1 << " ";
                    }
                    cout << "\n";
                }
                return 0;
            }
        }
    }
    cout << -1 << "\n";
    return 0;
}

Compilation message (stderr)

cookies.cpp: In function 'int main()':
cookies.cpp:45:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::bitset<15005> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         for(int j=0;j+1<bt[i].size();j++){
      |                     ~~~^~~~~~~~~~~~~
cookies.cpp:53:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::bitset<15005> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         for(int j=1;j<bt[i+1].size();j++){
      |                     ~^~~~~~~~~~~~~~~
cookies.cpp:58:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::bitset<15005> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |         for(int j=0;j<bt[i].size();j++){
      |                     ~^~~~~~~~~~~~~

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