Submission #1218013

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218013		paskalisapo	Job Scheduling (CEOI12_jobs)	C++20	0 / 100	61 ms	131072 KiB

jobs

#include<bits/stdc++.h>
using namespace std;

int daysnum, maxdelay, reqnum;
vector<int> requests(1e6 + 10);
vector<int> prefreq(2 * 1e6, 1e8);
vector<stack<int>> numind(1e6 + 10);
vector<int> inp(1e6 + 1);

bool valid(int machnum) {
    int index = 1;   
    while(index <= daysnum) {
        if(inp[index] > maxdelay) {
            if(prefreq[index + maxdelay - 1] - prefreq[index - 1] > machnum * maxdelay ) {
                return false;
            }
        }
        index++;
    }
    return true;
}

int main() {
    cin >> daysnum >> maxdelay >> reqnum;
    for(int i = 0 ;i < reqnum; i++) {
        int time;
        cin >> time;
        inp[i + 1] = time;
        requests[time]++;
        numind[time].push(i + 1);
    }

    int l = 0;
    int r = 1e6 + 1;
    prefreq[0] = 0;
    for(int i = 1; i <= 1e6; i++) {
        prefreq[i] = requests[i] +  prefreq[i - 1];
    }
    while(l < r) {
        int mid = (l + r) / 2;
        if(valid(mid)) {
            r = mid;
        }
        else {
            l = mid + 1;
        }
    }

    int minmach = l;
    int cur = minmach;
    cout << minmach << endl;
    int day = 1;
    int curday = 1;
    while(day <= daysnum) {
        int used = 0;
        while(used < minmach) {
            if(curday > day) {
                break;
            }
            else if(numind[curday].empty()) {
                curday++;
            }
            else {
                int ans = numind[curday].top();
                cout << ans << " ";
                numind[curday].pop();   
            }
            used++;
        }
        cout << 0 << endl;
        day++;
    }
}

• Subtask 1: 0 / 100