제출 #642592

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
642592		accidentac	Job Scheduling (CEOI12_jobs)	Java	40 / 100	1098 ms	61412 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>> form(int count) {
    List<List<Integer>> ans = new ArrayList<>();
    for (int day = 1, l = 0, r = 0; day <= n; day++) {
      List<Integer> cur = new ArrayList<>();
      while (r < m && jobs[r][0] == day) {
        r++;
      }
      for (int rep = 0; rep < count && l < r; rep++) {
        cur.add(jobs[l++][1]);
      }
      cur.add(0);
      ans.add(cur);
    }
    return ans;
  }

  // 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 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 (List<Integer> row : form(best)) {
      for (int x : row) {
        io.print(x);
        if (x != 0)
          io.print(' ');
      }
      io.println();
    }
    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: 40 / 100