oj.uz

Submission #391432

# Submission time Handle Problem Language Result Execution time Memory
391432 2021-04-18T18:03:38 Z hopetosuccess9102 Job Scheduling (CEOI12_jobs) C++14
0 / 100
 599 ms 14212 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 < n - m / l; ++i) cout << 0 << endl;
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 51 ms 1740 KB Output isn't correct
2 Incorrect 58 ms 1748 KB Output isn't correct
3 Incorrect 61 ms 1788 KB Output isn't correct
4 Incorrect 62 ms 1724 KB Output isn't correct
5 Incorrect 58 ms 1720 KB Output isn't correct
6 Incorrect 51 ms 1776 KB Output isn't correct
7 Incorrect 62 ms 1736 KB Output isn't correct
8 Incorrect 51 ms 1784 KB Output isn't correct
9 Incorrect 220 ms 2448 KB Output isn't correct
10 Incorrect 212 ms 2336 KB Output isn't correct
11 Incorrect 49 ms 1732 KB Output isn't correct
12 Incorrect 95 ms 3248 KB Output isn't correct
13 Incorrect 145 ms 4744 KB Output isn't correct
14 Incorrect 224 ms 6264 KB Output isn't correct
15 Incorrect 240 ms 7740 KB Output isn't correct
16 Incorrect 333 ms 9396 KB Output isn't correct
17 Incorrect 387 ms 10820 KB Output isn't correct
18 Incorrect 394 ms 12256 KB Output isn't correct
19 Incorrect 599 ms 14212 KB Output isn't correct
20 Incorrect 394 ms 10852 KB Output isn't correct