Submission #956204

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
956204	2024-04-01T10:03:58 Z	steveonalex	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	191 ms	22096 KB

jobs

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
#define MASK(i) (1ULL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
#define ALL(v) (v).begin(), (v).end()
 
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
 
ll LASTBIT(ll mask){return (mask) & (-mask);}
int pop_cnt(ll mask){return __builtin_popcountll(mask);}
int ctz(ull mask){return __builtin_ctzll(mask);}
int logOf(ull mask){return 63 - __builtin_clzll(mask);}
 
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rngesus(ll l, ll r){return l + (ull) rng() % (r - l + 1);}
 
template <class T1, class T2>
    bool maximize(T1 &a, T2 b){
        if (a < b) {a = b; return true;}
        return false;
    }
 
template <class T1, class T2>
    bool minimize(T1 &a, T2 b){
        if (a > b) {a = b; return true;}
        return false;
    }
 
template <class T>
    void printArr(T& container, string separator = " ", string finish = "\n", ostream &out = cout){
        for(auto item: container) out << item << separator;
        out << finish;
    }
 
template <class T>
    void remove_dup(vector<T> &a){
        sort(ALL(a));
        a.resize(unique(ALL(a)) - a.begin());
    }

const int N = 1e5 + 69;
vector<pair<int, int>> createQuery[N];
int destroyQuery[N];

int main(void){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n, d, m; cin >> n >> d >> m;
    vector<int> a(m);
    for(int i = 0; i<m; ++i) cin >> a[i];

    for(int i = 0; i<m; ++i) {
        createQuery[a[i]].push_back({a[i] + d, i+1});
        destroyQuery[a[i] + d]++;
    }

    int l = 1, r = m;
    while(l < r){
        int mid = (l + r) >> 1;
        bool check = true;
        int sum1 = 0, cur = 0, sum2 = 0;
        for(int i = 1; i<=n; ++i){
            sum1 += createQuery[i].size();
            sum2 += destroyQuery[i];
            cur = min(sum1, cur + mid);
            if (cur < sum2) {check = false; break;}
        }

        if (check) r = mid;
        else l = mid + 1;
    }

    int x = l;
    cout << x << "\n";

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    for(int i = 1; i<=n; ++i){
        for(auto j: createQuery[i]) pq.push(j);
        for(int j = 0; j < x; ++j){
            if (pq.empty()) break;
            pair<int, int> cur = pq.top(); pq.pop();
            cout << cur.second << " ";
        }
        cout << 0 << "\n";
    }

    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	5712 KB	Output is correct
2	Correct	21 ms	5844 KB	Output is correct
3	Correct	21 ms	5724 KB	Output is correct
4	Correct	22 ms	5844 KB	Output is correct
5	Correct	21 ms	5724 KB	Output is correct
6	Correct	20 ms	5724 KB	Output is correct
7	Correct	26 ms	5724 KB	Output is correct
8	Correct	21 ms	5712 KB	Output is correct
9	Correct	24 ms	5468 KB	Output is correct
10	Correct	26 ms	5468 KB	Output is correct
11	Correct	22 ms	4956 KB	Output is correct
12	Correct	50 ms	7376 KB	Output is correct
13	Correct	61 ms	10580 KB	Output is correct
14	Correct	102 ms	12804 KB	Output is correct
15	Correct	84 ms	14420 KB	Output is correct
16	Correct	103 ms	17040 KB	Output is correct
17	Correct	143 ms	20560 KB	Output is correct
18	Correct	171 ms	20672 KB	Output is correct
19	Correct	191 ms	22096 KB	Output is correct
20	Correct	129 ms	20620 KB	Output is correct