oj.uz

답안 #604111

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
604111 2022-07-24T18:20:48 Z chuangsheep Balloons (CEOI11_bal) Java 11
100 / 100
 1370 ms 33936 KB 
import java.io.*;
import java.util.*;

// class Balloons causes compilation error on ojuz
public class bal {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		// number of balloonss
		int n = Integer.parseInt(br.readLine());

		// the radius of each balloon after inflating
		double[] res = new double[n];
		// the balloons we should check when we add a new one
		Stack<Balloon> toCheck = new Stack<>();

		// simulate inflating balloons
		for (int i = 0; i < n; i++) {
			// the x coordinate and the maximum radius of the current balloon being inflated
			StringTokenizer st = new StringTokenizer(br.readLine());
			long x = Integer.parseInt(st.nextToken());
			double r = Integer.parseInt(st.nextToken());

			// the maximum radius of the current balloon
			double maxR = r;
			/*
			 * as long as the stack is not empty, we want to check
			 * if the last balloon makes the radius of the current balloon smaller
			 */
			while (!toCheck.isEmpty()) {
				// the radius if the current balloon touches the last balloon
				double toLastR = toCheck.peek().calcR(x);
				/*
				 * the maximum possible radius is the smaller one between current 
				 * maximum and the maximum radius so that we touches the last balloon
				 * (by which we have to stop)
				 */
				maxR = Math.min(maxR, toLastR);

				/*
				 * if current maximum radius >= radius of the last balloon, we can
				 * remove the last balloon since it will never be touched by any
				 * new balloons other than the current one
				 */
				if (maxR >= toCheck.peek().r) {
					toCheck.pop();
					// check the next balloon saved which will possibly reduce max_r
					continue;
				}
				/*
				 * otherwise, the current balloon is smaller than the last saved balloon
				 * and we can stop checking
				 */
				else {
					break;
				}
			}
			/*
			 * save the x coordinate and radius of the current balloon, so that
			 * it can be checked later when a new balloon being inflated
			 */
			toCheck.add(new Balloon(x, maxR));
			res[i] = maxR;
		}

		PrintWriter pw = new PrintWriter(System.out);
		for (double r : res) {
			pw.println(r);
		}
		pw.close();
	}

	// class to save the data of an infalted balloon
	private static class Balloon {
		public long x;
		public double r;

		public Balloon(long x, double r) {
			this.x = x;
			this.r = r;
		}

		/*
		 * how long can the radius of the new balloon at position bx be
		 * so that it touches the ballon a, which is described by
		 * its x position a.first and its radius a.second
		 */
		public double calcR(long bx) {
			return (x - bx) * (x - bx) / (4 * r);
		}
	}
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 65 ms 8328 KB 10 numbers

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 66 ms 8144 KB 2 numbers

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 97 ms 8884 KB 505 numbers

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 356 ms 15460 KB 2000 numbers

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 756 ms 18672 KB 20000 numbers

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1351 ms 33620 KB 50000 numbers
2 Correct 534 ms 17364 KB 49912 numbers

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1319 ms 32352 KB 100000 numbers

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 954 ms 26484 KB 115362 numbers
2 Correct 634 ms 18748 KB 119971 numbers

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1067 ms 25976 KB 154271 numbers
2 Correct 629 ms 21128 KB 200000 numbers

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1370 ms 33936 KB 200000 numbers
2 Correct 603 ms 21292 KB 199945 numbers