oj.uz

답안 #305722

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
305722 2020-09-23T21:47:02 Z aZvezda Job Scheduling (CEOI12_jobs) C++14
95 / 100
 1000 ms 23764 KB 
#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

# 결과 실행 시간 메모리 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