Submission #849221

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
849221	2023-09-14T09:28:17 Z	quanlt206	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	993 ms	26292 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

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	148 ms	6296 KB	Output is correct
2	Correct	159 ms	6244 KB	Output is correct
3	Correct	145 ms	6300 KB	Output is correct
4	Correct	146 ms	6240 KB	Output is correct
5	Correct	145 ms	6312 KB	Output is correct
6	Correct	143 ms	6232 KB	Output is correct
7	Correct	144 ms	6296 KB	Output is correct
8	Correct	144 ms	6328 KB	Output is correct
9	Correct	118 ms	6336 KB	Output is correct
10	Correct	126 ms	6552 KB	Output is correct
11	Correct	68 ms	5320 KB	Output is correct
12	Correct	232 ms	8108 KB	Output is correct
13	Correct	283 ms	11452 KB	Output is correct
14	Correct	350 ms	14780 KB	Output is correct
15	Correct	417 ms	16312 KB	Output is correct
16	Correct	350 ms	20928 KB	Output is correct
17	Correct	539 ms	23220 KB	Output is correct
18	Correct	993 ms	23600 KB	Output is correct
19	Correct	989 ms	26292 KB	Output is correct
20	Correct	528 ms	23220 KB	Output is correct