fork download
copy 
  1. import java.io.*;
  2. import java.util.*;
  3.  
  4. class Makanan {
  5.     private int harga;
  6.     private String tipe;
  7.  
  8.     public Makanan(int harga, String tipe){
  9.         this.harga=harga;
  10.         this.tipe=tipe;
  11.     }
  12.  
  13.     String getTipe(){
  14.         return this.tipe;
  15.     }
  16.  
  17.     int getHarga(){
  18.         return this.harga;
  19.     }
  20. }
  21.  
  22. class Pelanggan {
  23.     private int id;
  24.     private String statusKesehatan;
  25.     private int uang;
  26.     private Queue<Makanan> makananDiPesan;
  27.     private Queue<Koki> dilayaniKoki;
  28.     private int tagihan;
  29.  
  30.  
  31.     public Pelanggan(int id, int uang, String statusKesehatan){
  32.         this.statusKesehatan=statusKesehatan;
  33.         this.uang=uang;
  34.         makananDiPesan = new LinkedList<Makanan>();
  35.         dilayaniKoki = new LinkedList<Koki>();
  36.         tagihan=0;
  37.         this.id=id;
  38.     }
  39.  
  40.     int getId(){
  41.         return this.id;
  42.     }
  43.  
  44.     String getStatus(){
  45.         return this.statusKesehatan;
  46.     }
  47.  
  48.     void tambahPesanan (Makanan makanan){
  49.         makananDiPesan.add(makanan);
  50.         tagihan+=makanan.getHarga();
  51.     }
  52.  
  53.     int getTagihan(){
  54.         return this.tagihan;
  55.     }
  56.  
  57.     Makanan getMakanan() {
  58.         return this.makananDiPesan.poll();
  59.     }
  60.  
  61.     int getUang(){
  62.         return this.uang;
  63.     }
  64.  
  65.     Koki getKoki() {
  66.         this.makananDiPesan.poll();
  67.         return this.dilayaniKoki.poll();
  68.     }
  69.  
  70.     void tambahKoki (Koki koki){
  71.         this.dilayaniKoki.add(koki);
  72.     }
  73.  
  74. }
  75.  
  76. class Koki {
  77.     private int id;
  78.     private int banyakMelayani=0;
  79.     private String spesialisasi;
  80.  
  81.     public Koki(int id, String spesialisasi, int banyakMelayani){
  82.         this.id=id;
  83.         this.spesialisasi=spesialisasi;
  84.         this.banyakMelayani=banyakMelayani;
  85.     }
  86.  
  87.     int getId(){
  88.         return this.id;
  89.     }
  90.  
  91.     String getSpesialisasi(){
  92.         return this.spesialisasi;
  93.     }
  94.  
  95.     int getBanyakMelayani(){
  96.         return this.banyakMelayani;
  97.     }
  98.  
  99.     void tambahPelayanan(){
  100.         this.banyakMelayani++;
  101.     }
  102.  
  103. }
  104.  
  105. class comparator implements Comparator<Koki>{
  106.     @Override
  107.     public int compare(Koki a, Koki b){
  108.         // cek pada banyak melayani
  109.         if (a.getBanyakMelayani() < b.getBanyakMelayani()) return -1; 
  110.         else if (a.getBanyakMelayani() == b.getBanyakMelayani()){
  111.             // cek pada spesialisasi (sort secara descending)
  112.             if (a.getSpesialisasi().compareTo(b.getSpesialisasi())>0){
  113.                 return -1;
  114.             } else if (a.getSpesialisasi().compareTo(b.getSpesialisasi()) == 0){
  115.                 // cek pada id
  116.                 if (a.getId() < b.getId()) return -1;
  117.             }
  118.         }
  119.         return 1;
  120.     }
  121. }
  122.  
  123. class TP1 {
  124.     private static InputReader in;
  125.     private static PrintWriter out;
  126.     private static ArrayList<Makanan> daftarMakanan = new ArrayList<Makanan>();; // index arraylist == id/index makanan-1
  127.     private static PriorityQueue<Koki> daftarKokiA = new PriorityQueue<Koki>(new comparator());
  128.     private static PriorityQueue<Koki> daftarKokiG = new PriorityQueue<Koki>(new comparator());
  129.     private static PriorityQueue<Koki> daftarKokiS = new PriorityQueue<Koki>(new comparator());
  130.     private static HashMap<Integer, Pelanggan> daftarPelanggan; // id, pelanggan, berlaku selamanya
  131.     private static ArrayList<Integer> daftarBlacklist; // isinya id pelanggan dan berlaku selamanya
  132.     private static ArrayList<Pelanggan> restoran; // berlaku pada hari itu
  133.     private static Queue<Pelanggan> urutanPelanggan; // berlaku pada hari itu
  134.     private static HashMap<String, Integer> costs; 
  135.     private static HashMap<String, Boolean> foundPackage;
  136.  
  137.     public static void main(String[] args) {
  138.         InputStream inputStream = System.in;
  139.         in = new InputReader(inputStream);
  140.         OutputStream outputStream = System.out;
  141.         out = new PrintWriter(outputStream);
  142.  
  143.         // Input keperluan makanan lalu buat objek Makanan dan tambahkan ke daftarMakanan
  144.         int banyakMakanan = in.nextInt();
  145.         for (int i=0;i<banyakMakanan;i++) { // 50000
  146.             int harga = in.nextInt();
  147.             String tipe = in.next();
  148.             Makanan makanan = new Makanan(harga, tipe);
  149.             daftarMakanan.add(makanan);
  150.         }
  151.  
  152.         // Input keperluan koki lalu buat objek Koki dan tambahkan ke daftarKoki
  153.         int banyakKoki = in.nextInt();
  154.         for (int i=0;i<banyakKoki;i++) { // 1000000
  155.             String spesialisasi = in.next();
  156.             if (spesialisasi.equals("A")){
  157.                 Koki koki= new Koki(i+1,"A",0);
  158.                 daftarKokiA.add(koki);
  159.             } else if (spesialisasi.equals("G")){
  160.                 Koki koki= new Koki(i+1,"G",0);
  161.                 daftarKokiG.add(koki);
  162.             } else {
  163.                 Koki koki= new Koki(i+1,"S",0);
  164.                 daftarKokiS.add(koki);
  165.             }
  166.         }
  167.  
  168.         int banyakPelanggan = in.nextInt(); 
  169.         daftarBlacklist = new ArrayList<Integer>();
  170.         daftarPelanggan = new HashMap<Integer, Pelanggan>(banyakPelanggan);
  171.         int banyakKursi = in.nextInt(); 
  172.         int jumlahHari = in.nextInt(); 
  173.  
  174.         for (int hariKe=1;hariKe<=jumlahHari;hariKe++){ // 5
  175.             int jumlahPelanggan = in.nextInt(); 
  176.             int pelangganDuduk = 0;
  177.             int penghitungStatus = 0; // jika positif maka lebih banyak pelanggan positif dan sebaliknya
  178.             int[] memo = new int[jumlahPelanggan]; // menyimpan status pelanggan sebelum nya
  179.             restoran = new ArrayList<Pelanggan>();
  180.             urutanPelanggan = new LinkedList<Pelanggan>();
  181.             for (int pelangganKe=0;pelangganKe<jumlahPelanggan;pelangganKe++) { // 100000
  182.                 // Input keperluan Pelanggan
  183.                 int id = in.nextInt();
  184.                 String status = in.next();
  185.                 int uang = in.nextInt();
  186.                 int range, hasil;
  187.  
  188.                 // Lakukan advance scanning
  189.                 if (status.equals("?")){ 
  190.                     range = in.nextInt();
  191.                     if (range==pelangganKe) hasil=penghitungStatus;
  192.                     else hasil = penghitungStatus-memo[pelangganKe - range - 1];
  193.                     if (hasil>0) status="+";
  194.                     else status="-";
  195.                     // for (int i = pelangganKe-range; i<=pelangganKe-1;i++){ // Hitung pelanggan positif dan negatif 
  196.                     //     if (restoran.get(i).getStatus().equals("+")) pos++;
  197.                     //     else neg++;
  198.                     // }
  199.                     // if (neg<pos) status="+";
  200.                     // else status="-";
  201.                 }
  202.  
  203.                 if (status.equals("+")) penghitungStatus++;
  204.                 else penghitungStatus--;
  205.                 memo[pelangganKe]=penghitungStatus;
  206.  
  207.                 // Buat Objek Pelanggan lalu tambahkan ke daftarPelanggan dan restoran. Apabila sudah ada maka update
  208.                 Pelanggan pelanggan = new Pelanggan(id, uang, status);
  209.                 if (daftarPelanggan.containsKey(id)) daftarPelanggan.replace(id, pelanggan);
  210.                 daftarPelanggan.put(id, pelanggan);
  211.                 restoran.add(pelanggan);
  212.  
  213.                 if (status.equals("-") && !daftarBlacklist.contains(id)){ // Diperbolehkan masuk dan tidak ada di daftar blacklist
  214.                     if (pelangganDuduk < banyakKursi) { // Cek keadaan restoran
  215.                         pelangganDuduk++;
  216.                         out.print("1 ");
  217.                     } else {
  218.                         if (pelangganKe==jumlahPelanggan-1) out.print("2");
  219.                         else out.print("2 ");
  220.                     }
  221.                 } else if (status.equals("+") && !daftarBlacklist.contains(id)){ // Pelanggan berstatus positif
  222.                     out.print("0 ");
  223.                 } else { // Pelanggan di blacklist
  224.                     out.print("3 ");
  225.                 }
  226.             }
  227.             out.println();
  228.  
  229.             int jumlahPelayanan = in.nextInt();
  230.             for (int layananKe=0;layananKe<jumlahPelayanan;layananKe++){ // 200000
  231.                 String perintah = in.next();
  232.                 if (perintah.equals("P")){
  233.                     int idPelanggan = in.nextInt();
  234.                     int indexMakanan = in.nextInt();
  235.                     Koki koki = null;
  236.  
  237.                     // Mencari koki sesuai persyaratan 
  238.                     if (daftarMakanan.get(indexMakanan-1).getTipe().equals("A")){
  239.                         koki=daftarKokiA.peek();
  240.                     } else if (daftarMakanan.get(indexMakanan-1).getTipe().equals("G")){
  241.                         koki=daftarKokiG.peek();
  242.                     } else {
  243.                         koki=daftarKokiS.peek();
  244.                     }
  245.  
  246.                     Pelanggan pelanggan = daftarPelanggan.get(idPelanggan);
  247.                     pelanggan.tambahPesanan(daftarMakanan.get(indexMakanan-1));
  248.                     pelanggan.tambahKoki(koki);
  249.  
  250.                     urutanPelanggan.add(pelanggan);
  251.                     out.println(koki.getId());
  252.                     // Print id koki yg mengambil pesanan
  253.  
  254.                 } else if (perintah.equals("L")){
  255.                     Pelanggan pelanggan = urutanPelanggan.poll();
  256.                     Koki koki = pelanggan.getKoki();
  257.  
  258.                     // Update koki pada banyak pelayanan
  259.                     if (daftarKokiA.contains(koki)){
  260.                         daftarKokiA.remove(koki);
  261.                         koki.tambahPelayanan();
  262.                         daftarKokiA.add(koki);
  263.                     } else if (daftarKokiG.contains(koki)){
  264.                         daftarKokiG.remove(koki);
  265.                         koki.tambahPelayanan();
  266.                         daftarKokiG.add(koki);
  267.                     } else {
  268.                         daftarKokiS.remove(koki);
  269.                         koki.tambahPelayanan();
  270.                         daftarKokiS.add(koki);
  271.                     }
  272.                     out.println(pelanggan.getId());
  273.                     // Print id pelanggan yg memesan
  274.  
  275.                 } else if (perintah.equals("B")){
  276.                     int idPelanggan = in.nextInt();
  277.                     Pelanggan pelanggan = daftarPelanggan.get(idPelanggan);
  278.  
  279.                     if (pelanggan.getUang() < pelanggan.getTagihan()){ // Pelanggan tidak mampu membayar
  280.                         daftarBlacklist.add(pelanggan.getId());
  281.                         out.println(0);
  282.                     } else{
  283.                         out.println(1);
  284.                     }
  285.                     // Print mencukupi/tidak   
  286.  
  287.                 } else if (perintah.equals("C")){
  288.                     int q = in.nextInt();
  289.  
  290.                     PriorityQueue<Koki> urutanKoki = new PriorityQueue<Koki>(new comparator()); // Berisi semua tipe koki
  291.                     urutanKoki.addAll(daftarKokiS);
  292.                     urutanKoki.addAll(daftarKokiG);
  293.                     urutanKoki.addAll(daftarKokiA);
  294.  
  295.                     for (int i=0;i<q;i++) { // 500000
  296.                         if (i<q-1) out.print(urutanKoki.poll().getId() + " ");
  297.                         else out.println(urutanKoki.poll().getId());
  298.                     }
  299.  
  300.                     // Print id koki berada pada urutan ke q teratas
  301.                 } else if (perintah.equals("D")){ // 2500
  302.                     int costA = in.nextInt();
  303.                     int costG = in.nextInt();
  304.                     int costS = in.nextInt();
  305.                     costs = new HashMap<String, Integer>();
  306.                     costs.put("A", costA);
  307.                     costs.put("G", costG);
  308.                     costs.put("S", costS);
  309.  
  310.                     foundPackage = new HashMap<String , Boolean>();
  311.                     foundPackage.put("A", false);
  312.                     foundPackage.put("G", false);
  313.                     foundPackage.put("S", false);
  314.  
  315.                     out.println(paketTermurah(0));
  316.                     // harga minimum utk dpt membeli seluruh daftarMakanan makanan
  317.                 }   
  318.             }
  319.         }
  320.  
  321.         out.close();
  322.     }
  323.  
  324.     public static int paketTermurah(int start){
  325.         if (start==daftarMakanan.size()) return 0;
  326.  
  327.         int ans = Integer.MAX_VALUE;
  328.         for (int i=start; i<daftarMakanan.size(); i++){ // 1000
  329.             int temp=0;
  330.             if (daftarMakanan.get(start).getTipe().equals(daftarMakanan.get(i).getTipe())){
  331.                 if (i==start) {
  332.                     temp = daftarMakanan.get(start).getHarga() + paketTermurah(i+1);
  333.                 } else if (daftarMakanan.get(start).getTipe().equals("A")) {
  334.                     if (foundPackage.get("A"))  continue;
  335.                     else { 
  336.                         foundPackage.replace("A", true);
  337.                         temp =  costs.get("A")*(i-start+1) + paketTermurah(i+1);
  338.                         foundPackage.replace("A",false);
  339.                     }
  340.                 } else if (daftarMakanan.get(start).getTipe().equals("G")) {
  341.                     if (foundPackage.get("G")) continue;
  342.                     else {
  343.                         foundPackage.replace("G", true);
  344.                         temp =  costs.get("G")*(i-start+1) + paketTermurah(i+1);
  345.                         foundPackage.replace("G",false);
  346.                     }
  347.                 }  else {
  348.                     if (foundPackage.get("S")) continue;
  349.                     else {
  350.                         foundPackage.replace("S", true);
  351.                         temp = costs.get("S")*(i-start+1) + paketTermurah(i+1);
  352.                         foundPackage.replace("S",false);
  353.                     }
  354.                 }
  355.                 ans = Math.min(temp, ans);
  356.             }
  357.         }
  358.         return ans;
  359.     }
  360.  
  361.     // taken from https://c...content-available-to-author-only...s.com/submissions/Petr
  362.     // together with PrintWriter, these input-output (IO) is much faster than the
  363.     // usual Scanner(System.in) and System.out
  364.     // please use these classes to avoid your fast algorithm gets Time Limit
  365.     // Exceeded caused by slow input-output (IO)
  366.     static class InputReader {
  367.         public BufferedReader reader;
  368.         public StringTokenizer tokenizer;
  369.  
  370.         public InputReader(InputStream stream) {
  371.             reader = new BufferedReader(new InputStreamReader(stream));
  372.         }
  373.  
  374.         public String next() {
  375.             while (tokenizer == null || !tokenizer.hasMoreElements()) {
  376.                 try {
  377.                     tokenizer = new StringTokenizer(reader.readLine());
  378.                 } catch (IOException e) {
  379.                     throw new RuntimeException(e);
  380.                 }
  381.             }
  382.             return tokenizer.nextToken();
  383.         }
  384.  
  385.         public int nextInt() {
  386.             return Integer.parseInt(next());
  387.         }
  388.  
  389.     }
  390.  
  391. }
  392.  
  393.  
