oj.uz

Submission #807175

# Submission time Handle Problem Language Result Execution time Memory
807175 2023-08-04T14:28:01 Z Arturgo Cookies (JOI23_cookies) C++14
6 / 100
 73 ms 55680 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAX_COOKIES = 15000 + 1;
using bits = bitset<MAX_COOKIES>;

int nbTypes, nbBoites, nbCookies;
vector<int> tailles;

int profil[MAX_COOKIES], cumul[MAX_COOKIES];

priority_queue<pair<int, int>> nbs;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    bits zeroes, ones;
    ones = ~zeroes;
    
    cin >> nbTypes;
    
    for(int iType = 0;iType < nbTypes;iType++) {
        int nb;
        cin >> nb;
        nbs.push({nb, iType + 1});
        
        nbCookies += nb;
        for(int iDiff = 0;iDiff < nb;iDiff++) {
            profil[iDiff]++;
        }
    }
    
    for(int iCookie = 0;iCookie < nbCookies;iCookie++) {
        cumul[iCookie + 1] = cumul[iCookie] + profil[iCookie];
    }
    
    cin >> nbBoites;
    for(int iBoite = 0;iBoite < nbBoites;iBoite++) {
        int taille;
        cin >> taille;
        tailles.push_back(taille);
    }
    
    reverse(tailles.begin(), tailles.end());
    
    // iBoite, k, somme
    vector<vector<bits>> dyn;
    
    int minBoites = nbCookies + 1;
    int boiteOpt = 0;
    
    for(int iBoite = 0;iBoite < nbBoites;iBoite++) {
        vector<bits> curCouche;
        
        bits premLigne;
        premLigne[0] = 1;
        curCouche.push_back(premLigne);
        
        for(int k = 1;k * tailles[iBoite] <= nbCookies;k++) {
            bits curLigne = curCouche.back() << tailles[iBoite];
            
            if(!dyn.empty() && k < (int)dyn.back().size())
                curLigne |= dyn.back()[k];

            if(curLigne[nbCookies] && k < minBoites) {
                minBoites = k;
                boiteOpt = iBoite;
            }
            
            bits mask = ones;
            mask >>= cumul[k] + 1;
            mask <<= cumul[k] + 1;
            
            curLigne = curLigne & ~mask;
            curCouche.push_back(curLigne);
        }
        
        dyn.push_back(curCouche);
    }
    
    if(minBoites > nbCookies) {
        cout << -1 << endl;
        return 0;
    }
    
    cout << minBoites << endl;
    
    // reconstruct the sizes
    
    int curBoite = boiteOpt;
    int curK = minBoites;
    int curSomme = nbCookies;
    
    vector<int> optTailles;
    
    while(curK != 0) {
        while(tailles[curBoite] <= curSomme && dyn[curBoite][curK - 1][curSomme - tailles[curBoite]]) {
            optTailles.push_back(tailles[curBoite]);
            curSomme -= tailles[curBoite];
            curK--;
        }
        curBoite--;
    }
    
    for(int taille : optTailles) {
        cout << taille << " ";
        
        vector<pair<int, int>> to_insert;
        for(int iElem = 0;iElem < taille;iElem++) {
            pair<int, int> p = nbs.top();
            nbs.pop();
            cout << p.second << " ";
            
            p.first--;
            if(p.first) {
                to_insert.push_back(p);
            }
        }
        
        for(pair<int, int> p : to_insert) {
            nbs.push(p);
        }
        
        cout << endl;
    }
    
    return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 2 ms 2216 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 9 ms 9176 KB Output is correct
