Submission #849217

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
849217	2023-09-14T09:25:49 Z	quanlt206	Job Scheduling (CEOI12_jobs)	C++14	95 / 100	1000 ms	26056 KB

jobs

#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

#	Verdict	Execution time	Memory	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