Submission #305722

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
305722	2020-09-23T21:47:02 Z	aZvezda	Job Scheduling (CEOI12_jobs)	C++14	95 / 100	1000 ms	23764 KB

jobs

#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e9 + 7;
template<class T> inline void fix(T &x) {if(x >= mod | x <= -mod) {x %= mod;} if(x < 0) {x += mod;}}
#define out(x) cout << __LINE__ << ": " << (#x) << " = " << (x) << endl

const int MAX_N = 1e6 + 10;
pair<int, int> arr[MAX_N];
vector<int> p;
int n, d, m;

bool eval(int x) {
    priority_queue<int> pq;
    int ind = 0;
    for(int i = 1; i <= m; i ++) {
        while(ind < n && arr[ind].first == i) {
            pq.push(-arr[ind].first - d);
            ind ++;
        }
        for(int j = 0; j < x; j ++) {
            if(pq.empty()) {break;}
            pq.pop();
        }
        if(!pq.empty() && -pq.top() <= i) {
            return false;
        }
    }
    return true;
}

void print(int x) {
    priority_queue<pair<int, int> > pq;
    int ind = 0;
    for(int i = 1; i <= m; i ++) {
        while(ind < n && arr[ind].first == i) {
            pq.push({-arr[ind].first - d, arr[ind].second + 1});
            ind ++;
        }
        for(int j = 0; j < x; j ++) {
            if(pq.empty()) {break;}
            cout << pq.top().second << " ";
            pq.pop();
        }
        cout << 0 << endl;
    }
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> m >> d >> n;
    for(int i = 0; i < n; i ++) {
        cin >> arr[i].first;
        arr[i].second = i;
        p.push_back(arr[i].first);
        p.push_back(arr[i].first + d);
    }
    sort(arr, arr + n);
    int l = 0, r = mod;
    while(l < r - 1) {
        int m = (l + r) / 2ll;
        if(eval(m)) {
            r = m;
        } else {
            l = m;
        }
    }
    cout << r << endl;
    print(r);
    return 0;

}

/*
8 2 12
1 2 4 2 1 3 5 6 2 3 6 4
*/

Subtask #1

95.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	163 ms	3492 KB	Output is correct
2	Correct	160 ms	3460 KB	Output is correct
3	Correct	163 ms	3508 KB	Output is correct
4	Correct	162 ms	3500 KB	Output is correct
5	Correct	158 ms	3592 KB	Output is correct
6	Correct	159 ms	3464 KB	Output is correct
7	Correct	160 ms	3432 KB	Output is correct
8	Correct	161 ms	3496 KB	Output is correct
9	Correct	135 ms	2928 KB	Output is correct
10	Correct	154 ms	2924 KB	Output is correct
11	Correct	94 ms	2672 KB	Output is correct
12	Correct	275 ms	5352 KB	Output is correct
13	Correct	328 ms	7672 KB	Output is correct
14	Correct	509 ms	11492 KB	Output is correct
15	Correct	476 ms	13052 KB	Output is correct
16	Correct	533 ms	16212 KB	Output is correct
17	Correct	713 ms	19032 KB	Output is correct
18	Correct	958 ms	20948 KB	Output is correct
19	Execution timed out	1016 ms	23764 KB	Time limit exceeded
20	Correct	693 ms	19080 KB	Output is correct