oj.uz

Submission #429495

# Submission time Handle Problem Language Result Execution time Memory
429495 2021-06-16T03:53:39 Z joshualiu555 Job Scheduling (CEOI12_jobs) C++14
0 / 100
 81 ms 5064 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];
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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 2564 KB Output isn't correct
2 Incorrect 28 ms 2536 KB Output isn't correct
3 Incorrect 29 ms 2548 KB Output isn't correct
4 Incorrect 30 ms 2420 KB Output isn't correct
5 Incorrect 28 ms 2476 KB Output isn't correct
6 Incorrect 28 ms 2428 KB Output isn't correct
7 Incorrect 28 ms 2528 KB Output isn't correct
8 Incorrect 28 ms 2476 KB Output isn't correct
9 Incorrect 36 ms 2420 KB Output isn't correct
10 Incorrect 36 ms 2488 KB Output isn't correct
11 Incorrect 38 ms 2540 KB Output isn't correct
12 Incorrect 81 ms 5064 KB Output isn't correct
13 Incorrect 19 ms 2828 KB Output isn't correct
14 Incorrect 23 ms 3404 KB Output isn't correct
15 Incorrect 19 ms 2892 KB Output isn't correct
16 Incorrect 29 ms 3136 KB Output isn't correct
17 Incorrect 23 ms 3404 KB Output isn't correct
18 Incorrect 20 ms 2900 KB Output isn't correct
19 Incorrect 19 ms 2924 KB Output isn't correct
20 Incorrect 23 ms 3320 KB Output isn't correct