Submission #685296

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
685296	2023-01-24T02:13:27 Z	vxxwu	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	477 ms	20952 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	42 ms	2528 KB	Output is correct
2	Correct	42 ms	2492 KB	Output is correct
3	Correct	39 ms	2488 KB	Output is correct
4	Correct	39 ms	2592 KB	Output is correct
5	Correct	40 ms	2500 KB	Output is correct
6	Correct	52 ms	2544 KB	Output is correct
7	Correct	43 ms	2580 KB	Output is correct
8	Correct	40 ms	2596 KB	Output is correct
9	Correct	152 ms	2980 KB	Output is correct
10	Correct	174 ms	2720 KB	Output is correct
11	Correct	41 ms	2564 KB	Output is correct
12	Correct	76 ms	4764 KB	Output is correct
13	Correct	121 ms	8564 KB	Output is correct
14	Correct	207 ms	9284 KB	Output is correct
15	Correct	192 ms	11624 KB	Output is correct
16	Correct	271 ms	16756 KB	Output is correct
17	Correct	305 ms	16808 KB	Output is correct
18	Correct	342 ms	18448 KB	Output is correct
19	Correct	477 ms	20952 KB	Output is correct
20	Correct	324 ms	16832 KB	Output is correct