Submission #1125763

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125763		abel2008	Job Scheduling (CEOI12_jobs)	C++20	0 / 100	1100 ms	127016 KiB

jobs

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

bool solve(int crtd) {
        multiset<int> req = requests,todo;
        for (int i = 1;i<=n;++i) {
                while(!req.empty()&&*req.begin()<=i) {
                        todo.insert(*req.begin());
                        req.erase(req.find(*req.begin()));
                }
                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.insert(val);
                identifiers.insert({val,i});
        }
        int st = 1,dr = n;
        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();
                                int num = el.first;
                                cout<<el.second<<" ";
                                todo.erase(todo.find(*todo.begin()));
                                if (num+d<i) {
                                        return 0;
                                }
                        }
                }
                cout<<0<<'\n';
        }
        if (!todo.empty())
                return 0;
        return 1;
        return 0;
}

• Subtask 1: 0 / 100