제출 #600781

#제출 시각아이디문제언어결과실행 시간메모리
600781as111Job Scheduling (CEOI12_jobs)C++17
0 / 100
802 ms65536 KiB
#include <iostream> #include <set> #include<vector> #define MAXN 100000 using namespace std; int jobs[MAXN + 1]; multiset<int> curr; // currently working jobs set<int> ID[MAXN + 1]; // all identifiers in the input for each day set<int> ans[MAXN + 1]; // identifiers used in each day int main() { int N, D, M; cin >> N >> D >> M; for (int m = 1; m <= M; m++) { int j; cin >> j; jobs[j] ++; ID[j].insert(m); } int low = 2; int high = 2; while (low == high) { int mid = (low + high) / 2; // bsearch on # of machines int mx = 0; // maximum delay occuring for (int i = 1; i <= N; i++) { // day i if(!curr.empty()) mx = max(mx, i - *curr.begin()); // number of days delay on earliest job if (curr.size() <= mid) { int left = mid - curr.size(); curr.clear(); for (int j = 1; j <= jobs[i] - left;j++) { curr.insert(i); } } else { set<int>::iterator it = curr.begin(); advance(it, mid); curr.erase(curr.begin(), it); for (int j = 1; j <= jobs[i]; j++) { curr.insert(i); } } } if (mx <= D) { high = mid; } else { low = mid + 1; } if (low >= high) break; } set<int>::iterator it; int day = 0; for (int i = 1; i <= N; i++) { // day i if (curr.size() <= low) { int left = low - curr.size(); for (int j = 1; j <= curr.size(); j++) { if (*curr.begin() != day) { day = *curr.begin(); it = ID[day].begin(); } curr.erase(curr.begin()); ans[i].insert(*it); // add to job finished on this day it++; } day = i; it = ID[day].begin(); for (int j = 1; j <= jobs[i]; j++) { if (j > jobs[i] - left) { ans[i].insert(*it); it++; } else { curr.insert(i); } } } else { for (int j = 1; j <= low; j++) { if (*curr.begin() != day) { day = *curr.begin(); it = ID[day].begin(); } curr.erase(curr.begin()); ans[i].insert(*it); it++; } for (int j = 1; j <= jobs[i]; j++) { curr.insert(i); } } } cout << low << endl; for (int i = 1; i <= N; i++) { for (int e : ans[i]) { cout << e << " "; } cout << 0 << endl; } }

컴파일 시 표준 에러 (stderr) 메시지

jobs.cpp: In function 'int main()':
jobs.cpp:28:20: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   28 |    if (curr.size() <= mid) {
      |        ~~~~~~~~~~~~^~~~~~
jobs.cpp:55:19: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   55 |   if (curr.size() <= low) {
      |       ~~~~~~~~~~~~^~~~~~
jobs.cpp:57:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::multiset<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |    for (int j = 1; j <= curr.size(); j++) {
      |                    ~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...