Submission #93994

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
93994	2019-01-14T11:42:03 Z	rkocharyan	Job Scheduling (CEOI12_jobs)	C++14	60 / 100	158 ms	13284 KB

jobs

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 7;

int n, d, m;
int f[N];
vector <int> g[N];

bool check(int t) {
    deque < pair <int, int> > h;
    for(int i = 1; i <= n; i++) {
        if(f[i]) h.emplace_back(i, f[i]);
        int cur_t = t;
        while(!h.empty() && cur_t) {
            if(i - h[0].first > d) return false;
            int next_t = cur_t;
            next_t -= min(h[0].second, cur_t);
            h[0].second -= min(h[0].second, cur_t);
            cur_t = next_t;
            if(h[0].second == 0) {
                h.pop_front();
            }
        }
    }
    if(h.size()) return false;
    return true;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> d >> m;
    for(int i = 0; i < m; i++) {
        int x;
        cin >> x;
        f[x]++;
        g[x].push_back(i + 1);
    }
    int low = 1, high = n, best = n;
    while(low <= high) {
        int mid = (low + high) >> 1;
        if(check(mid)) {
            best = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    cout << best << '\n';
    deque < pair <int, int> > h;
    for(int i = 1; i <= n; i++) {
        if(f[i]) h.emplace_back(i, f[i]);
        int cur_t = best;
        while(!h.empty() && cur_t) {
            int next_t = cur_t;
            for(int j = 0; j < min(h[0].second, cur_t); j++) {
                cout << g[h[0].first].back() << ' ';
                g[h[0].first].pop_back();
            }
            next_t -= min(h[0].second, cur_t);
            h[0].second -= min(h[0].second, cur_t);
            cur_t = next_t;
            if(h[0].second == 0) {
                h.pop_front();
            }
        }
        cout << "0\n";
    }
    return 0;
}

Subtask #1

60.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	18 ms	3800 KB	Output isn't correct
2	Incorrect	18 ms	3828 KB	Output isn't correct
3	Incorrect	18 ms	3956 KB	Output isn't correct
4	Incorrect	18 ms	3828 KB	Output isn't correct
5	Incorrect	17 ms	3800 KB	Output isn't correct
6	Incorrect	18 ms	3828 KB	Output isn't correct
7	Incorrect	18 ms	3828 KB	Output isn't correct
8	Incorrect	17 ms	3828 KB	Output isn't correct
9	Correct	23 ms	4088 KB	Output is correct
10	Correct	21 ms	4088 KB	Output is correct
11	Correct	20 ms	3832 KB	Output is correct
12	Correct	38 ms	4924 KB	Output is correct
13	Correct	50 ms	6776 KB	Output is correct
14	Correct	85 ms	8056 KB	Output is correct
15	Correct	94 ms	9116 KB	Output is correct
16	Correct	134 ms	10744 KB	Output is correct
17	Correct	158 ms	12664 KB	Output is correct
18	Correct	131 ms	12536 KB	Output is correct
19	Correct	153 ms	13284 KB	Output is correct
20	Correct	153 ms	12536 KB	Output is correct