# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
896272 | akkshaysr | Job Scheduling (CEOI12_jobs) | C++17 | 332 ms | 28196 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 <bits/stdc++.h>
#define fr first
#define se second
#define rep(i,a,b) for(int i = a; i < (b); ++i)
#define repr(i,a,b) for(int i = a; i > (b); --i)
#define sz(x) (int)(x).size()
#define all(x) (x).begin(),(x).end()
#define IN(i,l,r) (l<i&&i<r)
#define pb push_back
using namespace std;
typedef pair<int,int> pi;
typedef vector<int> vi;
typedef long long ll;
const int U = 1e6+2;
int N,D,M;
pi job[U];
pair<bool,vector<vi>> check(int m){
vector<vi> s(N);
int t=0;
rep(day,1,N+1){
rep(i,0,m){
if(job[t].fr > day){
break;
}
if(job[t].fr + D >= day){
s[day-1].pb(job[t].se);
++t;
}else{
return {false,s};
}
if(t==M) return {true,s};
}
}
cout << "over" << '\n';
return {false,s};
}
int main(){
cin.tie(0)->sync_with_stdio(false);
cin >> N >> D >> M;
rep(i,0,M){
cin >> job[i].fr;
job[i].se = i+1;
}
sort(job,job+M);
int lo=1,hi=M;
vector<vi> s;
while(lo < hi){
ll m = (lo+hi)/2;
pair<bool,vector<vi>> res = check(m);
if(res.fr){
hi = m;
s = res.se;
}else{
lo = m+1;
}
}
cout << hi << '\n';
for(auto &v:s){
for(auto &e:v){
cout << e << ' ';
}
cout << "0\n";
}
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |