oj.uz

Submission #391402

# Submission time Handle Problem Language Result Execution time Memory
391402 2021-04-18T17:02:09 Z hopetosuccess9102 Job Scheduling (CEOI12_jobs) C++14
0 / 100
 447 ms 13924 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 = 1;
    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 37 ms 1692 KB Output isn't correct
2 Incorrect 44 ms 1664 KB Output isn't correct
3 Incorrect 35 ms 1592 KB Output isn't correct
4 Incorrect 36 ms 1704 KB Output isn't correct
5 Incorrect 36 ms 1604 KB Output isn't correct
6 Incorrect 36 ms 1712 KB Output isn't correct
7 Incorrect 36 ms 1652 KB Output isn't correct
8 Incorrect 36 ms 1604 KB Output isn't correct
9 Incorrect 63 ms 1976 KB Output isn't correct
10 Incorrect 71 ms 1964 KB Output isn't correct
11 Incorrect 49 ms 1600 KB Output isn't correct
12 Incorrect 95 ms 3104 KB Output isn't correct
13 Incorrect 142 ms 4560 KB Output isn't correct
14 Incorrect 230 ms 6152 KB Output isn't correct
15 Incorrect 233 ms 7616 KB Output isn't correct
16 Incorrect 328 ms 9236 KB Output isn't correct
17 Incorrect 382 ms 10708 KB Output isn't correct
18 Incorrect 397 ms 12112 KB Output isn't correct
19 Incorrect 447 ms 13924 KB Output isn't correct
20 Incorrect 379 ms 10756 KB Output isn't correct