Submission #642595

#	Time	Username	Problem	Language	Result	Execution time	Memory
642595		accidentac	Job Scheduling (CEOI12_jobs)	Java	40 / 100	1099 ms	39256 KiB

jobs

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

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

  static void form(int count) {
    for (int day = 1, l = 0, r = 0; day <= n; day++) {
      while (r < m && jobs[r][0] == day) {
        r++;
      }
      for (int rep = 0; rep < count && l < r; rep++) {
        out.print(jobs[l++][1]);
        out.print(' ');
      }
      out.println(0);
    }
  }

  // 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++;
      }
      if (l < r && day - jobs[l][0] > d)
        return false;
      for (int rep = 0; rep < count && l < r; rep++) {
        l++;
      }
    }
    return true;
  }

  public static void solve() {
    n = ni();
    d = ni();
    m = ni();
    jobs = new int[m][2];
    for (int i = 0; i < m; i++) {
      int day = ni();
      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;
      }
    }
    out.println(best);
    form(best);
  }

  /* I/O Template from uwi */
  static InputStream is;
  static PrintWriter out;
  static String INPUT = "";
  static String taskName = null;

  public static void main(String[] args) throws Exception {
    long S = System.currentTimeMillis();
    if (taskName != null) {
      File initialFile = new File(taskName + ".in");
      is = new FileInputStream(initialFile);
      out = new PrintWriter(taskName + ".out");
    } else {
      is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
      out = new PrintWriter(System.out);
    }

    solve();
    out.flush();
    long G = System.currentTimeMillis();
    tr(G - S + "ms");
  }

  private static boolean eof() {
    if (lenbuf == -1)
      return true;
    int lptr = ptrbuf;
    while (lptr < lenbuf)
      if (!isSpaceChar(inbuf[lptr++]))
        return false;

    try {
      is.mark(1000);
      while (true) {
        int b = is.read();
        if (b == -1) {
          is.reset();
          return true;
        } else if (!isSpaceChar(b)) {
          is.reset();
          return false;
        }
      }
    } catch (IOException e) {
      return true;
    }
  }

  private static byte[] inbuf = new byte[1024];
  static int lenbuf = 0, ptrbuf = 0;

  private static int readByte() {
    if (lenbuf == -1)
      throw new InputMismatchException();
    if (ptrbuf >= lenbuf) {
      ptrbuf = 0;
      try {
        lenbuf = is.read(inbuf);
      } catch (IOException e) {
        throw new InputMismatchException();
      }
      if (lenbuf <= 0)
        return -1;
    }
    return inbuf[ptrbuf++];
  }

  private static boolean isSpaceChar(int c) {
    return !(c >= 33 && c <= 126);
  }

  private static int skip() {
    int b;
    while ((b = readByte()) != -1 && isSpaceChar(b))
      ;
    return b;
  }

  private static double nd() {
    return Double.parseDouble(ns());
  }

  private static char nc() {
    return (char) skip();
  }

  private static String nline() {
    int b = skip();
    StringBuilder sb = new StringBuilder();
    while (b != '\n') { // when nextLine, (isSpaceChar(b) && b != ' ')
      sb.appendCodePoint(b);
      b = readByte();
    }
    return sb.toString();
  }

  private static String ns() {
    int b = skip();
    StringBuilder sb = new StringBuilder();
    while (!(isSpaceChar(b))) { // when nextLine, (isSpaceChar(b) && b != ' ')
      sb.appendCodePoint(b);
      b = readByte();
    }
    return sb.toString();
  }

  private static char[] ns(int n) {
    char[] buf = new char[n];
    int b = skip(), p = 0;
    while (p < n && !(isSpaceChar(b))) {
      buf[p++] = (char) b;
      b = readByte();
    }
    return n == p ? buf : Arrays.copyOf(buf, p);
  }

  private static char[][] nm(int n, int m) {
    char[][] map = new char[n][];
    for (int i = 0; i < n; i++)
      map[i] = ns(m);
    return map;
  }

  private static int[] na(int n) {
    int[] a = new int[n];
    for (int i = 0; i < n; i++)
      a[i] = ni();
    return a;
  }

  private static int ni() {
    int num = 0, b;
    boolean minus = false;
    while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
      ;
    if (b == '-') {
      minus = true;
      b = readByte();
    }

    while (true) {
      if (b >= '0' && b <= '9') {
        num = num * 10 + (b - '0');
      } else {
        return minus ? -num : num;
      }
      b = readByte();
    }
  }

  private static long nl() {
    long num = 0;
    int b;
    boolean minus = false;
    while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
      ;
    if (b == '-') {
      minus = true;
      b = readByte();
    }

    while (true) {
      if (b >= '0' && b <= '9') {
        num = num * 10 + (b - '0');
      } else {
        return minus ? -num : num;
      }
      b = readByte();
    }
  }

  private static void tr(Object... o) {
    if (INPUT.length() != 0)
      System.out.println(Arrays.deepToString(o));
  }
}

• Subtask 1: 40 / 100