Submission #1283111

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283111		hoangnguyen0703	Job Scheduling (CEOI12_jobs)	C++20	100 / 100	83 ms	13584 KiB

jobs

#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> a;
int m,n,d,res;

bool check(int k)
{
    if(k <= 0)return 0;
    int cnt = 0, finished = 0, dl = 0;
    for(int i = 1; i <= n; i++){
        if(i <= n-d)cnt += (int)a[i].size();
        //cnt = (cnt > k) ? cnt-k : 0;
        if(cnt > k){
            cnt -= k;
            finished += k;
        }
        else{
            finished += cnt;
            cnt = 0;
        }
        if(i > d){
            dl += (int)a[i-d].size();
            if(finished < dl)return false;
        }
        if(cnt == 0 && i > n-d)break;
    }
    return (cnt == 0);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);

    cin >> n >> d >> m;
    a = vector<vector<int>> (n-d+1);

    for(int i = 0; i < m; i++){
        int tmp; cin >> tmp;
        a[tmp].push_back(i+1);
    }

    int l = 0, r = m;
    while(l < r){
        int mid = (l+r) >> 1;
        if(check(mid))r = mid;
        else l = mid+1;
    }

    for(int i = l-1; i <= l+1; i++){
        if(check(i)){
            res = i;
            break;
        }
    }

    cout << res << '\n';

    queue<int> q;

    for(int i = 1; i <= n; i++){
        if(i <= n-d){
            for(int j = 0; j < (int)a[i].size(); j++)
                q.push(a[i][j]);
        }
        if(!q.empty())
        for(int j = 0; j < res; j++){
            cout << q.front() << ' ';
            q.pop();
            if(q.empty())break;
        }
        cout << 0 << '\n';
    }

    return 0;
}

• Subtask 1: 100 / 100