Submission #391403

#	Time	Username	Problem	Language	Result	Execution time	Memory
391403		hopetosuccess9102	Job Scheduling (CEOI12_jobs)	C++14	0 / 100	443 ms	13860 KiB

jobs

#include <iostream>
#include <algorithm>
#include <tuple>
using namespace std;
#define pi pair<int, int>
#define f first
#define s second

int n, d, m;
int j[100001];
pi jd[1000000];

bool q(int x) {
    int cd = 0;
    int cj[100001];
    for (int i = 1; i <= n; ++i) {
        cj[i] = j[i];
    }
    for (int i = 1; i <= n; ++i) {
        if (cj[i] % x == 0 || cj[i] < x) {
            if (cd + cj[i] / x - i >= d) return false;
            cd += cj[i] / x;
        }
        else {
            if (cd + cj[i] / x + 1 - i >= d) return false;
            cd += cj[i] / x + 1;
        }
        if (i != n) {
            if (cj[i + 1] >= x - (cj[i] - x * (cj[i] / x)))
                cj[i + 1] -= x - (cj[i] - x * (cj[i] / x));
            else cj[i + 1] = 0;
        }
    }
    return true;
}

int main() {
	cin >> n >> d >> m;
	for (int i = 0; i < m; ++i) {
	    int a; cin >> a;
	    ++j[a];
	    jd[i] = {a, i + 1};
	}
	sort(jd, jd + m);
	int l = 0, r = 1000000;
	for (r ++; l < r; ) {
	    int m = l + (r - l) / 2;
	    if (q(m)) r = m;
	    else l = m + 1;
	}
	cout << l << endl;
	for (int i = 0; i < m; i += l) {
	    for (int j = 0; j < l; ++j) {
	        cout << jd[i + j].s << ' ';
	    }
	    cout << 0 << endl;
	}
	for (int i = 0; i < d; ++i) cout << 0 << endl;
}

• Subtask 1: 0 / 100