oj.uz

Submission #836893

# Submission time Handle Problem Language Result Execution time Memory
836893 2023-08-24T16:55:50 Z alvingogo Cookies (JOI23_cookies) C++14
7 / 100
 83 ms 121696 KB 
#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(gd);
    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+1].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 i=0;i<=m;i++){
        for(int j=0;j<bt[i].size();j++){
            if(bt[i][j][s]){
                vector<int> k;
                while(i>0 && j>0){
                    if(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

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+1].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:55:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::bitset<15005> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |         for(int j=0;j<bt[i].size();j++){
      |                     ~^~~~~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 55536 KB Output is correct
2 Correct 22 ms 55484 KB Output is correct
3 Correct 21 ms 55508 KB Output is correct
4 Correct 22 ms 55600 KB Output is correct
5 Correct 23 ms 55512 KB Output is correct
6 Correct 22 ms 55524 KB Output is correct
7 Correct 29 ms 55508 KB Output is correct
8 Correct 23 ms 56456 KB Output is correct
9 Correct 22 ms 55600 KB Output is correct
10 Runtime error 83 ms 121696 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 55544 KB Output is correct
2 Correct 27 ms 55580 KB Output is correct
3 Correct 25 ms 55508 KB Output is correct
4 Correct 23 ms 55576 KB Output is correct
5 Correct 25 ms 56436 KB Output is correct
6 Correct 23 ms 55540 KB Output is correct
7 Correct 24 ms 55500 KB Output is correct
8 Correct 23 ms 56440 KB Output is correct
9 Correct 27 ms 61056 KB Output is correct
10 Correct 48 ms 83344 KB Output is correct
11 Correct 29 ms 55584 KB Output is correct
12 Correct 23 ms 55512 KB Output is correct
13 Correct 28 ms 55500 KB Output is correct
14 Correct 23 ms 55544 KB Output is correct
15 Correct 28 ms 55508 KB Output is correct
16 Correct 24 ms 55636 KB Output is correct
17 Correct 23 ms 55632 KB Output is correct
18 Correct 33 ms 62536 KB Output is correct
19 Correct 45 ms 64896 KB Output is correct
20 Correct 32 ms 56012 KB Output is correct
21 Correct 26 ms 55768 KB Output is correct
22 Correct 28 ms 55772 KB Output is correct
23 Correct 24 ms 55516 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 55508 KB Output is correct
2 Correct 23 ms 55532 KB Output is correct
3 Correct 23 ms 55572 KB Output is correct
4 Correct 24 ms 55596 KB Output is correct
5 Correct 29 ms 55556 KB Output is correct
6 Correct 23 ms 55512 KB Output is correct
7 Correct 22 ms 55532 KB Output is correct
8 Correct 22 ms 55552 KB Output is correct
9 Correct 22 ms 55608 KB Output is correct
10 Correct 23 ms 55520 KB Output is correct
11 Correct 22 ms 55492 KB Output is correct
12 Correct 22 ms 55492 KB Output is correct
13 Correct 22 ms 55536 KB Output is correct
14 Correct 22 ms 55548 KB Output is correct
15 Correct 23 ms 55636 KB Output is correct
16 Correct 22 ms 55508 KB Output is correct
17 Correct 21 ms 55636 KB Output is correct
18 Correct 22 ms 55532 KB Output is correct
19 Correct 23 ms 55600 KB Output is correct
20 Correct 22 ms 55508 KB Output is correct
21 Incorrect 22 ms 55504 KB Too many cookies..
22 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 55536 KB Output is correct
2 Correct 22 ms 55484 KB Output is correct
3 Correct 21 ms 55508 KB Output is correct
4 Correct 22 ms 55600 KB Output is correct
5 Correct 23 ms 55512 KB Output is correct
6 Correct 22 ms 55524 KB Output is correct
7 Correct 29 ms 55508 KB Output is correct
8 Correct 23 ms 56456 KB Output is correct
9 Correct 22 ms 55600 KB Output is correct
10 Runtime error 83 ms 121696 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 55536 KB Output is correct
2 Correct 22 ms 55484 KB Output is correct
3 Correct 21 ms 55508 KB Output is correct
4 Correct 22 ms 55600 KB Output is correct
5 Correct 23 ms 55512 KB Output is correct
6 Correct 22 ms 55524 KB Output is correct
7 Correct 29 ms 55508 KB Output is correct
8 Correct 23 ms 56456 KB Output is correct
9 Correct 22 ms 55600 KB Output is correct
10 Runtime error 83 ms 121696 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 55536 KB Output is correct
2 Correct 22 ms 55484 KB Output is correct
3 Correct 21 ms 55508 KB Output is correct
4 Correct 22 ms 55600 KB Output is correct
5 Correct 23 ms 55512 KB Output is correct
6 Correct 22 ms 55524 KB Output is correct
7 Correct 29 ms 55508 KB Output is correct
8 Correct 23 ms 56456 KB Output is correct
9 Correct 22 ms 55600 KB Output is correct
10 Runtime error 83 ms 121696 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -