// The Central Engineering Organization, International (CEOI) has received
// Mjob requests for the next Ndays. To perform a job requires exactly one day
// by one machine. CEOI has access to several machines, each of which can
// perform at most one job per day, sothe organization can do at most as many
// jobs a day as the number of available machines. CEOI aims to work with at
// mostDdays of delay, which means that if a client submits a job for
// processing on day S, then it will be finished no later than on day S+D.
// Task:
// You are to write a program that computes the minimum number of machines that
// the organization needs to process all jobs with at most Ddays of
// delay.
//
// Input
// The first line of the input contains three integers, N(1
// ≤N ≤100000) is the number of days the organization performs jobs, D(0
// ≤D< N) is the maximum number of days permitted for the delay, and M(1 ≤M ≤1
// 000 000) is the number of job requests. The days are numbered from 1to N,
// and the requests are numbered from 1toM. The second line contains
// exactly Mintegers separated by space, the ith number is the day when
// request iis submitted for processing.No jobs are submitted after day
// N–D.
//
// Output
// The first line of the output contains one integer, the minimum
// number ofmachines that the organization needs to be able to process
// all jobs with at most Ddays of delay. The next Nlines describe a
// feasible schedule for processing the requests. The (i+1)th line
// contains the identifiers of the requests scheduled for day i.
// Numbers in a line must be separated by space and terminated by
// 0. If there are multiple solutions, your program should output only
// one; it does not matter which one.
//
#include <iostream>
#include <fstream>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <queue>
#define sz(x) (int)size(x)
#define last_elem(coll) (*(coll.rbegin()))
#define FOR(x, e) for(u32 x = 0; x < (u32)(e); x++)
#define FORR(x, e) for(u32 x = (u32)(e) - 1; x < (u32)(e); x--)
#define FOB(x, b, e) for(auto x = (b); x != (e); x++)
#define FOI(x, e, i) for(u32 x = 0; x < (u32)e; x += (u32)(i))
#define FORE(x, C) for(auto& x: C)
using namespace std;
using i32 = int;
using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;
using i16 = short;
using u16 = unsigned short;
using i8 = char;
using u8 = unsigned char;
using f64 = double;
using f32 = float;
using si = i32;
using sl = i64;
using ui = u32;
using ul = u64;
using vl = std::vector<i64>;
using vi = std::vector<i32>;
using vs = std::vector<i16>;
using vul = std::vector<u64>;
using vui = std::vector<u32>;
using vus = std::vector<u16>;
#ifdef MY_COMPILE
auto stin = std::ifstream("TestSamples/Job_Scheduling_CEOI.in");
auto sout = std::ofstream("TestSamples/Job_Scheduling_CEOI.out");
#elif OLDERN
auto stin = std::ifstream("bcount.in");
auto sout = std::ofstream("bcount.out");
#else
auto &stin = std::cin;
auto &sout = std::cout;
#endif
bool is_goodp(vector<pair<sl, sl>>& schedules, sl days, sl delay, sl n)
{
sl jobs = 0;
sl nth_day = 1;
queue<sl> js;
FOR(i, sz(schedules)) {
if (!i || schedules[i].first != schedules[i - 1].first) {
sl inc = 0;
if (i) inc = schedules[i].first - schedules[i - 1].first;
else inc = schedules[i].first - 1;
FOR(k, inc) {
FOR(j, n) {
if (!sz(js)) break;
sout << js.front() << ' ';
js.pop();
}
sout << "0" << endl;
nth_day++;
}
}
js.push(schedules[i].second);
}
while(nth_day <= days) {
FOR(j, n) {
if (!sz(js)) break;
sout << js.front() << ' ';
js.pop();
}
sout << "0" << endl;
nth_day++;
}
return true;
}
bool is_good(vector<pair<sl, sl>>& schedules, sl days, sl delay, sl n)
{
sl jobs = 0;
sl nth_day = 0;
FOR(i, sz(schedules)) {
if (!i || schedules[i].first != schedules[i - 1].first) {
auto inc = i
? schedules[i].first - schedules[i - 1].first
: schedules[i].first;
jobs -= n * inc;
jobs = max((sl)0, jobs);
nth_day += inc;
}
jobs++;
if ((jobs - 1) / n > delay) {
return false;
}
}
if ((jobs - 1) / n > (days - nth_day)) return false;
return true;
}
int main()
{
ui N, D, M;
stin >> N >> D >> M;
vector<pair<sl, sl>> schedules(M);
FOR(i, M) {
stin >> schedules[i].first;
schedules[i].second = i + 1;
}
sort(schedules.begin(), schedules.end());
sl in = 1, ax = M;
while(in < ax) {
auto ean = (in + ax) / 2;
if (is_good(schedules, N, D, ean)) {
ax = ean;
} else {
in = ean + 1;
}
}
sout << in << endl;
is_goodp(schedules, N, D, in);
return 0;
}
Compilation message
jobs.cpp: In function 'bool is_goodp(std::vector<std::pair<long long int, long long int> >&, sl, sl, sl)':
jobs.cpp:86:8: warning: unused variable 'jobs' [-Wunused-variable]
86 | sl jobs = 0;
| ^~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
62 ms |
3268 KB |
Output is correct |
| 2 |
Correct |
61 ms |
3276 KB |
Output is correct |
| 3 |
Correct |
63 ms |
3272 KB |
Output is correct |
| 4 |
Correct |
61 ms |
3264 KB |
Output is correct |
| 5 |
Correct |
63 ms |
3288 KB |
Output is correct |
| 6 |
Correct |
61 ms |
3264 KB |
Output is correct |
| 7 |
Correct |
61 ms |
3272 KB |
Output is correct |
| 8 |
Correct |
62 ms |
3268 KB |
Output is correct |
| 9 |
Correct |
206 ms |
2632 KB |
Output is correct |
| 10 |
Correct |
211 ms |
2748 KB |
Output is correct |
| 11 |
Correct |
58 ms |
2376 KB |
Output is correct |
| 12 |
Correct |
131 ms |
4944 KB |
Output is correct |
| 13 |
Correct |
180 ms |
6900 KB |
Output is correct |
| 14 |
Correct |
259 ms |
9492 KB |
Output is correct |
| 15 |
Correct |
291 ms |
11460 KB |
Output is correct |
| 16 |
Correct |
379 ms |
13912 KB |
Output is correct |
| 17 |
Correct |
445 ms |
15984 KB |
Output is correct |
| 18 |
Correct |
501 ms |
18440 KB |
Output is correct |
| 19 |
Correct |
697 ms |
20780 KB |
Output is correct |
| 20 |
Correct |
453 ms |
15980 KB |
Output is correct |
