Submission #500146

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
500146	2021-12-30T11:37:18 Z	mhsi2005	Job Scheduling (CEOI12_jobs)	C++17	40 / 100	1000 ms	16044 KB

jobs

// In the name of God

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T> using indexed_set = tree<T, null_type, less<T>,
	rb_tree_tag, tree_order_statistics_node_update>;

#define watch(x) cerr << "{" << (#x) << " = " << x << "}" << '\n';
#define watch2(x, y) cerr << "{" << (#x) << " = " << x << ", " << (#y) << " = " << y << "}" << '\n';
#define watch3(x, y, z) cerr << "{" << (#x) << " = " << x << ", " << (#y) << " = " << y << ", " << (#z) << " = " << z << "}" << '\n';
#define fast_io ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);

const ll maxn = 1e6 + 10, INF = 1e9;

int n, d, m;
pii a[maxn];
vector<vector<int>> ans(n);

bool ok (int x)
{
    ans.clear();
    ans.resize(n+10);
    multiset<int> s;
    for (int i = 0; i < x; i++)
        s.insert(1);
    for (int i = 0; i < m; i++) {
        auto it = s.upper_bound(a[i].first + d);
        if (it == s.begin()) {
            if (*it - a[i].first > d)
                return false;
        }
        else
            it--;
        assert(it != s.end());
        int f = *it;
        s.erase(it);
        s.insert(max(f, a[i].first) + 1);
        ans[max(f, a[i].first)].push_back(a[i].second);
    }
    return true;
}

int main()
{
    fast_io

    cin >> n >> d >> m;
    for (int i = 0; i < m; i++) {
        cin >> a[i].first;
        a[i].second = i+1;
    }
    sort(a, a + m);
    int l = 0, r = 1e5;
    while (r > l + 1) {
        int mid = (r + l) / 2;
        if (ok(mid)) r = mid;
        else l = mid;
    }

    cout << r << '\n';

    for (int i = 1; i <= n; i++) {
        for (int x : ans[i]) {
            cout << x << ' ';
        }
        cout << 0 << '\n';
    }

	return 0;
}

Subtask #1

40.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	409 ms	5056 KB	Output is correct
2	Correct	409 ms	4964 KB	Output is correct
3	Correct	397 ms	4912 KB	Output is correct
4	Correct	416 ms	4956 KB	Output is correct
5	Correct	393 ms	5016 KB	Output is correct
6	Correct	423 ms	5016 KB	Output is correct
7	Correct	396 ms	4968 KB	Output is correct
8	Correct	407 ms	5112 KB	Output is correct
9	Incorrect	238 ms	6676 KB	Output isn't correct
10	Incorrect	257 ms	6564 KB	Output isn't correct
11	Incorrect	265 ms	4172 KB	Output isn't correct
12	Incorrect	509 ms	5688 KB	Output isn't correct
13	Incorrect	706 ms	7032 KB	Output isn't correct
14	Incorrect	970 ms	8480 KB	Output isn't correct
15	Execution timed out	1073 ms	10076 KB	Time limit exceeded
16	Execution timed out	1090 ms	10312 KB	Time limit exceeded
17	Execution timed out	1095 ms	13424 KB	Time limit exceeded
18	Execution timed out	1086 ms	13216 KB	Time limit exceeded
19	Execution timed out	1078 ms	16044 KB	Time limit exceeded
20	Execution timed out	1091 ms	13356 KB	Time limit exceeded