Submission #429495

#	Time	Username	Problem	Language	Result	Execution time	Memory
429495		joshualiu555	Job Scheduling (CEOI12_jobs)	C++14	0 / 100	81 ms	5064 KiB

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];
vector<vector<int>> v;

bool ok(int num_machines) {
    int current_day = 1;
    int current_index = 0;
    while (current_index < m) {
        vector<int> temp;
        int x = current_index;
        for (; current_index < x + num_machines; current_index++) {
            if (a[current_index].first + d < current_day) {
                return false;
            }
            temp.push_back(a[current_index].second);
        }
        current_day++;
        v.push_back(temp);
    }
    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) {
        v.clear();
        int middle = (left + right) / 2;
        cerr << middle << endl;
        if (ok(middle)) {
            right = middle;
        } else {
            left = middle;
        }
    }

    cout << right << endl;

    for (int i = 0; i < v.size(); i++) {
        for (int j = 0; j < v[i].size(); j++) {
            cout << v[i][j] << " ";
        }
        cout << 0 << "\n";
    }

    return 0;
}

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

//

Compilation message (stderr)

jobs.cpp: In function 'int main()':
jobs.cpp:67:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     for (int i = 0; i < v.size(); i++) {
      |                     ~~^~~~~~~~~~
jobs.cpp:68:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         for (int j = 0; j < v[i].size(); j++) {
      |                         ~~^~~~~~~~~~~~~

• Subtask 1: 0 / 100