Submission #471927

#	Time	Username	Problem	Language	Result	Execution time	Memory
471927		zorz	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	488 ms	20936 KiB

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 / 100