# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
521105 | it111 | Job Scheduling (CEOI12_jobs) | C++14 | 255 ms | 16720 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
struct uzsakymas{
int diena;
int eilesNr;
int priimtas;
};
uzsakymas uzsakymai[1000005];
int n,d,m;
bool rikiavimas (uzsakymas a, uzsakymas b){
return a.diena<b.diena;
}
bool tinka(int dirba){
int dabarDiena = 1;
for(int i = 0; i<m; i++){
for(int j = 0; j<dirba; j++){
if(dabarDiena-uzsakymai[i].diena>d){
return false;
}
uzsakymai[i].priimtas = dabarDiena;
i++;
if(i==m){
return true;
}
}
i--;
dabarDiena++;
}
return true;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> d >> m;
for(int i = 1; i<=m; i++){
int a; cin >> a;
uzsakymai[i-1].diena = a;
uzsakymai[i-1].eilesNr = i;
}
sort(uzsakymai,uzsakymai+m,rikiavimas);
int k = 1; int d = (m/n)+1;
int ats = INT_MAX;
while(k<d){
int v = (k+d+1)/2;
if(tinka(v)){
ats = min(ats,v);
d = v-1;
} else{
k = v;
}
}
cout << ats << endl;
int nr = 0;
for(int i = 1; i<=n; i++){
while(uzsakymai[nr].priimtas==i and nr<m){
cout << uzsakymai[nr].eilesNr << " ";
nr++;
}
cout << 0 << endl;
}
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |