Submission #1172631

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172631		nguyenkhangninh99	Job Scheduling (CEOI12_jobs)	C++17	70 / 100	159 ms	39180 KiB

jobs

#include<bits/stdc++.h>
 using namespace std;
 
#define int long long

const int maxn = 1e6 + 5;

vector<int> day[maxn];
int n, d, m; 

bool ok(int mid){
    queue<int> q;
    for(int i = 1; i <= n; i++){
        if(q.size() && q.front() < i - d) return false;
        for(int x: day[i]) q.push(i);
        for(int j = 0; j < mid && q.size(); j++) q.pop();
    }

    return true;
}
signed main(){
    ios_base::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);

    cin >> n >> d >> m;

    for(int i = 1; i <= m; i++){
        int x; cin >> x;
        day[x].push_back(i);
    }
    
    int l = 1, r = m, ans = -1;

    while(l <= r){
        int mid = (l + r) / 2;

        if(ok(mid)){
            ans = mid;
            r = mid - 1;
        }
        else l = mid + 1;
    } 
    cout << ans << "\n";

    queue<int> q;
    for(int i = 1; i <= n; i++){
        for(int x: day[i]) q.push(x);
        for(int j = 0; j < ans && q.size(); j++){
            cout << q.front()  << " ";
            q.pop();
        }
        cout << 0 << "\n";
    }
}

• Subtask 1: 70 / 100