Submission #443764

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
443764	2021-07-12T03:23:31 Z	BackNoob	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	314 ms	20036 KB

jobs

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define mask(i) (1LL << (i))
#define y1 BinhKhung
using namespace std;
const int mxN = 1e6 + 7;
const int mxM = 1e5 + 7;
const int inf = 1e9 + 7;
const ll mod = 1e9 + 7;
const ll infll = 1e18 + 7;
const int offset = 1e5;

int numday , maxday , numjob;
pair<int , int> job[mxN];
vector<int> ans[mxM];

bool ok(int x)
{
    int day = 1;
    for(int i = 1 ; i <= numday ; i++) {
        for(int j = 1 ; j <= x ; j++) {
            if(job[day].fi <= i && i <= job[day].fi + maxday) {
                day++;
                if(day > numjob) return true;
            }
            else break;
        }
    }
    return day > numjob;
    
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen("task.inp" , "r" , stdin);
    //freopen("task.out" , "w" , stdout);
    
    cin >> numday >> maxday >> numjob;

    for(int i = 1 ; i <= numjob ; i++) cin >> job[i].fi;
    for(int i = 1 ; i <= numjob ; i++) job[i].se = i;

    sort(job + 1 , job + 1 + numjob);

    int lo = 1 , hi = numjob;
    while(lo + 1 < hi) {
        int m = (lo + hi) / 2;
        if(ok(m)) hi = m;
        else lo = m;
    }

    int res = 0;

    if(ok(lo)) res = lo;
    else res = hi;

    cout << res << endl;
    int day = 1;
    for(int i = 1 ; i <= numday ; i++) {
        for(int j = 1 ; j <= res ; j++) {
            if(job[day].fi <= i && i <= job[day].fi + maxday) {
                ans[i].push_back(job[day].se);
                day++;
                if(day > numjob) break;
            }
            else break;
        }
        if(day > numjob) break;
    }

    for(int i = 1 ; i <= numday ; i++) {
        for(int j : ans[i]) cout << j << ' ';
        cout << 0 << endl;
    }
    
    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	25 ms	4484 KB	Output is correct
2	Correct	27 ms	4568 KB	Output is correct
3	Correct	33 ms	4468 KB	Output is correct
4	Correct	25 ms	4556 KB	Output is correct
5	Correct	25 ms	4476 KB	Output is correct
6	Correct	25 ms	4524 KB	Output is correct
7	Correct	25 ms	4524 KB	Output is correct
8	Correct	26 ms	4468 KB	Output is correct
9	Correct	42 ms	4724 KB	Output is correct
10	Correct	42 ms	4664 KB	Output is correct
11	Correct	33 ms	4500 KB	Output is correct
12	Correct	66 ms	6512 KB	Output is correct
13	Correct	101 ms	8900 KB	Output is correct
14	Correct	138 ms	11136 KB	Output is correct
15	Correct	165 ms	11936 KB	Output is correct
16	Correct	204 ms	14184 KB	Output is correct
17	Correct	243 ms	17992 KB	Output is correct
18	Correct	270 ms	18636 KB	Output is correct
19	Correct	314 ms	20036 KB	Output is correct
20	Correct	250 ms	17944 KB	Output is correct