oj.uz

답안 #305719

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
305719 2020-09-23T21:41:05 Z aZvezda Job Scheduling (CEOI12_jobs) C++14
55 / 100
 190 ms 4600 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 = 1e5 + 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);
    p.resize(unique(p.begin(), p.end()) - p.begin());
    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
55.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 167 ms 3752 KB Output is correct
2 Correct 165 ms 3748 KB Output is correct
3 Correct 168 ms 3720 KB Output is correct
4 Correct 164 ms 3860 KB Output is correct
5 Correct 162 ms 3716 KB Output is correct
6 Correct 162 ms 3756 KB Output is correct
7 Correct 190 ms 3716 KB Output is correct
8 Correct 161 ms 3748 KB Output is correct
9 Correct 138 ms 3180 KB Output is correct
10 Correct 153 ms 3312 KB Output is correct
11 Correct 98 ms 3056 KB Output is correct
12 Runtime error 14 ms 4600 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 13 ms 4600 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 14 ms 4600 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 14 ms 4600 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 15 ms 4472 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 14 ms 4600 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 14 ms 4472 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 14 ms 4600 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 14 ms 4600 KB Execution killed with signal 11 (could be triggered by violating memory limits)