Submission #1125810

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125810		abel2008	Job Scheduling (CEOI12_jobs)	C++17	55 / 100	1098 ms	46196 KiB

jobs

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
int n,d,m,val;
vector<int> requests;
set<pair<int,int>> identifiers;

bool solve(int crtd) {
        multiset<int> todo;
        int reqi = 0;
        for (int i = 1;i<=n;++i) {
                while(reqi<requests.size()&&requests[reqi]<=i) {
                        todo.insert(requests[reqi]);
                        reqi++;
                }
                for (int j = 1;j<=crtd;++j) {
                        if (!todo.empty()) {
                                int num = *todo.begin();
                                todo.erase(todo.find(*todo.begin()));
                                if (num+d<i) {
                                        return 0;
                                }
                        }
                }
        }
        if (!todo.empty())
                return 0;
        return 1;
}

int main() {
        cin>>n>>d>>m;
        for (int i = 1;i<=m;++i) {
                cin>>val;
                requests.push_back(val);
                identifiers.emplace(val,i);
        }
        sort(requests.begin(),requests.end());
        int st = 1,dr = m;
        while(st<dr) {
                int mid = (st+dr)/2;
                if (solve(mid)) {
                        dr = mid;
                } else {
                        st = mid+1;
                }
        }
        cout<<dr<<'\n';
        int crtd = dr;
        multiset<pair<int,int>> todo;
        // modify RED
        for (int i = 1;i<=n;++i) {
                while(!identifiers.empty()&&(*identifiers.begin()).first<=i) {
                        todo.insert(*identifiers.begin());
                        identifiers.erase(identifiers.find(*identifiers.begin()));
                }
                for (int j = 1;j<=crtd;++j) {
                        if (!todo.empty()) {
                                auto el = *todo.begin();
                                cout<<el.second<<" ";
                                todo.erase(todo.find(*todo.begin()));
                        }
                }
                cout<<0<<'\n';
        }
        return 0;
}

• Subtask 1: 55 / 100