Submission #642575

#	Time	Username	Problem	Language	Result	Execution time	Memory
642575		accidentac	Job Scheduling (CEOI12_jobs)	Java	0 / 100	1102 ms	39184 KiB

jobs

import java.util.*;
import java.lang.*;
import java.io.*;

class jobs {
  static int[][] jobs;
  static int n, d, m;

  static List<List<Integer>> dummy() {
    List<List<Integer>> res = new ArrayList<>();
    res.add(new ArrayList<>());
    return res;
  }

  // return true if there is a way to use `count` no. of machines to solve
  static boolean ok(int count) {
    for (int day = 1, l = 0, r = 0; day <= n; day++) {
      while (r < m && jobs[r][0] >= day) {
        r++;
      }
      int filled = 0;
      while (l < r && filled < count) {
        if (day - jobs[l][0] > d)
          return false;
        l++;
        filled++;
        if (l == m)
          return true;
      }
    }
    return false;
  }

  public static void main(String[] args) throws java.lang.Exception {
    Reader r = new Reader();
    n = r.nextInt();
    d = r.nextInt();
    m = r.nextInt();
    jobs = new int[m][2];
    for (int i = 0; i < m; i++) {
      int day = r.nextInt();
      jobs[i][0] = day;
      jobs[i][1] = i + 1;
    }
    Arrays.sort(jobs, (a, b) -> Integer.compare(a[0], b[0]));
    int lo = 1, hi = m, best = m;
    while (lo <= hi) {
      int mid = lo + (hi - lo) / 2;
      if (ok(mid)) {
        best = mid;
        hi = mid - 1;
      } else {
        lo = mid + 1;
      }
    }
    System.out.println(best);
    for (int i = 0; i < n; i++) {
      System.out.println(0);
    }
    r.close();
  }
}

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