Success #stdin #stdout 0.11s 47608KB
comments (?)
stdin
copy 
5
100000 S
100000 A
100000 A
100000 G
100000 S
5
S G A S A
8
4
3
8
6 - 25000
7 ? 50000 1
8 - 50000
4 + 30000
2 + 50000
3 - 25000
5 ? 50000 4
1 + 25000
122
P 1 1
P 4 5
P 2 3
L
P 4 3
L
P 8 2
P 3 2
P 8 2
P 7 3
L
P 6 2
L
P 8 3
P 8 3
L
P 1 5
P 8 1
P 7 4
L
P 1 1
P 5 2
L
L
P 8 2
L
L
P 1 4
P 7 4
L
P 3 3
L
P 8 2
P 1 4
L
P 1 2
P 6 3
P 6 3
P 2 2
P 6 5
P 6 5
P 8 4
L
P 4 5
L
L
P 7 3
L
P 7 4
L
L
L
P 5 5
P 3 1
P 1 5
P 1 2
P 2 2
P 8 1
L
L
L
L
L
L
P 3 5
P 5 1
L
L
P 2 5
P 2 4
L
P 1 3
L
L
L
L
L
P 8 5
P 4 1
P 7 1
P 7 5
L
L
L
B 6
L
L
L
P 3 4
P 3 3
L
L
L
P 4 1
L
B 8
L
L
L
P 7 2
L
B 1
L
B 3
L
L
B 4
B 2
P 5 1
L
P 7 3
P 5 4
L
B 7
L
P 5 3
L
P 5 2
L
P 5 4
L
B 5
1
1 - 25000
7
P 1 4
P 1 5
P 1 4
L
L
L
B 1
2
4 - 25000
2 ? 25000 1
40
P 2 1
P 4 2
P 4 1
L
P 2 1
P 2 1
P 4 4
P 2 4
P 4 5
P 2 2
L
P 4 3
L
L
P 2 1
P 4 1
P 4 5
P 4 3
P 2 2
P 2 3
L
P 4 1
L
P 2 2
L
P 2 5
L
L
L
L
L
L
L
L
L
L
L
L
B 2
B 4
stdout
copy 
1 1 1 0 0 1 2 0 
1
1
3
1
3
4
3
3
3
3
2
5
4
5
5
8
4
4
2
3
4
5
8
7
5
6
8
2
2
8
5
1
5
2
8
5
5
5
5
1
1
2
7
1
1
5
5
8
2
1
7
3
1
1
1
3
3
1
8
1
1
6
6
2
1
1
6
6
4
2
8
3
4
7
7
5
3
4
4
4
4
1
1
2
0
8
3
5
2
3
2
2
1
4
8
0
4
7
7
3
3
0
3
0
4
7
0
0
4
5
3
2
7
0
5
3
5
5
5
2
5
0
3 
2
4
2
1
1
1
0
3 3 
1
3
1
2
4
4
2
2
4
3
4
5
4
2
4
4
4
5
5
5
2
1
4
5
2
1
4
2
4
2
4
4
4
2
2
4
2
2
0
0
https://ideone.com/CQnqt3
language:
Java (HotSpot 12)
created:
1 year ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!