import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Collections; import java.util.HashMap; import java.util.PriorityQueue; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int T = Integer.parseInt(br.readLine()); StringBuilder sb = new StringBuilder(); for(int testcase = 1 ; testcase <= T ; testcase++) { // System.out.println("----- " + testcase +" ------"); int N = Integer.parseInt(br.readLine()); StringTokenizer st; int in = 0; int out = 0; PriorityQueue pq = new PriorityQueue<>(); PriorityQueue rpq = new PriorityQueue<>(Collections.reverseOrder()); HashMap remove_front = new HashMap<>(); HashMap remove_back = new HashMap<>(); for(int i = 0 ; i < N ; i++) { st = new StringTokenizer(br.readLine()); String command = st.nextToken(); int target = Integer.parseInt(st.nextToken()); if(command.equals("I")) { in++; pq.offer(target); rpq.offer(target); } if(command.equals("D")) { if(target == -1 && !pq.isEmpty()) { out++; int tmp = pq.poll(); remove_front.put(tmp, remove_front.getOrDefault(tmp, 0) + 1); } if(target == 1 && !rpq.isEmpty()){ out++; int tmp = rpq.poll(); remove_back.put(tmp, remove_back.getOrDefault(tmp, 0) + 1); } } // System.out.println("-----"+ command + " " +target+" ------"); // System.out.println("----- 작은거 삭제 정보 ------"); // System.out.println(remove_front.toString()); // System.out.println("----- 큰거 삭제 정보 ------"); // System.out.println(remove_back.toString()); // System.out.println("----- 정방향 PQ ------"); // System.out.println(pq.toString()); // System.out.println("----- 역방향 PQ ------"); // System.out.println(rpq.toString()); // System.out.println("-------------------------\n\n"); } if(out >= in) { sb.append("EMPTY\n"); }else { // 최대값 출력 while(true) { if(rpq.isEmpty()) { // 값이 비어있는 경우 종료 sb.append("EMPTY\n"); } int tmp = rpq.poll(); if(!remove_front.containsKey(tmp)) { // 최대값을 찾은 경우 sb.append(tmp).append(" "); break; }else { // 이미 지워진 경우 if(remove_front.get(tmp) > 1) remove_front.put(tmp, remove_front.get(tmp)-1); else remove_front.remove(tmp); } } // 최소값 while(true) { if(pq.isEmpty()) { // 값이 비어있는 경우 종료 sb.append("EMPTY\n"); return; } int tmp = pq.poll(); if(!remove_back.containsKey(tmp)) { // 최대값을 찾은 경우 sb.append(tmp).append("\n"); break; }else { // 이미 지워진 경우 if(remove_back.get(tmp) > 1) remove_back.put(tmp, remove_back.get(tmp)-1); else remove_back.remove(tmp); } } } } System.out.println(sb); } }

제출 #11471

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: