Submission #292342

#	Time	Username	Problem	Language	Result	Execution time	Memory
292342		R3KT	Job Scheduling (CEOI12_jobs)	Java	0 / 100	1597 ms	65548 KiB

jobs

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(); 
        } 
    }
		
}

• Subtask 1: 0 / 100