Submission #740179

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
740179	2023-05-12T06:55:05 Z	Unforgettablepl	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	369 ms	23464 KB

jobs

/*
ID: samikgo1
TASK:
LANG: C++
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
#define all(x) x.begin(),x.end()
#define allr(x) x.rbegin(),x.rend()
//#define f first
//#define s second
//#define x first
//#define y second
const int INF = INT32_MAX;
vector<pair<int,int>> jobs;
int n,d,m;

bool check(int machines, bool print){
    // machines is the amount of machines we have
    if(machines==0){return false;}
    int day = 1;
    int curr = 0;
    vector<vector<int>> schedule(n);
    for(auto&job:jobs){
        while(job.first>day){
            curr = 0;
            day++;
        }
        if(day-job.first>d){
            return false;
        }
        curr++;
        schedule[day-1].emplace_back(job.second);
        if(curr == machines){
            day++;
            curr = 0;
        }
    }
    if(print){
        cout << machines << '\n';
        for(auto&i:schedule){
            for(int&j:i){
                cout << j << ' ';
            }
            cout << "0\n";
        }
    }
    return true;
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
//    freopen("measurement.in","r",stdin);
//    freopen("measurement.out","w",stdout);
    cin >> n >> d >> m;
    jobs.resize(m);
    for (int i = 0; i < m; i++) {
        cin >> jobs[i].first;
        jobs[i].second = i+1;
    }
    sort(all(jobs));
    int l = 1;
    int r = 1000000;
    int ans = 1000000;
    while(l<=r){
        int mid = (l+r)/2;
        if(check(mid,false)){
            ans = min(ans,mid);
            r = mid-1;
        } else {
            l = mid+1;
        }
    }
    check(ans,true);
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	30 ms	2896 KB	Output is correct
2	Correct	29 ms	2876 KB	Output is correct
3	Correct	29 ms	2820 KB	Output is correct
4	Correct	30 ms	2948 KB	Output is correct
5	Correct	29 ms	2964 KB	Output is correct
6	Correct	28 ms	2896 KB	Output is correct
7	Correct	28 ms	2948 KB	Output is correct
8	Correct	29 ms	2912 KB	Output is correct
9	Correct	38 ms	5000 KB	Output is correct
10	Correct	41 ms	5072 KB	Output is correct
11	Correct	36 ms	2580 KB	Output is correct
12	Correct	78 ms	4960 KB	Output is correct
13	Correct	104 ms	7820 KB	Output is correct
14	Correct	171 ms	11124 KB	Output is correct
15	Correct	187 ms	11576 KB	Output is correct
16	Correct	232 ms	14868 KB	Output is correct
17	Correct	281 ms	19296 KB	Output is correct
18	Correct	293 ms	19568 KB	Output is correct
19	Correct	369 ms	23464 KB	Output is correct
20	Correct	292 ms	19208 KB	Output is correct