Untitled

mail@pastecode.io avatar
unknown
plain_text
2 years ago
3.2 kB
3
Indexable
Never
import java.io.*;
import java.util.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

class Pair implements Comparable<Pair> {
    int val;
    int i;

    Pair(int val, int i) {
        this.val = val;
        this.i = i;
    }

    public int compareTo(Pair b) {
        if (this.val != b.val) {
            return (b.val < this.val) ? 1 : -1;
        }

        if (b.i == this.i) {
            return 0;
        }
        
        return (b.i < this.i) ? 1 : -1;
    }
}

class Result {
    public static List<Double> runningMedian(List<Integer> a) {
        // Map to store values and their occurences
        HashMap<Integer, Integer> values = new HashMap<>();
        ArrayList<Double> medians = new ArrayList<>();
        TreeSet<Pair> tree = new TreeSet<>();
        
        //Set the occurences to 0
        for (int x : a) {
            values.put(x, 0);
        }
        
        //Init the current median
        Pair median = new Pair(0, 0);
        
        for (int i = 1; i <= a.size(); i++) {
            int x = a.get(i - 1);
            
            //Update its ocurrences in map
            values.put(x, values.get(x) + 1);
            
            //Add the value to tree
            Pair newPair = new Pair(x, values.get(x));
            tree.add(newPair);
        
            //Update the median according to the new pair
            if (i % 2 == 0) {
                // New pair < median
                if (median.compareTo(newPair) == 1) { 
                    median = tree.lower(median);
                }
                
                medians.add(0.5 * (median.val + tree.higher(median).val));
            } else {
                // Median < new pair
                if (newPair.compareTo(median) == 1) {
                    median = tree.higher(median);
                }
                    
                medians.add(1.0 * median.val);
            }
        }
            
        return medians;
    }

}

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int aCount = Integer.parseInt(bufferedReader.readLine().trim());

        List<Integer> a = IntStream.range(0, aCount).mapToObj(i -> {
            try {
                return bufferedReader.readLine().replaceAll("\\s+$", "");
            } catch (IOException ex) {
                throw new RuntimeException(ex);
            }
        })
            .map(String::trim)
            .map(Integer::parseInt)
            .collect(toList());

        List<Double> result = Result.runningMedian(a);

        bufferedWriter.write(
            result.stream()
                .map(Object::toString)
                .collect(joining("\n"))
            + "\n"
        );

        bufferedReader.close();
        bufferedWriter.close();
    }
}