oj.uz

Submission #429518

# Submission time Handle Problem Language Result Execution time Memory
429518 2021-06-16T05:07:44 Z joshualiu555 Job Scheduling (CEOI12_jobs) C++14
20 / 100
 68 ms 3060 KB 
#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) {
        for (int i = 0; i < num_machines && current_index < m; i++) {
            if (a[current_index].first + d < current_day) {
                return false;
            }
            current_index++;
        }
        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 << "\n";
    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
20.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 1612 KB Output isn't correct
2 Incorrect 23 ms 1612 KB Output isn't correct
3 Incorrect 25 ms 1616 KB Output isn't correct
4 Incorrect 28 ms 1612 KB Output isn't correct
5 Incorrect 22 ms 1604 KB Output isn't correct
6 Incorrect 22 ms 1660 KB Output isn't correct
7 Incorrect 22 ms 1628 KB Output isn't correct
8 Incorrect 22 ms 1616 KB Output isn't correct
9 Correct 38 ms 1868 KB Output is correct
10 Correct 37 ms 1856 KB Output is correct
11 Correct 35 ms 1624 KB Output is correct
12 Correct 68 ms 3060 KB Output is correct
13 Incorrect 18 ms 1868 KB Output isn't correct
14 Incorrect 26 ms 1840 KB Output isn't correct
15 Incorrect 18 ms 1852 KB Output isn't correct
16 Incorrect 22 ms 1860 KB Output isn't correct
17 Incorrect 21 ms 1876 KB Output isn't correct
18 Incorrect 19 ms 1884 KB Output isn't correct
19 Incorrect 26 ms 1996 KB Output isn't correct
20 Incorrect 21 ms 1900 KB Output isn't correct