Submission #471927

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
471927	2021-09-11T20:29:18 Z	zorz	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	488 ms	20936 KB

jobs

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define MOD 1000000007
#define vi vector<int>
#define pi pair<int, int>
pi a[1000005];
vector<int> last, last_cpy; 
int main()
{
    //freopen("CEOI12_JOBS.in", "r", stdin);
    //freopen("CEOI12_JOBS.out", "w", stdout);
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    LL n, d, m;
    cin >> n >> d >> m; 
    for (int i = 0; i < m; ++i) 
    {
        cin >> a[i].first; 
        a[i].second = i + 1;
    }
    sort(a, a + m); 
    LL l = 1, r = 1E6, mid;
    while (l != r)
    {
        mid = (l + r) / 2; 
        // cout << mid << endl;
        LL i = 0;
        bool flag = true;
        while (i < m && flag)
        {
            for (int j = 1; j <= mid; ++j)
            {
                if (i == m) break; 
                if (i >= mid) last.pb(max(last[i - mid] + 1, a[i].first)); 
                else last.pb(a[i].first); 
                LL delay = last[i] - a[i].first; 
                if (delay > d) 
                {
                    flag = false;
                    break;
                }
                //cout << i << " " << last[i] << endl;
                i++; 
            }
        }
        if (flag) 
        {
            r = mid; 
            last_cpy = last; 
        }
        else l = mid + 1; 
        last.clear(); 
    }
    cout << l << endl;
    LL j = 0; 
    for (int i = 1; i <= n; ++i)
    {
        while (last_cpy[j] == i)
        {
            cout << a[j].second << " ";
            j++; 
        }
        cout << 0 << endl;
    }
    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	40 ms	2636 KB	Output is correct
2	Correct	40 ms	2648 KB	Output is correct
3	Correct	40 ms	2632 KB	Output is correct
4	Correct	44 ms	2536 KB	Output is correct
5	Correct	50 ms	2636 KB	Output is correct
6	Correct	41 ms	2608 KB	Output is correct
7	Correct	41 ms	2536 KB	Output is correct
8	Correct	41 ms	2528 KB	Output is correct
9	Correct	191 ms	2788 KB	Output is correct
10	Correct	191 ms	2908 KB	Output is correct
11	Correct	44 ms	2500 KB	Output is correct
12	Correct	73 ms	4800 KB	Output is correct
13	Correct	115 ms	7084 KB	Output is correct
14	Correct	169 ms	9432 KB	Output is correct
15	Correct	183 ms	11576 KB	Output is correct
16	Correct	250 ms	13868 KB	Output is correct
17	Correct	297 ms	16260 KB	Output is correct
18	Correct	329 ms	18448 KB	Output is correct
19	Correct	488 ms	20936 KB	Output is correct
20	Correct	300 ms	16120 KB	Output is correct