oj.uz

Submission #836864

# Submission time Handle Problem Language Result Execution time Memory
836864 2023-08-24T16:27:04 Z alvingogo Cookies (JOI23_cookies) C++14
19 / 100
 51 ms 84456 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];
    }
    sort(b.begin()+1,b.end(),greater<int>());
    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 && bt[i-1][j][s-b[j]]){
                        k.push_back(b[j]);
                        s-=b[j];
                        i--;
                    }
                    else{
                        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:46:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::bitset<15005> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         for(int j=0;j+1<bt[i].size();j++){
      |                     ~~~^~~~~~~~~~~~~
cookies.cpp:54:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::bitset<15005> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |         for(int j=1;j<bt[i+1].size();j++){
      |                     ~^~~~~~~~~~~~~~~
cookies.cpp:59:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::bitset<15005> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |         for(int j=0;j<bt[i].size();j++){
      |                     ~^~~~~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 83668 KB Output is correct
2 Correct 46 ms 83700 KB Output is correct
3 Correct 43 ms 83672 KB Output is correct
4 Correct 33 ms 69836 KB Output is correct
5 Correct 40 ms 83656 KB Output is correct
6 Correct 35 ms 74428 KB Output is correct
7 Correct 33 ms 72540 KB Output is correct
8 Correct 45 ms 83792 KB Output is correct
9 Correct 23 ms 56020 KB Output is correct
10 Correct 39 ms 84456 KB Output is correct
11 Correct 32 ms 70196 KB Output is correct
12 Correct 41 ms 83048 KB Output is correct
13 Incorrect 28 ms 63296 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 62940 KB Output is correct
2 Correct 42 ms 83724 KB Output is correct
3 Correct 41 ms 83700 KB Output is correct
4 Correct 33 ms 69828 KB Output is correct
5 Correct 42 ms 83732 KB Output is correct
6 Correct 24 ms 56088 KB Output is correct
7 Correct 41 ms 83688 KB Output is correct
8 Correct 42 ms 83704 KB Output is correct
9 Correct 44 ms 83772 KB Output is correct
10 Correct 47 ms 83972 KB Output is correct
11 Correct 45 ms 83660 KB Output is correct
12 Correct 34 ms 69900 KB Output is correct
13 Correct 35 ms 69896 KB Output is correct
14 Correct 30 ms 65276 KB Output is correct
15 Correct 33 ms 69792 KB Output is correct
16 Correct 26 ms 58760 KB Output is correct
17 Correct 25 ms 58736 KB Output is correct
18 Correct 36 ms 62984 KB Output is correct
19 Correct 33 ms 65324 KB Output is correct
20 Correct 27 ms 56372 KB Output is correct
21 Correct 25 ms 56196 KB Output is correct
22 Correct 25 ms 56312 KB Output is correct
23 Correct 25 ms 56124 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 83652 KB Output is correct
2 Correct 27 ms 62900 KB Output is correct
3 Correct 44 ms 83660 KB Output is correct
4 Correct 42 ms 83708 KB Output is correct
5 Correct 34 ms 69860 KB Output is correct
6 Correct 51 ms 83548 KB Output is correct
7 Correct 36 ms 74420 KB Output is correct
8 Correct 34 ms 72636 KB Output is correct
9 Correct 43 ms 83752 KB Output is correct
10 Correct 43 ms 83764 KB Output is correct
11 Correct 33 ms 69788 KB Output is correct
12 Correct 35 ms 69836 KB Output is correct
13 Correct 30 ms 65300 KB Output is correct
14 Correct 33 ms 69844 KB Output is correct
15 Correct 41 ms 83660 KB Output is correct
16 Correct 35 ms 74340 KB Output is correct
17 Correct 41 ms 83660 KB Output is correct
18 Correct 34 ms 69816 KB Output is correct
19 Correct 37 ms 76796 KB Output is correct
20 Correct 39 ms 76720 KB Output is correct
21 Correct 34 ms 72564 KB Output is correct
22 Correct 37 ms 72532 KB Output is correct
23 Correct 34 ms 72524 KB Output is correct
24 Correct 37 ms 76752 KB Output is correct
25 Correct 33 ms 69788 KB Output is correct
26 Correct 33 ms 69824 KB Output is correct
27 Correct 34 ms 72624 KB Output is correct
28 Correct 37 ms 79020 KB Output is correct
29 Correct 33 ms 69780 KB Output is correct
30 Correct 32 ms 69768 KB Output is correct
31 Correct 39 ms 79632 KB Output is correct
32 Correct 33 ms 69828 KB Output is correct
33 Correct 33 ms 69844 KB Output is correct
34 Correct 34 ms 71732 KB Output is correct
35 Correct 38 ms 78540 KB Output is correct
36 Correct 40 ms 83536 KB Output is correct
37 Correct 35 ms 69800 KB Output is correct

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 83668 KB Output is correct
2 Correct 46 ms 83700 KB Output is correct
3 Correct 43 ms 83672 KB Output is correct
4 Correct 33 ms 69836 KB Output is correct
5 Correct 40 ms 83656 KB Output is correct
6 Correct 35 ms 74428 KB Output is correct
7 Correct 33 ms 72540 KB Output is correct
8 Correct 45 ms 83792 KB Output is correct
9 Correct 23 ms 56020 KB Output is correct
10 Correct 39 ms 84456 KB Output is correct
11 Correct 32 ms 70196 KB Output is correct
12 Correct 41 ms 83048 KB Output is correct
13 Incorrect 28 ms 63296 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 83668 KB Output is correct
2 Correct 46 ms 83700 KB Output is correct
3 Correct 43 ms 83672 KB Output is correct
4 Correct 33 ms 69836 KB Output is correct
5 Correct 40 ms 83656 KB Output is correct
6 Correct 35 ms 74428 KB Output is correct
7 Correct 33 ms 72540 KB Output is correct
8 Correct 45 ms 83792 KB Output is correct
9 Correct 23 ms 56020 KB Output is correct
10 Correct 39 ms 84456 KB Output is correct
11 Correct 32 ms 70196 KB Output is correct
12 Correct 41 ms 83048 KB Output is correct
13 Incorrect 28 ms 63296 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 83668 KB Output is correct
2 Correct 46 ms 83700 KB Output is correct
3 Correct 43 ms 83672 KB Output is correct
4 Correct 33 ms 69836 KB Output is correct
5 Correct 40 ms 83656 KB Output is correct
6 Correct 35 ms 74428 KB Output is correct
7 Correct 33 ms 72540 KB Output is correct
8 Correct 45 ms 83792 KB Output is correct
9 Correct 23 ms 56020 KB Output is correct
10 Correct 39 ms 84456 KB Output is correct
11 Correct 32 ms 70196 KB Output is correct
12 Correct 41 ms 83048 KB Output is correct
13 Incorrect 28 ms 63296 KB Output isn't correct
14 Halted 0 ms 0 KB -