Submission #604111

#	Time	Username	Problem	Language	Result	Execution time	Memory
604111		chuangsheep	Balloons (CEOI11_bal)	Java	100 / 100	1370 ms	33936 KiB

bal

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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10