Submission #1132942

#	Time	Username	Problem	Language	Result	Execution time	Memory
1132942		yumemystery	Job Scheduling (CEOI12_jobs)	C++20	100 / 100	209 ms	20940 KiB

jobs

#include <iostream>
#include <stack>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

bool canwork (vector<pair<int,int>> rq,int mid,int &N,int &D,int command) {
    int top = 0;
    stack <int> num;
    for (int i=1; i<=N+D; i++) {
        int cnt = 0;
        while (top!=rq.size()-1 && rq[top].first <= i) {
                if (cnt < mid) {
                    if (rq[top].first <= i && i-rq[top].first > D) return false;
                    if (command == 1) num.push(rq[top].second);
                    ++cnt;
                    ++top;
                }
                else break;
        }
        if (command == 1) {
            while (command == 1 && !num.empty()) {
                cout << num.top() << " ";
                num.pop();
            }
            cout << 0 << "\n";
            if (i==N) break;
        }
    }

    return true;
}

int main() {
    cin.tie(0) -> ios_base::sync_with_stdio(false);
    int N,D,M;
    cin >> N >> D >> M;

    vector <pair<int,int>> request;
    
    int left = 1;
    int right = M;

    for (int i=1; i<=M; i++) {
        int req;
        cin >> req;
        request.push_back(make_pair(req,i));
    }

    sort(request.begin(),request.end());

    int ans=0;

    while (left <= right) {
        int mid = left + (right-left)/2;
        
        if (canwork(request,mid,N,D,0)) {
            right = mid-1;
            ans = mid;
        }
        else {
            left = mid+1;
        }
    }

    cout << ans << "\n";

    int top = 0;

    canwork(request,ans,N,D,1);
    
}

• Subtask 1: 100 / 100