Submission #783527

#	Time	Username	Problem	Language	Result	Execution time	Memory
783527		jnjwnwnw	Job Scheduling (CEOI12_jobs)	C++11	100 / 100	409 ms	14192 KiB

jobs

#include <iostream>
#include <algorithm>
using namespace std;
#define pb push_back
#define MAXM 1000001
#define d first
#define id second
typedef pair<int, int> request; // day, id

int n, D, m;
request requests[MAXM];

void setIO(string s) {
	freopen((s + ".in").c_str(), "r", stdin);
	freopen((s + ".out").c_str(), "w", stdout);
}

bool works(int numMachines);

int main(){
    cin >> n >> D >> m;
    for(int i = 0; i < m; i++){
        cin >> requests[i].d;
        requests[i].id = i;
    }
    sort(requests, requests+m);
    int lb = 1, ub = m;
    int mid;
    while (lb != ub){
        mid = (lb+ub)/2;
        if (works(mid)){
            // works with this many machines, so try less
            ub = mid;
        }else{
            // doesnt work, so try more
            lb = mid+1;
        }
    }

    cout << lb << endl;
    int idx = 0;
    for(int i = 0; i < n; i++){
        int end = min(m, idx+lb);
        for(;idx<end;idx++){
            if (requests[idx].d > i+1) break;
            cout << requests[idx].id+1 << " ";
        }
        cout << 0 << endl;
    }
}

bool works(int numMachines){
    // cout << endl << endl << numMachines << endl;
    int curNum = numMachines, day = 1;
    for(int i = 0; i < m; i++){
        if (requests[i].d > day) {day = requests[i].d; curNum = numMachines;}
        if (requests[i].d+D < day) return false; // you had to finish it before today, as now it has been S-D days
        curNum--;
        if (curNum == 0) {curNum = numMachines; day++;}
    } return true;
}

Compilation message (stderr)

jobs.cpp: In function 'void setIO(std::string)':
jobs.cpp:14:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |  freopen((s + ".in").c_str(), "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:15:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |  freopen((s + ".out").c_str(), "w", stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100