Submission #1165038

#TimeUsernameProblemLanguageResultExecution timeMemory
1165038danieldswJob Scheduling (CEOI12_jobs)C++20
0 / 100
153 ms13640 KiB
#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,j; cin >> n >> d >> j;

    vector<vector<int>> nums(n);
    int num;
    for (int i =0; i < j; i++){
        cin >> num;
        nums[num-1].push_back(i);
    }
    int l = 1, r = j, m;
    bool a;
    int sol = j;
    queue<int> q;
    while (l <= r){
        m = (l+r)/2;
        a = true;
        q = {};
        for (int i = 0; i < n; i++){
            for (int x = 0; x < nums[i].size(); x++){
                q.push(nums[i][x]+d);
            }
            for (int f = 0; f < m; f++){
                if (q.empty()){break;}
                if (q.front() < i){a=false;}
                q.pop();
            }
        }
        if (a){
            sol = m;
            r = m-1;
        }
        else {
            l = m+1;
        }
    }
    q = {};
    for (int i = 0; i < n; i++){
        for (int x = 0; x < nums[i].size(); x++){
            q.push(nums[i][x]);
        }
        for (int f = 0; f < m; f++){
            if (q.empty()){break;}
            cout << q.front()+1 << " ";
            q.pop();
        } 
        cout << "0\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();
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...