Submission #500128

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
500128	2021-12-30T10:54:51 Z	mhsi2005	Job Scheduling (CEOI12_jobs)	C++17	40 / 100	1000 ms	12408 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];

bool ok (ll x)
{
    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--;
        s.insert(max(*it, a[i].first) + 1);
        s.erase(it);
    }
    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';

    vector<int> ans[(int)1e5 + 10];
    multiset<int> s;
    for (int i = 1; i <= r; i++)
        s.insert(1);
    for (int i = 0; i < m; i++) {
        auto it = s.upper_bound(a[i].first + d);
        if (it != s.begin())
            it--;
//        watch2(*it, a[i].first)
        ans[max(*it, a[i].first)].push_back(a[i].second);
        s.insert(max(*it, a[i].first) + 1);
        s.erase(it);
//        for (int i : s)
//            cout << i << ' ';
//        cout << '\n';
    }
//    cout << '\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	406 ms	6984 KB	Output is correct
2	Correct	426 ms	6976 KB	Output is correct
3	Correct	380 ms	6980 KB	Output is correct
4	Correct	399 ms	6924 KB	Output is correct
5	Correct	397 ms	6976 KB	Output is correct
6	Correct	384 ms	6932 KB	Output is correct
7	Correct	454 ms	6948 KB	Output is correct
8	Correct	388 ms	6928 KB	Output is correct
9	Incorrect	223 ms	6480 KB	Output isn't correct
10	Incorrect	242 ms	6564 KB	Output isn't correct
11	Incorrect	273 ms	6456 KB	Output isn't correct
12	Incorrect	508 ms	7964 KB	Output isn't correct
13	Incorrect	672 ms	9248 KB	Output isn't correct
14	Incorrect	935 ms	10944 KB	Output isn't correct
15	Execution timed out	1077 ms	12408 KB	Time limit exceeded
16	Execution timed out	1095 ms	9564 KB	Time limit exceeded
17	Execution timed out	1092 ms	10432 KB	Time limit exceeded
18	Execution timed out	1083 ms	11220 KB	Time limit exceeded
19	Execution timed out	1085 ms	12000 KB	Time limit exceeded
20	Execution timed out	1086 ms	10436 KB	Time limit exceeded