| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 723755 | Toxtaq | Job Scheduling (CEOI12_jobs) | C++17 | 0 ms | 0 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<vector>
#include<map>
using namespace std;
int n, d, m;
vector<vector<int>>jobs;
bool check(int mid, vector<vector<int>>&tempo){
int day = 1, job = 0, current_day = 1;
while(current_day <= n- d){
for(int i = 0;i < mid;++i){
if(day > current_day)break;
//cout << current_day << " " << day << " " << job << '\n';
if(current_day-day<=d)tempo[current_day].push_back(jobs[day][job]);
else{
// cout << "$\n";
return false;
}
job++;
if(day == n - d&&job ==jobs[n-d].size()){
// cout << "£\n";
return true;
}
if(job == jobs[day].size()){day++;job=0;}
}
current_day++;
}
// cout << "€\n";
return false;
}
int main(){
cin >> n >> d >> m;
jobs.resize(n+1);
for(int i = 1;i <= m;++i){
int a;
cin >> a;
jobs[a].push_back(i);
}
int l = 1, r = m, ans = m;
vector<vector<int>>res(n+1);
while(r>=l){
int mid = (l+r)>> 1;
vector<vector<int>>tempo(n+1); // cout << "[" << l << ", " << r << "]\n";
if(check(mid, tempo)){
res=tempo;
r = mid - 1;
ans = min(ans, mid);
}
else{
l = mid + 1;
}
}
cout << ans << '\n';
for(int i = 1;i<=n;++i){
for(int j : res[i]){
cout << j << " ";
}
cout << "0\n";
}
}
int main(){
cin >> n >> d >> m;
jobs.resize(n+1);
for(int i = 1;i <= m;++i){
int a;
cin >> a;
jobs[a].push_back(i);
}
int l = 1, r = m, ans = m;
vector<vector<int>>res(n+1);
while(r>=l){
int mid = (l+r)>> 1;
vector<vector<int>>tempo(n+1); // cout << "[" << l << ", " << r << "]\n";
if(check(mid, tempo)){
res=tempo;
r = mid - 1;
ans = min(ans, mid);
}
else{
l = mid + 1;
}
}
cout << ans << '\n';
for(int i = 1;i<=n;++i){
for(int j : res[i]){
cout << j << " ";
}
cout << "0\n";
}
}