Submission #836909

#	Time	Username	Problem	Language	Result	Execution time	Memory
836909		alvingogo	Cookies (JOI23_cookies)	C++14	100 / 100	155 ms	234940 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];
    }
    reverse(b.begin()+1,b.end());
    vector<vector<bitset<gd> > > bt(m+1);
    vector<bitset<gd> > lp(gd+1);
    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(1);
    bt[0][0][0]=1;
    for(int i=0;i<m;i++){
        bt[i+1].resize(s/(b[i+1])+1);
        for(int j=0;j<bt[i].size();j++){
            bt[i+1][j]|=bt[i][j];
        }
        for(int j=1;j<bt[i+1].size();j++){
            bt[i+1][j]|=(bt[i+1][j-1]<<b[i+1])&lp[j];
        }
    }
    for(int j=0;j<gd;j++){
        for(int i=0;i<=m;i++){
            if(j<bt[i].size() && bt[i][j][s]){
                vector<int> k;
                while(i>0 && j>0){
                    if(j<bt[i-1].size() && bt[i-1][j][s]){
                        i--;
                    }
                    else{
                        k.push_back(b[i]);
                        s-=b[i];
                        j--;
                    }
                }
                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:47:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::bitset<15005> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |         for(int j=0;j<bt[i].size();j++){
      |                     ~^~~~~~~~~~~~~
cookies.cpp:50:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::bitset<15005> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |         for(int j=1;j<bt[i+1].size();j++){
      |                     ~^~~~~~~~~~~~~~~
cookies.cpp:56:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::bitset<15005> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |             if(j<bt[i].size() && bt[i][j][s]){
      |                ~^~~~~~~~~~~~~
cookies.cpp:59:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::bitset<15005> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |                     if(j<bt[i-1].size() && bt[i-1][j][s]){
      |                        ~^~~~~~~~~~~~~~~

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