Submission #1165046

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165046		danieldsw	Job Scheduling (CEOI12_jobs)	C++20	0 / 100	156 ms	13640 KiB

jobs

#define ll long long
#include <bits/stdc++.h>
using namespace std;
ll inf = 999999999999999999;

/*
Job Scheduling
*/

void solve(istream& cin = std::cin, ostream& cout = std::cout){
    int n,d,jobs; cin >> n >> d >> jobs;
    vector<vector<int>> nums(n);
    int num;
    for (int i = 0; i < jobs; i++){
        cin >> num;
        nums[num-1].push_back(i);
    }
    queue<int> q;
    int l=1,r=jobs,m, sol = r;
    bool a;
    while (l <= r){
        m = (l+r)/2;
        a = true;
        q = {};
        for (int i = 0; i < n; i++){
            for (int j = 0; j < nums[i].size(); j++){
                q.push(nums[i][j]+d);
            }
            for (int j =0 ; j < m; j++){
                if (q.empty()){break;}
                else {
                    if (q.front() < i){a=false;}
                    q.pop();
                }
            }
        }
        if (a){
            sol = m, r=m-1;;
        }
        else {l=m+1;}
    }
    cout << sol << '\n';
    q = {};
    for (int i = 0; i < n; i++){
        for (int j = 0; j < nums[i].size(); j++){
            q.push(nums[i][j]);
        }
        for (int j= 0; j < sol; j++){
            if (q.empty()){break;}
            cout << q.front()+1 << " ";
            q.pop();
        }
        cout << "0";
        if (i < n-1){cout << "\n";}
    }
}



// ------------------------------

bool fileExists(const std::string& filename) {
    std::ifstream file(filename);
    return file.good();
}
int main() {
	ios::sync_with_stdio(0);
	cout.tie(0);
	cin.tie(0);

    string f = "angry";
    if (fileExists(f+".in")){
        ifstream cin(f+".in"); ofstream cout(f+".out");
        solve(cin,cout);
        cin.close(),cout.close();
    }
    else if (fileExists("input.txt")){
        ifstream cin("input.txt"); ofstream cout("output.txt");
        solve(cin,cout);
        cin.close(), cout.close();
    }
    else {
        solve();
    }
}

• Subtask 1: 0 / 100