oj.uz

Submission #1108423

# Submission time Handle Problem Language Result Execution time Memory
1108423 2024-11-04T05:38:47 Z min_j2024 Job Scheduling (CEOI12_jobs) Java 11
0 / 100
 115 ms 17624 KB 
import java.io.*;
import java.util.*;

/**
 * Problem    = ceoiJobScheduling
 * Date       = Sun Nov  3 17:02:47 PST 2024
 */
class ceoiJobScheduling {

  static class Req {
    int id;
    int day;
    Req(int id, int day){
      this.id=id;
      this.day=day;
    }
    @Override
    public String toString() {
      return "{id:" + id + ", day:" + day + "}";
    }
  }

  public void run() {
    int N = in.nextInt();
    int D = in.nextInt();
    int M = in.nextInt();
    List<Deque<Req>> schedule = new ArrayList<>(N+1);
    for(int i = 0; i <= N; ++i)
      schedule.add(new LinkedList<>());
    for(int i = 1; i <= M; ++i){
      Req r = new Req(i, in.nextInt());
      schedule.get(r.day).addFirst(r);
    }

    int left = 1;
    int right = 1000000;
    int ans = 0;
    List<Deque<Req>> answer = Collections.emptyList();
    while(left<=right){
      int machines = (left+right)/2;
      List<Deque<Req>> candidate = copy(schedule);
      for(int i = 1; i < N; ++i){
        var today = candidate.get(i);
        var tmrw = candidate.get(i+1);
        while(today.size() > machines){
          tmrw.addFirst(today.pollLast());
        }
      }
      boolean valid = valid(candidate, machines, D);
      if (valid){
        ans = machines;
        answer = candidate;
        right = machines - 1;
      } else
        left = machines + 1;
      //out.println(machines + " " + valid);
    }
    out.println(ans);
    for(int i = 1; i <= N; ++i){
      var day = answer.get(i);
      for(var r : day)
        out.print(r.id + " ");
      out.println(0);
    }
  }

  boolean valid(List<Deque<Req>> candidate, int machines, int delay){
    int N = candidate.size() - 1;
    for(int i = 1; i <= N; ++i){
      var day = candidate.get(i);
      if (day.size() > machines)
        return false;
      for(var r : day){
        if (i - r.day + 1 > delay)
          return false;
      }
    }
    return true;
  }

  List<Deque<Req>> copy(List<Deque<Req>> schedule){
    List<Deque<Req>> copy = new ArrayList<>(schedule.size());
    for(var day : schedule){
      copy.add(new LinkedList<>(day));
    }
    return copy;
  }


  /////////////////////////////////////////////////////////////////////////////////
  static InputStream in(){try{if(file!=null)return new FileInputStream(file+".in");
  return System.in;}catch(Exception e){throw new RuntimeException(e);}}static
  OutputStream out(){try{if(file!=null)return new FileOutputStream(file+".out");
  return System.out;}catch(Exception e){throw new RuntimeException(e);}}IR in=new
  IR(in());PrintWriter out=new PrintWriter(out());void c(){out.close();}static
  class IR{BufferedReader r;StringTokenizer t=null;IR(InputStream s){r=new
  BufferedReader(new InputStreamReader(s),32768);}boolean p(){while(t==null||
  !t.hasMoreTokens()){try{String l=r.readLine();if(l==null)return false;t=new
  StringTokenizer(l);}catch(IOException e){throw new RuntimeException(e);}}return
  true;}boolean hasNext(){return p();}String next(){p();return t.nextToken();}int
  nextInt(){return Integer.parseInt(next());}long nextLong(){return Long.parseLong(
  next());}double nextDouble(){return Double.parseDouble(next());}}public static
  void main(String[]args){ceoiJobScheduling t=new ceoiJobScheduling();t.run();t.c();}
  /////////////////////////////////////////////////////////////////////////////////
  static String file;
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 105 ms 16684 KB Execution failed because the return code was nonzero
2 Runtime error 111 ms 16876 KB Execution failed because the return code was nonzero
3 Runtime error 109 ms 16604 KB Execution failed because the return code was nonzero
4 Runtime error 111 ms 17096 KB Execution failed because the return code was nonzero
5 Runtime error 106 ms 17044 KB Execution failed because the return code was nonzero
6 Runtime error 102 ms 16672 KB Execution failed because the return code was nonzero
7 Runtime error 105 ms 17252 KB Execution failed because the return code was nonzero
8 Runtime error 111 ms 16876 KB Execution failed because the return code was nonzero
9 Runtime error 107 ms 17056 KB Execution failed because the return code was nonzero
10 Runtime error 114 ms 17624 KB Execution failed because the return code was nonzero
11 Runtime error 105 ms 16828 KB Execution failed because the return code was nonzero
12 Runtime error 99 ms 16984 KB Execution failed because the return code was nonzero
13 Runtime error 99 ms 17168 KB Execution failed because the return code was nonzero
14 Runtime error 99 ms 16780 KB Execution failed because the return code was nonzero
15 Runtime error 99 ms 16628 KB Execution failed because the return code was nonzero
16 Runtime error 100 ms 17408 KB Execution failed because the return code was nonzero
17 Runtime error 102 ms 17228 KB Execution failed because the return code was nonzero
18 Runtime error 103 ms 16752 KB Execution failed because the return code was nonzero
19 Runtime error 115 ms 16928 KB Execution failed because the return code was nonzero
20 Runtime error 101 ms 16944 KB Execution failed because the return code was nonzero