Submission #1086800

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086800		Icelast	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	217 ms	26960 KiB

jobs

#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 4e18+9;
void solve(){
    int n, D, m;
    cin >> n >> D >> m;
    vector<int> a(m+1);
    vector<vector<int>> b(n+1);
    for(int i = 1; i <= m; i++){
        cin >> a[i];
        b[a[i]].push_back(i);
    }
    vector<vector<int>> ans(n+1);
    auto check = [&](int x) -> bool{
        queue<int> q;
        for(int i = 1; i <= n; i++){
            ans[i].clear();
            for(int j : b[i]){
                q.push(j);
            }
            int cnt = x;
            while(!q.empty() && cnt > 0){
                cnt--;
                int j = q.front();
                q.pop();
                ans[i].push_back(j);
                if(a[j]+D < i) return 0;
            }
        }
        return q.empty();
    };
    int l = 1, r = m, mid;
    while(l <= r){
        mid = (l+r)/2;
        if(check(mid)){
            r = mid-1;
        }else{
            l = mid+1;
        }
    }
    check(l);
    cout << l << "\n";
    for(int i = 1; i <= n; i++){
        for(int j : ans[i]){
            cout << j << " ";
        }
        cout << "0\n";
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}

• Subtask 1: 100 / 100