제출 #469469

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
469469		PancakeFactory	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	554 ms	20236 KiB

jobs

#include <bits/stdc++.h>
using namespace std;
/* ################################ */
#define pb push_back
#define FOR(i, a, n) for(int i = (a); i < (n); i++)
#define FORN(i, n) for(int i = 0; i < (n); i++)
#define SZ(x) ((int) (x).size())
#define mp(x,y) make_pair((x), (y))
#define xx first
#define yy second
#define clr clear()
#define MOD 1000000007
typedef long long ll;
/* ################################ */
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wsizeof-array-argument"
template<typename T>void dbg_var(T data){cout<<data<<endl;};
void dbg_vec(const vector<int>& v){FOR(i,0,(int)v.size()){cout<<v[i]<<" ";}cout<<endl;}
void dbg_varlist(const vector<pair<string, int>>& s){FOR(i, 0, (int)s.size()){cout<<s[i].first<<": "<<s[i].second<<" | ";}cout<<endl;}
template <class T, unsigned N> void dbg_arr(T (&arr)[N]){int size = sizeof(arr)/sizeof(arr[0]);FOR(i,0,size){cout<<arr[i]<<" ";}cout<<endl;}
#pragma GCC diagnostic pop
/* ################################ */

pair<int, int> jobs[1000000];
int n, d, m; 

bool possible(int numMachines) {
    vector<int> curWork(numMachines, 0);
    FORN(i, m) {
        int curMachine = i%numMachines;
        curWork[curMachine] = max(curWork[curMachine]+1, jobs[i].first);

        if(curWork[curMachine] - jobs[i].first > d) {
            return false;
        }
    }

    return true;
}

int main() {
    //(void)! freopen("./schedule.in", "r", stdin);
    //(void)! freopen("./schedule.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> d >> m;
    FORN(i, m) {cin >> jobs[i].first; jobs[i].second = i+1;}
    sort(jobs, jobs+m);

    int low = 1;
    int high  = m;

    while(low < high){
        int mid = low + (high - low) / 2;

        if(possible(mid)){
            high = mid;
        }else{
            low = mid + 1;
        }
    }

    cout << low << endl;

    vector<int> curWork(low, 0);
    vector<int> days[n+1];

    FORN(i, m) {
        int curMachine = i%low;
        curWork[curMachine] = max(curWork[curMachine]+1, jobs[i].first);
        days[curWork[curMachine]].push_back(jobs[i].second);

        if(curWork[curMachine] - jobs[i].first > d) {
            return false;
        }
    }

    FOR(i, 1, n+1) {
        for(int x : days[i]) {
            cout << x << " ";
        }
        cout << 0 << endl;
    }

    return 0;
}

• Subtask 1: 100 / 100