11 Correct 1 ms 1236 KB Output is correct
12 Correct 5 ms 4624 KB Output is correct
13 Correct 2 ms 1796 KB Output is correct
14 Correct 2 ms 1492 KB Output is correct
15 Correct 2 ms 1620 KB Output is correct
16 Correct 2 ms 1484 KB Output is correct
17 Correct 1 ms 876 KB Output is correct
18 Correct 2 ms 1672 KB Output is correct
19 Correct 1 ms 468 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 2 ms 1364 KB Output is correct
22 Correct 4 ms 4404 KB Output is correct
23 Correct 3 ms 3512 KB Output is correct
24 Correct 2 ms 2476 KB Output is correct
25 Correct 2 ms 2476 KB Output is correct
26 Correct 1 ms 716 KB Output is correct
27 Correct 1 ms 596 KB Output is correct
28 Correct 1 ms 1108 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 2 ms 2216 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 3 ms 2216 KB Output is correct
9 Correct 14 ms 11496 KB Output is correct
10 Correct 73 ms 55680 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Runtime error 1 ms 468 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Runtime error 1 ms 468 KB Execution killed with signal 6
14 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 2 ms 2216 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 9 ms 9176 KB Output is correct
11 Correct 1 ms 1236 KB Output is correct
12 Correct 5 ms 4624 KB Output is correct
13 Correct 2 ms 1796 KB Output is correct
14 Correct 2 ms 1492 KB Output is correct
15 Correct 2 ms 1620 KB Output is correct
16 Correct 2 ms 1484 KB Output is correct
17 Correct 1 ms 876 KB Output is correct
18 Correct 2 ms 1672 KB Output is correct
19 Correct 1 ms 468 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 2 ms 1364 KB Output is correct
22 Correct 4 ms 4404 KB Output is correct
23 Correct 3 ms 3512 KB Output is correct
24 Correct 2 ms 2476 KB Output is correct
25 Correct 2 ms 2476 KB Output is correct
26 Correct 1 ms 716 KB Output is correct
27 Correct 1 ms 596 KB Output is correct
28 Correct 1 ms 1108 KB Output is correct
29 Correct 0 ms 340 KB Output is correct
30 Correct 0 ms 340 KB Output is correct
31 Correct 0 ms 212 KB Output is correct
32 Correct 0 ms 340 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Correct 0 ms 340 KB Output is correct
35 Correct 0 ms 340 KB Output is correct
36 Correct 0 ms 340 KB Output is correct
37 Correct 1 ms 340 KB Output is correct
38 Correct 0 ms 340 KB Output is correct
39 Correct 0 ms 340 KB Output is correct
40 Correct 0 ms 340 KB Output is correct
41 Runtime error 1 ms 468 KB Execution killed with signal 6
42 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 2 ms 2216 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 9 ms 9176 KB Output is correct
11 Correct 1 ms 1236 KB Output is correct
12 Correct 5 ms 4624 KB Output is correct
13 Correct 2 ms 1796 KB Output is correct
14 Correct 2 ms 1492 KB Output is correct
15 Correct 2 ms 1620 KB Output is correct
16 Correct 2 ms 1484 KB Output is correct
17 Correct 1 ms 876 KB Output is correct
18 Correct 2 ms 1672 KB Output is correct
19 Correct 1 ms 468 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 2 ms 1364 KB Output is correct
22 Correct 4 ms 4404 KB Output is correct
23 Correct 3 ms 3512 KB Output is correct
24 Correct 2 ms 2476 KB Output is correct
25 Correct 2 ms 2476 KB Output is correct
26 Correct 1 ms 716 KB Output is correct
27 Correct 1 ms 596 KB Output is correct
28 Correct 1 ms 1108 KB Output is correct
29 Correct 0 ms 340 KB Output is correct
30 Correct 0 ms 340 KB Output is correct
31 Correct 0 ms 212 KB Output is correct
32 Correct 0 ms 340 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Correct 0 ms 340 KB Output is correct
35 Correct 0 ms 340 KB Output is correct
36 Correct 0 ms 340 KB Output is correct
37 Correct 1 ms 340 KB Output is correct
38 Correct 0 ms 340 KB Output is correct
39 Correct 0 ms 340 KB Output is correct
40 Correct 0 ms 340 KB Output is correct
41 Runtime error 1 ms 468 KB Execution killed with signal 6
42 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 2 ms 2216 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 9 ms 9176 KB Output is correct
11 Correct 1 ms 1236 KB Output is correct
12 Correct 5 ms 4624 KB Output is correct
13 Correct 2 ms 1796 KB Output is correct
14 Correct 2 ms 1492 KB Output is correct
15 Correct 2 ms 1620 KB Output is correct
16 Correct 2 ms 1484 KB Output is correct
17 Correct 1 ms 876 KB Output is correct
18 Correct 2 ms 1672 KB Output is correct
19 Correct 1 ms 468 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 2 ms 1364 KB Output is correct
22 Correct 4 ms 4404 KB Output is correct
23 Correct 3 ms 3512 KB Output is correct
24 Correct 2 ms 2476 KB Output is correct
25 Correct 2 ms 2476 KB Output is correct
26 Correct 1 ms 716 KB Output is correct
27 Correct 1 ms 596 KB Output is correct
28 Correct 1 ms 1108 KB Output is correct
29 Correct 0 ms 340 KB Output is correct
30 Correct 0 ms 340 KB Output is correct
31 Correct 0 ms 340 KB Output is correct
32 Correct 0 ms 340 KB Output is correct
33 Correct 2 ms 2216 KB Output is correct
34 Correct 0 ms 340 KB Output is correct
35 Correct 0 ms 340 KB Output is correct
36 Correct 3 ms 2216 KB Output is correct
37 Correct 14 ms 11496 KB Output is correct
38 Correct 73 ms 55680 KB Output is correct
39 Correct 1 ms 340 KB Output is correct
40 Correct 0 ms 340 KB Output is correct
41 Correct 0 ms 340 KB Output is correct
42 Runtime error 1 ms 468 KB Execution killed with signal 6
43 Halted 0 ms 0 KB -