| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 705705 | hex | Job Scheduling (CEOI12_jobs) | Java | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
import java.io.*;
import java.util.*;
public class Main {
static class Req implements Comparable<Req> {
int day;
int id;
public Req (int day, int id) {
this.day = day;
this.id = id;
}
public int compareTo (Req r) {
//Comparing by id is not needed here.
return Integer.compare(this.day, r.day);
}
}
//Check if changing reqs to a static array will be fater
static boolean valid (int numMachine, int delay, Req[] reqs) {
int day = reqs[0].day;
int r = 0;
PriorityQueue<Integer> res = new PriorityQueue<Integer>();
while (r < reqs.length) {
int num = 0;
while (res.size() > 0 && num < numMachine) {
if (res.peek() + delay < day) return false;
res.poll();
num++;
}
num = 0;
while (r < reqs.length && num < numMachine) {
res.add(reqs[r].day);
r++;
num++;
}
day++;
}
return true;
}
public static void main (String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
PrintWriter out = new PrintWriter(System.out);
StringTokenizer st = new StringTokenizer(reader.readLine());
int days = Integer.parseInt(st.nextToken());
int delay = Integer.parseInt(st.nextToken());
int numReq = Integer.parseInt(st.nextToken());
Req[] reqs = new Req[numReq];
st = new StringTokenizer(reader.readLine());
Set<Integer> diffs = new HashSet<Integer>();
for (int r = 0; r < numReq; r++) {
reqs[r] = new Req(Integer.parseInt(st.nextToken()), r + 1);
diffs.add(reqs[r].day);
}
Arrays.sort(reqs);
int lt = 1;
int rt = (int) 10e6;
int mid;
while (lt < rt) {
mid = (lt + rt) / 2;
if (valid(mid, delay, reqs)) {
rt = mid;
} else {
lt = mid + 1;
}
}
//At the end, just loop through reqs in sorted order and print out lt ids in a single line, followed by a 0
out.println(lt);
for (int d = 0; d < reqs[0].day; d++) {
out.println(0);
}
int r = 0;
for (int d = 0; d < days; d++) {
int num = 0;
while (r < reqs.length && num < lt) {
out.print(reqs[r].id + " ");
r++;
num++;
}
out.print(0);
out.println();
}
//out.println(valid(1, delay, reqs));
out.close();
}
}
//Check N = 1.
//Check for needed longs.
//Use Long.parseLong() instead of Integer.parseInt().
//Use Long.MAX_VALUE instead of Integer.MAX_VALUE.
//Use an int array of ids instead of a boolean array of visited nodes during DFS.
//Declare a class variable instead of a method parameter, as passing by value could result in a TLE.