█████████ ████ ███░░░░░███ ░░███ ███ ░░░ ██████ ███████ ██████ ██████ ░███ ███░░███ ███░░███ ███░░███ ███░░███ ░███ ░███ ░███░███ ░███ ░███████ ░███ ░███ ░░███ ███░███ ░███░███ ░███ ░███░░░ ░███ ░███ ░░█████████ ░░██████ ░░████████░░██████ ░░██████ ░░░░░░░░░ ░░░░░░ ░░░░░░░░ ░░░░░░ ░░░░░░

Envío 6607

Problema 0xcf - Mirando al horizonte

  • Autor: rpedrazacoello
  • Fecha: 2022-09-02 19:55:15 UTC (Hace 29 días)
Caso # Resultado Tiempo Memoria
#1
Correcto
0.138 s 14 KBi
#2
Correcto
0.13 s 13 KBi
#3
Correcto
0.178 s 14 KBi
#4
Correcto
0.15 s 13 KBi
#5
Correcto
0.133 s 13 KBi
#6
Error en tiempo de ejecución (NZEC)
Exited with error status 137
run: line 1:     3 Killed                  /usr/local/openjdk13/bin/java Main
0.975 s 125 KBi
#7
Tiempo límite excedido
1.046 s 125 KBi
#8
Tiempo límite excedido
1.022 s 111 KBi
#9
Tiempo límite excedido
1.018 s 125 KBi
#10
Tiempo límite excedido
1.027 s 122 KBi
Puntos totales: 50 / 100

Código

import java.util.HashMap;
import java.util.Scanner;
import java.util.Stack;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int casosDePrueba = scanner.nextInt();

        for(int caso=1; caso<=casosDePrueba; caso++){
            int n = scanner.nextInt();

            HashMap<Integer, Integer> memoization = new HashMap<Integer, Integer>();
            Stack<Key> stack = new Stack<Key>();
            for(int i=0; i<n; i++){
                int height = scanner.nextInt();
                while (!stack.isEmpty() && stack.peek().getHeight() < height) {
                    Key key = stack.pop();
                    memoization.put(key.getIndex(), height);
                }
                stack.add(new Key(i, height));
            }

            System.out.print("Case #" + caso + ":");
            for(int i=0; i<n; i++){
                if(memoization.containsKey(i)){
                    System.out.print(" " + memoization.get(i));
                } else {
                    System.out.print(" -1");
                }
            }

            System.out.println();
        }
    }

//    /**
//     * This doesn't work for this problem.
//     * I need the successor(x) to be to the first index i after x where value(i) > value(x)
//     * @param start
//     * @param array
//     * @return
//     */
//    private static int findMaxSuffixArray(int start, int[] array){
//        if(memoization.containsKey(start)){
//            return memoization.get(start);
//        }
//
//        if(start == array.length){
//            memoization.put(start, -1);
//            return -1;
//        }
//
//        int value = array[start];
//        int recResponse = findMaxSuffixArray(start+1, array);
//
//        int max = Math.max(value, recResponse);
//        memoization.put(start, max);
//        return max;
//    }

    private static class Key{
        private int index;
        private int height;

        public Key(int index, int height) {
            this.index = index;
            this.height = height;
        }

        public int getIndex() {
            return index;
        }

        public int getHeight() {
            return height;
        }
    }
}