Submission #489126

#	Time	Username	Problem	Language	Result	Execution time	Memory
489126		ak2006	Job Scheduling (CEOI12_jobs)	C++14	70 / 100	854 ms	65544 KiB

jobs

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vb = vector<bool>;
using vvb = vector<vb>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vc = vector<char>;
using vvc = vector<vc>;
using vs = vector<string>;
const ll mod = 1e9 + 7,inf = 1e18;
#define pb push_back
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
void setIO()
{
    fast;
}
int main()
{
    setIO();
    int t,d,m;
    cin>>t>>d>>m;
    vvi jobs(m,vi(2));
    for (int i = 0;i<m;i++)cin>>jobs[i][0],jobs[i][1] = i + 1;
    sort(jobs.begin(),jobs.end());
    int l = 1,r = m,ans = 1;
    vvi out;
    while (l <= r){
        int mid = (l + r)/2;
        bool is = true;
        int pos = 0,day = 1;
        vvi cur(t);
        while (day <= t and pos <= m){
            for (int mach = 0;mach < mid;mach++){
                if (pos == m)break;
                if (jobs[pos][0] + d < day){
                    is = false;
                    break;
                }
                if (jobs[pos][0] > day)break;
                cur[day - 1].pb(jobs[pos][1]);
                pos++;
            }   
            if (!is)break;
            day++;
        }
        if (is and pos == m){
            ans = mid;
            r = mid - 1;
            out = cur;
        }
        else l = mid + 1;
    }
    cout<<ans<<"\n";
    for (auto it:out){
        for (auto it2:it)cout<<it2<<" ";
        cout<<0<<"\n";
    }
    return 0;
}

• Subtask 1: 70 / 100