Submission #899718

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
899718	2024-01-06T22:46:01 Z	Karoot	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	333 ms	22868 KB

jobs

#include <iostream>
#include <cmath>
#include <unordered_map>
#include <map>
#include <set>
#include <queue>
#include <vector>
#include <string>
#include <iomanip>
#include <algorithm>

#define all(x)  (x).begin(), (x).end()
#define rall(x)  (x).rbegin(), (x).rend()

using namespace std;

typedef long long ll;

ll linf = 1e15+1;

inline void scoobydoobydoo(){
    ios::sync_with_stdio(false);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
}

const int MAXN = 1e5+1;

vector<int> v[MAXN];
vector<int> schedule[MAXN];
int n, d, m; 

bool isPossible(int machines){
    queue<pair<int, int> > q;
    for (int i = 0; i < n; i++){
        schedule[i].clear();
        for (int x : v[i])q.push({x, i+d});
        for (int j = 0; j < machines && !q.empty(); j++){
            int node = q.front().first;
            int t = q.front().second;
            q.pop();
            schedule[i].push_back(node);
            if (t < i)return false;
        }
    }
    return true;
}

int main(){
    scoobydoobydoo();
    cin >> n >> d >> m;
    for (int i = 0; i < m; i++){
        int a; cin >> a;
        v[--a].push_back(i+1);
    }

    int a = 1, b = 1000001;
    int ret = -1;
    while (a < b){
        int k = (a+b)>>1;
        if (isPossible(k)){
            b = k;
            ret = k;
        } else {
            a = k+1;
        }
    }


    isPossible(ret);

    cout << ret << endl;
    for (int i = 0; i < n; i++){
        for (int x : schedule[i])cout << x << " ";
        cout << 0 << endl;
    }







    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	30 ms	8160 KB	Output is correct
2	Correct	31 ms	7900 KB	Output is correct
3	Correct	32 ms	7896 KB	Output is correct
4	Correct	40 ms	7764 KB	Output is correct
5	Correct	43 ms	7840 KB	Output is correct
6	Correct	40 ms	7904 KB	Output is correct
7	Correct	37 ms	7900 KB	Output is correct
8	Correct	44 ms	7916 KB	Output is correct
9	Correct	128 ms	7284 KB	Output is correct
10	Correct	135 ms	7256 KB	Output is correct
11	Correct	24 ms	7248 KB	Output is correct
12	Correct	50 ms	9216 KB	Output is correct
13	Correct	74 ms	12300 KB	Output is correct
14	Correct	96 ms	15028 KB	Output is correct
15	Correct	97 ms	15624 KB	Output is correct
16	Correct	172 ms	18468 KB	Output is correct
17	Correct	152 ms	22788 KB	Output is correct
18	Correct	169 ms	21324 KB	Output is correct
19	Correct	333 ms	22824 KB	Output is correct
20	Correct	273 ms	22868 KB	Output is correct