oj.uz

Submission #746210

# Submission time Handle Problem Language Result Execution time Memory
746210 2023-05-21T22:34:21 Z rahulverma Balloons (CEOI11_bal) Java 11
60 / 100
 2000 ms 31184 KB 
import java.io.*;
import java.math.BigDecimal;
import java.math.RoundingMode;
import java.util.*;
 
public class bal {
 
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int[] coord = new int[n];
		int[] maxRad = new int[n];
		double[] ans = new double[n];
		for(int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			coord[i] = Integer.parseInt(st.nextToken());
			maxRad[i] = Integer.parseInt(st.nextToken());
		}
		ans[0] = maxRad[0];
		Stack<Integer> stack = new Stack<Integer>();
		stack.add(0); // indexes in the stack
		for(int i = 1; i < n; i++) {
			double pos = maxRad[i];
			while(!stack.isEmpty()) {
				int top = stack.peek();
				pos = Math.min(pos, dist(coord[top], ans[top], coord[i]));
				if(pos >= ans[top]) stack.pop();
				else break;
			}
			pos = Math.min(pos, maxRad[i]);
			ans[i] = pos;
			stack.add(i);
		}
		PrintWriter pw = new PrintWriter(System.out);
		for(int i = 0; i < n; i++) {
			pw.format("%.3f", (round(ans[i], 3)));
			pw.println();
		}
		pw.close();
	}
	public static double dist(int x1, double r1, int x2) {
		double x_1 = x1;
		double x_2 = x2;
		return (x_1 - x_2) * (x_1 - x_2) / (4*r1);
	}
	private static double round(double value, int places) {
	    if (places < 0) throw new IllegalArgumentException();
 
	    BigDecimal bd = new BigDecimal(Double.toString(value));
	    bd = bd.setScale(places, RoundingMode.HALF_UP);
	    return bd.doubleValue();
	}
 
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 9636 KB 10 numbers

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 9564 KB 2 numbers

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 10300 KB 505 numbers

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 789 ms 21544 KB 2000 numbers

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1567 ms 22668 KB 20000 numbers

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2055 ms 31184 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2043 ms 30120 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1897 ms 25648 KB 115362 numbers
2 Correct 1424 ms 26364 KB 119971 numbers

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2044 ms 26696 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2041 ms 27164 KB Time limit exceeded
2 Halted 0 ms 0 KB -