Submission #429498

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
429498	2021-06-16T04:05:06 Z	joshualiu555	Job Scheduling (CEOI12_jobs)	C++14	0 / 100	67 ms	3148 KB

jobs

#include <fstream>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <climits>

using namespace std;

using ll = long long;
const int INF = 2e5 + 5;

int n, d, m;
pair<int, int> a[INF], b[INF];

bool ok(int num_machines) {
    int current_day = 1;
    int current_index = 0;
    while (current_index < m) {
        int x = current_index;
        for (; current_index < x + num_machines; current_index++) {
            if (a[current_index].first + d < current_day) {
                return false;
            }
        }
        current_day++;
    }
    return true;
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);

    //ifstream fin(".in");
    //ofstream fout(".out");

    cin >> n >> d >> m;
    for (int i = 0; i < m; i++) {
        cin >> a[i].first;
        a[i].second = i + 1;
    }
    sort(a, a + m);

    int left = 0, right = m;
    while (right > left + 1) {
        int middle = (left + right) / 2;
        if (ok(middle)) {
            right = middle;
        } else {
            left = middle;
        }
    }

    cout << right << endl;
    int count = n;
    for (int i = 0; i < m; i += right) {
        for (int j = i; j < min(m, i + right); j++) {
            cout << a[j].second << " ";
        }
        count--;
        cout << 0 << "\n";
    }
    for (int i = 0; i < count; i++) {
        cout << 0 << "\n";
    }

    return 0;
}

/*
 * 8 2 12
 * 1 2 4 2 1 3 5 6 1 3 6 4
*/

//

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	30 ms	1608 KB	Output isn't correct
2	Incorrect	24 ms	1624 KB	Output isn't correct
3	Incorrect	23 ms	1640 KB	Output isn't correct
4	Incorrect	23 ms	1624 KB	Output isn't correct
5	Incorrect	22 ms	1648 KB	Output isn't correct
6	Incorrect	24 ms	1612 KB	Output isn't correct
7	Incorrect	24 ms	1640 KB	Output isn't correct
8	Incorrect	22 ms	1716 KB	Output isn't correct
9	Incorrect	38 ms	1868 KB	Output isn't correct
10	Incorrect	41 ms	1760 KB	Output isn't correct
11	Incorrect	40 ms	1600 KB	Output isn't correct
12	Incorrect	67 ms	3148 KB	Output isn't correct
13	Incorrect	18 ms	1812 KB	Output isn't correct
14	Incorrect	21 ms	1912 KB	Output isn't correct
15	Incorrect	18 ms	1788 KB	Output isn't correct
16	Incorrect	20 ms	1828 KB	Output isn't correct
17	Incorrect	21 ms	1868 KB	Output isn't correct
18	Incorrect	19 ms	1868 KB	Output isn't correct
19	Incorrect	26 ms	2072 KB	Output isn't correct
20	Incorrect	22 ms	1896 KB	Output isn't correct