oj.uz

Submission #544782

# Submission time Handle Problem Language Result Execution time Memory
544782 2022-04-02T16:44:26 Z rainboy Balloons (CEOI11_bal) C++
100 / 100
 132 ms 9832 KB 
#include <math.h>
#include <stdio.h>

#define N	200000

double min(double a, double b) { return a < b ? a : b; }

int xx[N]; double yy[N], yy_[N];

double f(int i, int j) {
	return (xx[j] * yy_[i] - xx[i] * yy_[j]) / (yy_[i] - yy_[j]);
}

int main() {
	static int qu[N];
	int n, i, cnt;

	scanf("%d", &n);
	cnt = 0;
	for (i = 0; i < n; i++) {
		int r, i_;

		scanf("%d%d", &xx[i], &r);
		while (cnt >= 2 && f(qu[cnt - 2], qu[cnt - 1]) <= xx[i])
			cnt--;
		i_ = cnt == 0 ? -1 : qu[cnt - 1];
		yy[i] = cnt == 0 ? r : min(r, (double) (xx[i] - xx[i_]) * (xx[i] - xx[i_]) / 4 / yy[i_]);
		yy_[i] = sqrt(yy[i]);
		printf("%f\n", yy[i]);
		while (cnt && (yy[qu[cnt - 1]] <= yy[i] || cnt >= 2 && f(qu[cnt - 2], qu[cnt - 1]) <= f(qu[cnt - 1], i)))
			cnt--;
		qu[cnt++] = i;
	}
	return 0;
}

Compilation message

bal.cpp: In function 'int main()':
bal.cpp:30:55: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   30 |   while (cnt && (yy[qu[cnt - 1]] <= yy[i] || cnt >= 2 && f(qu[cnt - 2], qu[cnt - 1]) <= f(qu[cnt - 1], i)))
      |                                              ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bal.cpp:18:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
bal.cpp:23:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |   scanf("%d%d", &xx[i], &r);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 296 KB 2000 numbers

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1068 KB 20000 numbers

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 2436 KB 50000 numbers
2 Correct 36 ms 2616 KB 49912 numbers

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 4756 KB 100000 numbers

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 5528 KB 115362 numbers
2 Correct 69 ms 6052 KB 119971 numbers

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 7372 KB 154271 numbers
2 Correct 116 ms 9832 KB 200000 numbers

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 9040 KB 200000 numbers
2 Correct 120 ms 9804 KB 199945 numbers