Submission #400810

#	Time	Username	Problem	Language	Result	Execution time	Memory
400810		phisti	Job Scheduling (CEOI12_jobs)	C++17	15 / 100	707 ms	21316 KiB

jobs

// 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) {
            jobs -= n;
            auto 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++;
            }
        }
        
        jobs++;
        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) {
            jobs -= n;
            if (i) nth_day+= schedules[i].first - schedules[i - 1].first;
            else nth_day += schedules[i].first;
        }
        
        jobs++;
        if (jobs / n > delay
            || jobs / 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;
}

• Subtask 1: 15 / 100