# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
899718 | Karoot | Job Scheduling (CEOI12_jobs) | C++17 | 333 ms | 22868 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |