oj.uz

답안 #849217

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
849217 2023-09-14T09:25:49 Z quanlt206 Job Scheduling (CEOI12_jobs) C++14
95 / 100
 1000 ms 26056 KB 
#include<bits/stdc++.h>
#define X first
#define Y second
#define all(x) begin(x), end(x)
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define FORD(i, b, a) for(int i = (b); i >= (a); i--)
#define REP(i, a, b) for (int i = (a); i < (b); i++)
#define mxx max_element
#define mnn min_element
#define SQR(x) (1LL * (x) * (x))
#define MASK(i) (1LL << (i))
#define Point Vector
#define left Left
#define right Right
#define div Div

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;
typedef pair<db, db> pdb;
typedef pair<ld, ld> pld;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<ll, ll> pll;
typedef pair<ll, pll> plll;
typedef pair<ll, int> pli;
typedef pair<ll, pii> plii;

template<class A, class B>
    bool maximize(A& x, B y) {
        if (x < y) return x = y, true; else return false;
    }
template<class A, class B>
    bool minimize(A& x, B y) {
        if (x > y) return x = y, true; else return false;
    }
/* END OF TEMPLATE */

const int N = 1e5 + 7;

vector<pii> query[N];
vector<int> res, ans;

int n, m, d;

bool check(int x) {
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    ans.clear();
    FOR(i, 1, n) {
        for (auto x : query[i]) pq.push({x.X, x.Y});
        int m = x;
//        cout<<i<<" "<<pq.size()<<"\n";
        while (m > 0 && !pq.empty()) {
            pii tmp = pq.top();
            pq.pop();
            int r = tmp.X, idx = tmp.Y;
            if (r < i) return false;
            ans.push_back(idx);
            m--;
        }
        ans.push_back(0);
    }
    if (!pq.empty()) return false;
    return true;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>d>>m;
    FOR(i, 1, m) {
        int x;
        cin>>x;
        query[x].push_back({x + d, i});
    }
    int d = 1, c = m, g, result = 0;
//    check(1);
//    exit(0);
    while (d <= c) {
        g = (d + c) >> 1;
        if (check(g)) {
            result = g;
            res = ans;
            c = g - 1;
        }
        else d = g + 1;
    }
    cout<<result<<"\n";
    for (auto x : res) cout<<x<<" \n"[x == 0];
    return 0;
}

Subtask #1
95.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 149 ms 6396 KB Output is correct
2 Correct 143 ms 6296 KB Output is correct
3 Correct 145 ms 6284 KB Output is correct
4 Correct 143 ms 6248 KB Output is correct
5 Correct 145 ms 6284 KB Output is correct
6 Correct 147 ms 6244 KB Output is correct
7 Correct 148 ms 6288 KB Output is correct
8 Correct 143 ms 6472 KB Output is correct
9 Correct 117 ms 6336 KB Output is correct
10 Correct 122 ms 6544 KB Output is correct
11 Correct 67 ms 5364 KB Output is correct
12 Correct 233 ms 8112 KB Output is correct
13 Correct 291 ms 11952 KB Output is correct
14 Correct 345 ms 14596 KB Output is correct
15 Correct 417 ms 16060 KB Output is correct
16 Correct 354 ms 19516 KB Output is correct
17 Correct 569 ms 23888 KB Output is correct
18 Execution timed out 1004 ms 24152 KB Time limit exceeded
19 Correct 993 ms 26056 KB Output is correct
20 Correct 563 ms 23308 KB Output is correct