Submission #623906

#	Time	Username	Problem	Language	Result	Execution time	Memory
623906		afatpotato	Job Scheduling (CEOI12_jobs)	C++14	0 / 100	377 ms	22628 KiB

jobs

#include <bits/stdc++.h>

using namespace std;

bool solve(int x);


int n, d, m;
vector<vector<int> > request;

int main() {
    cin >> n >> d >> m;
    request.resize(n);

    for (int i = 0; i < m; i++) {
        int a;
        cin >> a;
        request[a].push_back(i+1);
    }
    int low = 1;
    int high = m;
    int ans = 0;
    while (low < high) {
        int mid = (low + high) / 2;
        if (solve(mid)) {
            high = mid;
            ans = mid;
        } else {
            low = mid + 1;
        }
    }
    cout << ans << endl;
    vector<vector<int> > output(n+1);
    queue<int> q;
    int idx = 1;
    for (int i = 1; i < n+1; i++) {
        for (int j = 0; j < request[i].size(); j++) {
            q.push(request[i][j]);
        }
        for (int j = 0; j < ans; j++) {
            if (q.empty()) {
                break;
            }
            output[idx].push_back(q.front());
            q.pop();
        }
        output[idx].push_back(0);
        idx++;
    }
    for (int i = 1; i < n+1; i++) {
        for (int j = 0; j < output[i].size(); j++) {
            cout << output[i][j] << " ";
        }
        cout << endl;
    }
}

bool solve(int x) {
    vector<int> cur(n);
    int idx = 1;
    for (int i = 1; i < n; i++) {
        cur[i] = request[i].size();
        int num = x;
        while (idx <= i && num != 0) {
            if (cur[idx] == 0) {
                idx++;
            }
            if (num < cur[idx]) {
                cur[idx] -= num;
                num = 0;
            } else if (num == cur[idx]) {
                cur[idx] -= num;
                idx++;
                num = 0;
            } else {
                num -= cur[idx];
                cur[idx] = 0;
                idx++;
            }
        }
        if (i - idx > d) {
            return false;
        }
    }
    return true;
}

Compilation message (stderr)

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

• Subtask 1: 0 / 100