oj.uz

Submission #532903

# Submission time Handle Problem Language Result Execution time Memory
532903 2022-03-04T08:04:58 Z louiskwok Job Scheduling (CEOI12_jobs) C++17
100 / 100
 502 ms 26884 KB 
#include <bits/stdc++.h>
using namespace std;
struct Job {
    int id;
    int day;
    bool operator<(const Job arb) const { return day < arb.day; }
} job[1000005];
int n,d,m;
vector <int> tmp[100005],ans[100005];
bool possible(int x) {
    int ptr = 1;
    for (int i=1;i<=n;i++) {
        tmp[i].clear();
        for (int j=0;j<x;j++) {
            if (job[ptr].day>i) break;
            if (job[ptr].day+d>=i) tmp[i].push_back(job[ptr++].id);
            else return false;
            if (ptr>m) return true;
        }
    }
    return false;
}
int main() {
    cin >> n >> d >> m;
    for (int i=1;i<=m;i++) {
        cin >> job[i].day;
        job[i].id = i;
    }
    sort(job+1,job+m+1);
    int lo = 1,hi = m;
    while (lo<hi) {
        int mid = lo+(hi-lo)/2;
        if (possible(mid)) {
            hi = mid;
            for (int i=1;i<=n;i++) ans[i] = tmp[i];
        }
        else lo = mid+1;
    }
    cout << lo << endl;
    int it = 1;
    for (int i=1;i<=n;i++) {
        for (int j=0;j<ans[i].size();j++) cout << ans[i][j] << ' ';
        cout << 0 << endl;
    }
    return 0;
}

Compilation message

jobs.cpp: In function 'int main()':
jobs.cpp:42:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         for (int j=0;j<ans[i].size();j++) cout << ans[i][j] << ' ';
      |                      ~^~~~~~~~~~~~~~
jobs.cpp:40:9: warning: unused variable 'it' [-Wunused-variable]
   40 |     int it = 1;
      |         ^~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 7216 KB Output is correct
2 Correct 46 ms 7236 KB Output is correct
3 Correct 50 ms 7288 KB Output is correct
4 Correct 45 ms 7412 KB Output is correct
5 Correct 49 ms 7236 KB Output is correct
6 Correct 44 ms 7236 KB Output is correct
7 Correct 45 ms 7288 KB Output is correct
8 Correct 45 ms 7296 KB Output is correct
9 Correct 166 ms 7464 KB Output is correct
10 Correct 179 ms 7508 KB Output is correct
11 Correct 43 ms 7364 KB Output is correct
12 Correct 84 ms 9836 KB Output is correct
13 Correct 145 ms 12904 KB Output is correct
14 Correct 194 ms 15648 KB Output is correct
15 Correct 201 ms 17364 KB Output is correct
16 Correct 310 ms 20424 KB Output is correct
17 Correct 338 ms 24428 KB Output is correct
18 Correct 335 ms 24744 KB Output is correct
19 Correct 502 ms 26884 KB Output is correct
20 Correct 346 ms 24364 KB Output is correct