oj.uz

Submission #391403

# Submission time Handle Problem Language Result Execution time Memory
391403 2021-04-18T17:06:24 Z hopetosuccess9102 Job Scheduling (CEOI12_jobs) C++14
0 / 100
 443 ms 13860 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 36 ms 1624 KB Output isn't correct
2 Incorrect 36 ms 1632 KB Output isn't correct
3 Incorrect 35 ms 1648 KB Output isn't correct
4 Incorrect 36 ms 1596 KB Output isn't correct
5 Incorrect 36 ms 1612 KB Output isn't correct
6 Incorrect 35 ms 1660 KB Output isn't correct
7 Incorrect 36 ms 1648 KB Output isn't correct
8 Incorrect 36 ms 1604 KB Output isn't correct
9 Incorrect 56 ms 1976 KB Output isn't correct
10 Incorrect 55 ms 1944 KB Output isn't correct
11 Incorrect 48 ms 1588 KB Output isn't correct
12 Incorrect 97 ms 3144 KB Output isn't correct
13 Incorrect 141 ms 4588 KB Output isn't correct
14 Incorrect 225 ms 6348 KB Output isn't correct
15 Incorrect 237 ms 7492 KB Output isn't correct
16 Incorrect 329 ms 9088 KB Output isn't correct
17 Incorrect 396 ms 10628 KB Output isn't correct
18 Incorrect 376 ms 12280 KB Output isn't correct
19 Incorrect 443 ms 13860 KB Output isn't correct
20 Incorrect 379 ms 10636 KB Output isn't correct