Submission #1085547

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085547		vjudge1	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	290 ms	21396 KiB

jobs

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


const int N = 1e6 + 20;

int n, d, m;
ar<int, 2> A[N];

bool check(int x){
    int l = 0, r = 0;
    for(int i = 1;i <= n;i++){
        //cout<<l<<" "<<r<<'\n';
        while(r < m && A[r][0] == i)++r;
        if(l != r && l < m && i - A[l][0] > d)return 0;
        l = min(l + x, r);
    }
    return l == r && r== m;
}

void print(int x){
    int l = 0, r = 0;
    for(int i = 1;i <= n;i++){
        while(r < m && A[r][0] == i)++r;

        for(;l < min(l + x, r);l++){
            cout<<A[l][1]<<' ';
        }
        cout<<"0"<<endl;
        ++l;
    }
   
}

signed main() {ios_base::sync_with_stdio(false);cin.tie(0);
    cin>>n>>d>>m;
    for(int i = 0;i < m;i++){
        cin>>A[i][0];
        A[i][1] = 1 + i;
    }
    sort(A, A + m);
    int lo = 1, hi = m;
    int ans = m;
    //cout<<check(7);
    while(lo <= hi){
        //cout<<lo<<" "<<hi<<endl;
        int mid = (lo + hi) / 2;
        if(check(mid)){
            ans = mid;
            hi = mid - 1;
        }else lo = mid + 1;
    }
    cout<<ans<<endl;
    print(ans);
}

• Subtask 1: 100 / 100