답안 #535390

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
535390	2022-03-10T06:54:57 Z	Pyrodox	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	461 ms	27820 KB

jobs

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n, d, m;
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    cin >> n >> d >> m;
    vector<int> jobs(m);
    unordered_map<int, vector<int>> mp;
    unordered_map<int, int> val;
    for (int i = 1; i <= m; ++i) {
        int a;
        cin >> a;
        jobs[i - 1] = a;
        mp[a].push_back(i);
    }
    sort(jobs.begin(), jobs.end());
    vector<vector<int>> ans;
    int l = 1, r = m;
    while (l < r) {
        int mid = l + (r - l) / 2, start = 0;
        //cout << "testing mid: " << mid << "\n";
        bool check = true;
        vector<vector<int>> jobstmp(n);
        for (int i = 0; i < n && check; ++i) {
            //cout << i << "\n";
            for (int j = 0; j < mid && start <= m - 1; ++j) {
                //cout << "bat\n";
                if (jobs[start] <= i + 1 && i + 1 - jobs[start] <= d) {
                    jobstmp[i].push_back(jobs[start]);
                    ++start;
                    //cout << "at\n";
                }
                else if (i + 1 - jobs[start] > d) {
                    check = false;
                    break;
                }
                else {
                    break;
                }
            }
        }
        /*for (auto val : jobstmp) {
            for (int i : val) {
                cout << i << " ";
            }
            cout << "\n";
        }*/
        //cout << "start: " << start << " check: " << "\n";
        if (check && start == m) {
            //cout << "r from " << r << " to r -> " << mid << "\n";
            r = mid;
            ans = jobstmp;
        }
        else {
            //cout << "l from " << l << " to l -> " << mid << " + 1\n";
            l = mid + 1;
        }
    }
    cout << l << "\n";
    for (auto i : ans) {
        for (int j : i) {
            cout << mp[j][val[j]] << " ";
            ++val[j];
        }
        cout << "0\n";
    }
}

Subtask #1

100.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	49 ms	3232 KB	Output is correct
2	Correct	43 ms	3124 KB	Output is correct
3	Correct	35 ms	3180 KB	Output is correct
4	Correct	36 ms	3140 KB	Output is correct
5	Correct	35 ms	3128 KB	Output is correct
6	Correct	52 ms	3184 KB	Output is correct
7	Correct	54 ms	3204 KB	Output is correct
8	Correct	38 ms	3140 KB	Output is correct
9	Correct	52 ms	7700 KB	Output is correct
10	Correct	55 ms	7780 KB	Output is correct
11	Correct	58 ms	2944 KB	Output is correct
12	Correct	112 ms	5432 KB	Output is correct
13	Correct	155 ms	9124 KB	Output is correct
14	Correct	259 ms	13192 KB	Output is correct
15	Correct	288 ms	13536 KB	Output is correct
16	Correct	369 ms	17968 KB	Output is correct
17	Correct	460 ms	22976 KB	Output is correct
18	Correct	407 ms	21868 KB	Output is correct
19	Correct	456 ms	27820 KB	Output is correct
20	Correct	461 ms	22932 KB	Output is correct