oj.uz

Submission #804519

# Submission time Handle Problem Language Result Execution time Memory
804519 2023-08-03T09:29:51 Z mousebeaver Cookies (JOI23_cookies) C++14
13 / 100
 5 ms 1620 KB 
#define ll long long
#define INF numeric_limits<ll>::max()/2
#define pll pair<ll, ll>
#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    bool sub1 = true;

    ll n;
    cin>>n;
    vector<ll> a(n);
    for(ll i = 0; i < n; i++)
    {
        cin>>a[i];
        if(a[i] != 1 || n > 500)
        {
            sub1 = false;
        }
    }
    ll m;
    cin>>m;
    vector<ll> b(m);
    for(ll i = 0; i < m; i++)
    {
        cin>>b[i];
    }

    if(sub1)
    {
        //Subtask 1:
        vector<pll> dp(n+1, {INF, -1}); //Number, last
        dp[0] = {0, 0};
        for(ll i = 0; i < n; i++)
        {
            for(ll j = 0; j < m && i+b[j] <= n; j++)
            {
                if(dp[i].first+1 < dp[i+b[j]].first)
                {
                    dp[i+b[j]].first = dp[i].first+1;
                    dp[i+b[j]].second = j;
                }
            }
        }

        if(dp[n].first == INF)
        {
            cout<<-1<<"\n";
        }
        else
        {
            cout<<dp[n].first<<"\n";
            ll k = n;
            ll counter = 1;
            while(k > 0)
            {
                ll box = b[dp[k].second];
                k -= box;
                cout<<box<<" ";
                while(box > 0)
                {
                    cout<<counter<<" ";
                    counter++;
                    box--;
                }
                cout<<"\n";
            }
        }
        return 0;
    }

    //Subtask 2:
    ll sum = 0;
    for(ll i : a)
    {
        sum += i;
    }
    
    if(sum%b[0] != 0 || *max_element(a.begin(), a.end()) > sum/b[0])
    {
        cout<<-1<<"\n";
    }
    else
    {
        vector<vector<ll>> output(sum/b[0], vector<ll> (0));
        priority_queue<pll, vector<pll>, greater<pll>> q; //Contained, index
        for(ll i = 0; i < sum/b[0]; i++)
        {
            q.push({0, i});
        }

        for(ll i = 0; i < n; i++)
        {
            vector<pll> used(0); //Contained, index
            for(ll j = 0; j < a[i]; j++)
            {
                ll c, index;
                tie(c, index) = q.top();
                q.pop();
                used.push_back({c+1, index});
                output[index].push_back(i+1);
            }
            for(pll p : used)
            {
                q.push(p);
            }
        }

        cout<<sum/b[0]<<"\n";
        for(ll i = 0; i < sum/b[0]; i++)
        {
            cout<<b[0]<<" ";
            for(ll j : output[i])
            {
                cout<<j<<" ";
            }
            cout<<"\n";
        }
    }

    return 0;  
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 316 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 324 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 324 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 216 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 0 ms 212 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 1 ms 212 KB Output is correct
27 Correct 0 ms 212 KB Output is correct
28 Correct 1 ms 212 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 324 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 5 ms 1620 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 320 KB Output is correct
14 Correct 0 ms 320 KB Output is correct
15 Correct 1 ms 324 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 3 ms 724 KB Output is correct
19 Correct 4 ms 832 KB Output is correct
20 Correct 3 ms 596 KB Output is correct
21 Correct 2 ms 468 KB Output is correct
22 Correct 2 ms 468 KB Output is correct
23 Correct 1 ms 316 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 320 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 320 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Incorrect 0 ms 212 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 316 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 324 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 324 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 216 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 0 ms 212 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 1 ms 212 KB Output is correct
27 Correct 0 ms 212 KB Output is correct
28 Correct 1 ms 212 KB Output is correct
29 Correct 1 ms 212 KB Output is correct
30 Correct 0 ms 320 KB Output is correct
31 Correct 0 ms 212 KB Output is correct
32 Correct 1 ms 212 KB Output is correct
33 Correct 1 ms 212 KB Output is correct
34 Correct 1 ms 212 KB Output is correct
35 Correct 1 ms 212 KB Output is correct
36 Correct 0 ms 212 KB Output is correct
37 Correct 1 ms 212 KB Output is correct
38 Correct 0 ms 320 KB Output is correct
39 Correct 1 ms 212 KB Output is correct
40 Correct 0 ms 212 KB Output is correct
41 Correct 1 ms 212 KB Output is correct
42 Correct 0 ms 212 KB Output is correct
43 Incorrect 0 ms 212 KB Output isn't correct
44 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 316 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 324 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 324 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 216 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 0 ms 212 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 1 ms 212 KB Output is correct
27 Correct 0 ms 212 KB Output is correct
28 Correct 1 ms 212 KB Output is correct
29 Correct 1 ms 212 KB Output is correct
30 Correct 0 ms 320 KB Output is correct
31 Correct 0 ms 212 KB Output is correct
32 Correct 1 ms 212 KB Output is correct
33 Correct 1 ms 212 KB Output is correct
34 Correct 1 ms 212 KB Output is correct
35 Correct 1 ms 212 KB Output is correct
36 Correct 0 ms 212 KB Output is correct
37 Correct 1 ms 212 KB Output is correct
38 Correct 0 ms 320 KB Output is correct
39 Correct 1 ms 212 KB Output is correct
40 Correct 0 ms 212 KB Output is correct
41 Correct 1 ms 212 KB Output is correct
42 Correct 0 ms 212 KB Output is correct
43 Incorrect 0 ms 212 KB Output isn't correct
44 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 316 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 324 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 324 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 216 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 0 ms 212 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 1 ms 212 KB Output is correct
27 Correct 0 ms 212 KB Output is correct
28 Correct 1 ms 212 KB Output is correct
29 Correct 0 ms 212 KB Output is correct
30 Correct 0 ms 212 KB Output is correct
31 Correct 1 ms 212 KB Output is correct
32 Correct 0 ms 212 KB Output is correct
33 Correct 1 ms 212 KB Output is correct
34 Correct 0 ms 212 KB Output is correct
35 Correct 0 ms 212 KB Output is correct
36 Correct 1 ms 324 KB Output is correct
37 Correct 1 ms 596 KB Output is correct
38 Correct 5 ms 1620 KB Output is correct
39 Correct 1 ms 212 KB Output is correct
40 Correct 0 ms 212 KB Output is correct
41 Correct 0 ms 320 KB Output is correct
42 Correct 0 ms 320 KB Output is correct
43 Correct 1 ms 324 KB Output is correct
44 Correct 1 ms 340 KB Output is correct
45 Correct 0 ms 212 KB Output is correct
46 Correct 3 ms 724 KB Output is correct
47 Correct 4 ms 832 KB Output is correct
48 Correct 3 ms 596 KB Output is correct
49 Correct 2 ms 468 KB Output is correct
50 Correct 2 ms 468 KB Output is correct
51 Correct 1 ms 316 KB Output is correct
52 Correct 1 ms 212 KB Output is correct
53 Correct 0 ms 320 KB Output is correct
54 Correct 0 ms 212 KB Output is correct
55 Correct 1 ms 212 KB Output is correct
56 Correct 1 ms 212 KB Output is correct
57 Correct 1 ms 212 KB Output is correct
58 Correct 1 ms 212 KB Output is correct
59 Correct 0 ms 212 KB Output is correct
60 Correct 1 ms 212 KB Output is correct
61 Correct 0 ms 320 KB Output is correct
62 Correct 1 ms 212 KB Output is correct
63 Correct 0 ms 212 KB Output is correct
64 Correct 1 ms 212 KB Output is correct
65 Correct 0 ms 212 KB Output is correct
66 Incorrect 0 ms 212 KB Output isn't correct
67 Halted 0 ms 0 KB -