oj.uz

Submission #429497

# Submission time Handle Problem Language Result Execution time Memory
429497 2021-06-16T03:57:39 Z joshualiu555 Job Scheduling (CEOI12_jobs) C++14
0 / 100
 76 ms 4248 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;
        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";
    }
    for (int i = (int)v.size(); i < n; i++) {
        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:66:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     for (int i = 0; i < v.size(); i++) {
      |                     ~~^~~~~~~~~~
jobs.cpp:67:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |         for (int j = 0; j < v[i].size(); j++) {
      |                         ~~^~~~~~~~~~~~~

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 2172 KB Output isn't correct
2 Incorrect 30 ms 2144 KB Output isn't correct
3 Incorrect 31 ms 2156 KB Output isn't correct
4 Incorrect 28 ms 2172 KB Output isn't correct
5 Incorrect 28 ms 2180 KB Output isn't correct
6 Incorrect 29 ms 2204 KB Output isn't correct
7 Incorrect 28 ms 2216 KB Output isn't correct
8 Incorrect 32 ms 2156 KB Output isn't correct
9 Incorrect 45 ms 2412 KB Output isn't correct
10 Incorrect 46 ms 2404 KB Output isn't correct
11 Incorrect 38 ms 2180 KB Output isn't correct
12 Incorrect 76 ms 4248 KB Output isn't correct
13 Incorrect 20 ms 1828 KB Output isn't correct
14 Incorrect 22 ms 2244 KB Output isn't correct
15 Incorrect 18 ms 1808 KB Output isn't correct
16 Incorrect 22 ms 1952 KB Output isn't correct
17 Incorrect 22 ms 2244 KB Output isn't correct
18 Incorrect 19 ms 1868 KB Output isn't correct
19 Incorrect 26 ms 2100 KB Output isn't correct
20 Incorrect 22 ms 2208 KB Output isn't correct