Submission #685296

#	Time	Username	Problem	Language	Result	Execution time	Memory
685296		vxxwu	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	477 ms	20952 KiB

jobs

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>

using namespace std;

#define MAXN 500
#define ll long long
#define int ll
#define max max<int>
#define min min<int>
#define f first
#define s second

typedef pair<int, int> pii;

int max_days, d, n;
vector<pii> jobs;
//vector<vector<int>> sequence;
//vector<vector<int>> secure;

bool check = true;

void work(int day, int index, int machines) {
//    cout<<day<<" "<<index<<" "<<machines<<endl;
    if(index>=n-1){
//        for(int i=day; i<=max_days; i++)
//            sequence.emplace_back();
        return;
    }
//    sequence.emplace_back();
    if (jobs[index].f <= day) {
        for (int i = index; i < min(index + machines, n); i++) {
//            cout<<i<<endl;
            if (jobs[i].f > day){
                index=i;
                break;
            }

            if (jobs[i].f < day - d) {
                check = false;
                return;
            }

            if(i==min(index + machines, n)-1){
                index=min(index + machines, n);
                break;
            }
        }
    }

    work(day + 1, index, machines);
}

void work_final(int day, int index, int machines) {
//    cout<<day<<" "<<index<<" "<<machines<<endl;
    if(index>=n-1){
        for(int i=day; i<=max_days; i++)
            cout<<0<<endl;
//            sequence.emplace_back();
        return;
    }
//    sequence.emplace_back();
    if (jobs[index].f <= day) {
        for (int i = index; i < min(index + machines, n); i++) {
//            cout<<i<<endl;
            if (jobs[i].f > day){
                index=i;
                break;
            }

            if (jobs[i].f >= day - d) {
//                sequence[sequence.size() - 1].emplace_back(jobs[i].s);
                cout<<jobs[i].s<<" ";
//                cout<<"emplaced "<<jobs[i].f<<" "<<jobs[i].s<<endl;
            } else if (jobs[i].f < day - d) {
                check = false;
                return;
            }

            if(i==min(index + machines, n)-1){
                index=min(index + machines, n);
                break;
            }
        }
    }
    cout<<0<<endl;

    work_final(day + 1, index, machines);
}

int32_t main() {
//    freopen("test.in", "r", stdin);
//    freopen("test.out", "w", stdout);
    cin >> max_days >> d >> n;
    for (int i = 1; i <= n; i++) {
        int a;
        cin >> a;
        jobs.emplace_back(a, i);
    }
    sort(begin(jobs), end(jobs));

//    for(pii i:jobs) cout<<i.f<<endl;

    int lower = 1, upper = n;
    while (lower != upper) {
        int mid = (lower + upper) / 2;
        check = true;
//        sequence.clear();
//        cout<<"try "<<mid<<endl;
        work(1, 0, mid);
//        cout<<mid<<endl;
        if (check) {
            upper = mid;
//            secure=sequence;
//            cout<<"check"<<endl;
        } else {
            lower = mid + 1;
//            cout<<"failed"<<endl;
        }
    }

    cout << lower << endl;
    work_final(1, 0, lower);

//    for(vector<int> i:sequence){
//        for(int j:i){
//            cout<<j<<" ";
//        }
//        cout<<0<<endl;
//    }
}

• Subtask 1: 100 / 100