Untitled

mail@pastecode.io avatar
unknown
plain_text
2 years ago
3.0 kB
1
Indexable
Never
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

class Result {
    //Queues to store values in ascending and descending order
    PriorityQueue<Integer> min; // ascending
    PriorityQueue<Integer> max; // descending
        
    Result(int size) {
        min = new PriorityQueue<>(size / 2 + 1);
        max = new PriorityQueue<>(size / 2 + 1, Collections.reverseOrder());         
    }
    
    public void insert(int x) {
        if (max.isEmpty() || x < max.peek()) {
            max.offer(x);
        } else {
            min.offer(x);
        }
    }
    
    public void balance() {
        if (max.size() > min.size() + 1) {
            min.offer(max.poll());
        }
        
        if (min.size() > max.size() + 1) {
            max.offer(min.poll());
        }
    }
    
    public Double getMedian() {
        //Size is odd -> pick median in the larger stack
        if (max.size() > min.size()) {
            return Double.valueOf(max.peek());
        }
        
        if (min.size() > max.size()) {
            return Double.valueOf(min.peek());
        }
        
        //Size is even -> pick medians in both stacks
        return 0.5 * (max.peek() + min.peek());
    }
    
    public List<Double> runningMedian(List<Integer> a) {
        List<Double> arr = new ArrayList<>();
        
        for (int i = 0; i < a.size(); i++) {
            insert(a.get(i));
            balance(); //balance when the difference of sizes >= 2
            arr.add(getMedian());
        }
        
        return arr;
    }

}

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());

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

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

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