제출 #292342

#제출 시각아이디문제언어결과실행 시간메모리
292342R3KTJob Scheduling (CEOI12_jobs)Java
0 / 100
1597 ms65548 KiB
import java.util.*; import java.io.*; public class jobs { // https://oj.uz/problem/view/CEOI12_jobs // TLE && RTE public static void main(String[] args) throws IOException, FileNotFoundException { //BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); //BufferedReader in = new BufferedReader(new FileReader("jobs")); Reader in = new Reader(); // StringTokenizer st = new StringTokenizer(in.readLine()); // int n = Integer.parseInt(st.nextToken()); // int d = Integer.parseInt(st.nextToken()); // int m = Integer.parseInt(st.nextToken()); int n = in.nextInt(); int d = in.nextInt(); int m = in.nextInt(); obj[] arr = new obj[m]; //st = new StringTokenizer(in.readLine()); for (int i=0; i<m; ++i) { //int v = Integer.parseInt(st.nextToken()); int v = in.nextInt(); arr[i] = new obj(v, i+1); } Arrays.parallelSort(arr); /* int min=0; int max=m; while (min < max) { int middle = (min + max)/2; if (check(arr, middle, d, n)) { max = middle; } else min = middle+1; } System.out.println(min); // construct int count=1; for (int i=0; i<m; i+=min) { for (int j=i; j<i+min && j<m; j++) { System.out.print(arr[j].pos + " "); } System.out.println(0); count++; } for (int i=count; i<=n; i++) System.out.println(0); */ } public static boolean check(obj[] arr, int num, int d, int n) { int pointer=0; int m = arr.length; for (int i=1; i<=n; i++) { if (pointer>=m) break; if (i - arr[pointer].val > d) return false; pointer += num; } if (pointer < m) return false; return true; } static class obj implements Comparable<obj> { int pos; int val; obj (int a, int b) { val = a; pos = b; } public int compareTo(obj other) { return val - other.val; } } // source: https://www.geeksforgeeks.org/fast-io-in-java-in-competitive-programming/ static class Reader { final private int BUFFER_SIZE = 1 << 16; private DataInputStream din; private byte[] buffer; private int bufferPointer, bytesRead; public Reader() { din = new DataInputStream(System.in); buffer = new byte[BUFFER_SIZE]; bufferPointer = bytesRead = 0; } public Reader(String file_name) throws IOException { din = new DataInputStream(new FileInputStream(file_name)); buffer = new byte[BUFFER_SIZE]; bufferPointer = bytesRead = 0; } public String readLine() throws IOException { byte[] buf = new byte[64]; // line length int cnt = 0, c; while ((c = read()) != -1) { if (c == '\n') break; buf[cnt++] = (byte) c; } return new String(buf, 0, cnt); } public int nextInt() throws IOException { int ret = 0; byte c = read(); while (c <= ' ') c = read(); boolean neg = (c == '-'); if (neg) c = read(); do { ret = ret * 10 + c - '0'; } while ((c = read()) >= '0' && c <= '9'); if (neg) return -ret; return ret; } public long nextLong() throws IOException { long ret = 0; byte c = read(); while (c <= ' ') c = read(); boolean neg = (c == '-'); if (neg) c = read(); do { ret = ret * 10 + c - '0'; } while ((c = read()) >= '0' && c <= '9'); if (neg) return -ret; return ret; } public double nextDouble() throws IOException { double ret = 0, div = 1; byte c = read(); while (c <= ' ') c = read(); boolean neg = (c == '-'); if (neg) c = read(); do { ret = ret * 10 + c - '0'; } while ((c = read()) >= '0' && c <= '9'); if (c == '.') { while ((c = read()) >= '0' && c <= '9') { ret += (c - '0') / (div *= 10); } } if (neg) return -ret; return ret; } private void fillBuffer() throws IOException { bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE); if (bytesRead == -1) buffer[0] = -1; } private byte read() throws IOException { if (bufferPointer == bytesRead) fillBuffer(); return buffer[bufferPointer++]; } public void close() throws IOException { if (din == null) return; din.close(); } } }
#Verdict Execution timeMemoryGrader output
Fetching results...