Submission #713440

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
713440	2023-03-22T02:57:08 Z	magikrap	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	506 ms	13708 KB

jobs

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <cmath>
#include <iomanip>

#define ll long long

using namespace std;

int N, D, M;
pair<int, int> arr[1000000];

bool check (int val) {
    //cout << "val: " << val << endl;
    int index = 1;
    for (int day = 1; day <= N; day++) {
        int max = index + val;
        for (int i = index; i < max && i <= M; i++) {
            //cout << "day: " << day << " index: " << index << " i: " << i << " arr[i].first: " << arr[i].first << " arr[i].second: " << arr[i].second << endl;
            if (arr[i].first > day) {
                break;
            } else if (arr[i].first + D < day) {
                return false;
            }
            index++;
        }

    }
    if (index >= M) {
        return true;
    } else {
        return false;
    }
}

void printAns (int val) {
    int index = 1;
    for (int day = 1; day <= N; day++) {
        for (int i = index; i < index + val && i <= M; i++) {
            cout << arr[i].second << " ";
        }
        index += val;
        cout << "0" << endl;
    }
}

int main() {
    cin >> N >> D >> M;
    for (int i = 1; i <= M; i++) {
        cin >> arr[i].first;
        arr[i].second = i;
    }
    sort(arr+1, arr + M+1, [](pair<int, int> a, pair<int, int> b) {
        return a.first < b.first;
    });
    // cout << "arr: " << endl;
    // for (int i = 1; i <= M; i++) {
    //     cout << arr[i].first << " " << arr[i].second << endl;
    // }
    int low = 1;
    int high = 1e7;
    while (low < high) {
        int mid = (low + high) / 2;
        if (check(mid)) {
            high = mid;
        } else {
            low = mid + 1;
        }
    }
    cout << low << endl;
    printAns(low);
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	42 ms	1616 KB	Output is correct
2	Correct	44 ms	1588 KB	Output is correct
3	Correct	47 ms	1696 KB	Output is correct
4	Correct	40 ms	1612 KB	Output is correct
5	Correct	41 ms	1572 KB	Output is correct
6	Correct	38 ms	1620 KB	Output is correct
7	Correct	40 ms	1620 KB	Output is correct
8	Correct	42 ms	1680 KB	Output is correct
9	Correct	143 ms	1840 KB	Output is correct
10	Correct	149 ms	1824 KB	Output is correct
11	Correct	37 ms	1600 KB	Output is correct
12	Correct	69 ms	3148 KB	Output is correct
13	Correct	104 ms	4632 KB	Output is correct
14	Correct	168 ms	6076 KB	Output is correct
15	Correct	172 ms	7580 KB	Output is correct
16	Correct	243 ms	9060 KB	Output is correct
17	Correct	294 ms	10540 KB	Output is correct
18	Correct	297 ms	11964 KB	Output is correct
19	Correct	506 ms	13708 KB	Output is correct
20	Correct	279 ms	10576 KB	Output is correct