Submission #956202

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
956202	2024-04-01T10:01:59 Z	steveonalex	Job Scheduling (CEOI12_jobs)	C++17	80 / 100	189 ms	36176 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], 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].push_back({a[i] + d, i+ 1});
    }

    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].size();
            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

80.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	8900 KB	Output is correct
2	Correct	21 ms	8844 KB	Output is correct
3	Correct	21 ms	8900 KB	Output is correct
4	Correct	21 ms	8912 KB	Output is correct
5	Correct	21 ms	8904 KB	Output is correct
6	Correct	27 ms	8904 KB	Output is correct
7	Correct	21 ms	8904 KB	Output is correct
8	Correct	22 ms	8820 KB	Output is correct
9	Correct	26 ms	9032 KB	Output is correct
10	Correct	27 ms	9040 KB	Output is correct
11	Correct	24 ms	8540 KB	Output is correct
12	Correct	48 ms	12200 KB	Output is correct
13	Correct	69 ms	18004 KB	Output is correct
14	Correct	115 ms	21864 KB	Output is correct
15	Correct	87 ms	24148 KB	Output is correct
16	Correct	112 ms	29292 KB	Output is correct
17	Runtime error	147 ms	36176 KB	Memory limit exceeded
18	Runtime error	176 ms	34324 KB	Memory limit exceeded
19	Runtime error	189 ms	36068 KB	Memory limit exceeded
20	Runtime error	156 ms	35924 KB	Memory limit exceeded