Submission #642574

#	Time	Username	Problem	Language	Result	Execution time	Memory
642574		accidentac	Job Scheduling (CEOI12_jobs)	Java	0 / 100	1095 ms	62028 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 {
    Kattio io = new Kattio();
    n = io.nextInt();
    d = io.nextInt();
    m = io.nextInt();
    jobs = new int[m][2];
    for (int i = 0; i < m; i++) {
      int day = io.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;
      }
    }
    io.println(best);
    for (int i = 0; i < n; i++) {
      io.println(0);
    }
    io.close();
  }
}

class Kattio extends PrintWriter {

  private BufferedReader r;

  private StringTokenizer st;

  // standard input

  public Kattio() {
    this(System.in, System.out);
  }

  public Kattio(InputStream i, OutputStream o) {

    super(o);

    r = new BufferedReader(new InputStreamReader(i));

  }

  // USACO-style file input

  public Kattio(String problemName) throws IOException {

    super(problemName + ".out");

    r = new BufferedReader(new FileReader(problemName + ".in"));

  }

  // returns null if no more input

  public String next() {

    try {

      while (st == null || !st.hasMoreTokens())

        st = new StringTokenizer(r.readLine());

      return st.nextToken();

    } catch (Exception e) {
    }

    return null;

  }

  public int nextInt() {
    return Integer.parseInt(next());
  }

  public double nextDouble() {
    return Double.parseDouble(next());
  }

  public long nextLong() {
    return Long.parseLong(next());
  }

}

• Subtask 1: 0 / 100