Submission #1300826

#TimeUsernameProblemLanguageResultExecution timeMemory
1300826sz_3312Job Scheduling (CEOI12_jobs)Java
0 / 100
1101 ms120244 KiB
import java.io.*; import java.util.*; public class jobs { static class Job { int day, id; Job(int d, int i) { day = d; id = i; } } static int N, D, M; static Job[] jobs; // Simple pass to check feasibility static boolean works(int K) { int ptr = 0; for (int day = 1; day <= N; day++) { for (int used = 0; used < K; used++) { if (ptr == M) return true; if (jobs[ptr].day > day) break; if (jobs[ptr].day + D < day) return false; ptr++; } } return ptr == M; } // Build actual schedule once, after minimal K is known static List<List<Integer>> buildSchedule(int K) { List<List<Integer>> schedule = new ArrayList<>(N); for (int i = 0; i < N; i++) schedule.add(new ArrayList<>()); int ptr = 0; for (int day = 1; day <= N; day++) { for (int used = 0; used < K; used++) { if (ptr == M) return schedule; if (jobs[ptr].day > day) break; schedule.get(day - 1).add(jobs[ptr].id); ptr++; } } return schedule; } public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nextToken()); D = Integer.parseInt(st.nextToken()); M = Integer.parseInt(st.nextToken()); jobs = new Job[M]; st = new StringTokenizer(br.readLine()); for (int i = 0; i < M; i++) { int day = Integer.parseInt(st.nextToken()); jobs[i] = new Job(day, i + 1); } Arrays.sort(jobs, Comparator.comparingInt(a -> a.day)); int lo = 1, hi = M; while (lo < hi) { int mid = (lo + hi) / 2; if (works(mid)) hi = mid; else lo = mid + 1; } int K = lo; List<List<Integer>> schedule = buildSchedule(K); StringBuilder out = new StringBuilder(); out.append(K).append("\n"); for (int day = 0; day < N; day++) { for (int id : schedule.get(day)) out.append(id).append(" "); out.append("0\n"); } System.out.print(out); } }
#Verdict Execution timeMemoryGrader output
Fetching results...