Submission #1204730

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204730		nathlol2	Job Scheduling (CEOI12_jobs)	C++20	55 / 100	178 ms	31172 KiB

jobs

#include <bits/stdc++.h>
#define int long long
#define fi first
#define sc second
using namespace std;
int n, d, m;
pair<int, int> a[1000000];
bool ok(int x){
    int now = 1;
    for(int i = 0;i<m / x;i++){
        int t = (i + 1) * x;
        for(int j = i * x;j<t;j++){
            if(a[j].fi + d < now){
                return false;
            }
        }
        now++;
    }
    for(int i = (m / x) * x;i<m;i++){
        if(a[i].fi + d < now){
            return false;
        }
    }
    return true;
}
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> n >> d >> m;
	for(int i = 0;i<m;i++){
	    cin >> a[i].fi;
	    a[i].sc = i + 1;
	}
	sort(a, a + m);
	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;
	    }
	}
	vector<vector<int>> g(n + 1);
    int now = 1;
    int x = ans;
    for(int i = 0;i<m / x;i++){
        int t = (i + 1) * x;
        for(int j = i * x;j<t;j++){
            g[now].push_back(a[j].sc);
        }
        now++;
    }
    for(int i = (m / x) * x;i<m;i++){
        g[now].push_back(a[i].sc);
    }
    cout << ans << '\n';
    for(int i = 1;i<=n;i++){
        for(auto x : g[i]){
            cout << x << ' ';
        }
        cout << 0 << '\n';
    }
}

• Subtask 1: 55 / 100